LANGUAGES AND REWRITING SYSTEMS

Both natural and programming languages can be viewed as sets of sentences—that is, finite strings of elements of some basic vocabulary. The notion of a language introduced in this section is very general. It certainly includes both natural and programming languages and also all kinds of nonsense languages one might think of. Traditionally, formal language theory is concerned with the syntactic specification of a language rather than with any semantic issues. A syntactic specification of a language with finitely many sentences can be given, at least in principle, by listing the sentences. This is not possible for languages with infinitely many sentences. The main task of formal language theory is the study of finitary specifications of infinite languages.

The basic theory of computation, as well as of its various branches, such as cryptography, is inseparably connected with language theory. The input and output sets of a computational device can be viewed as languages, and—more profoundly—models of computation can be identified with classes of language specifications, in a sense to be made more precise. Thus, for instance, Turing machines can be identified with phrase-structure grammars and finite automata with regular grammars.

FINITE AUTOMATA

A finite automaton is a strictly finitary model of computation. Everything involved is of a fixed, finite size and cannot be extended during the course of computation. The other types of automata studied later have at least a potentially infinite memory. Differences between various types of automata are based mainly on how information can be accessed in the memory.

A finite automaton operates in discrete time, as do all essential models of computation. Thus, we may speak of the “next” time instant when specifying the functioning of a finite automaton.

The simplest case is the memoryless device, where, at each time instant, the output depends only on the current input. Such devices are models of combinational circuits.

In general, however, the output produced by a finite automaton depends on the current input as well as on earlier inputs. Thus, the automaton is capable (to a certain extent) of remembering its past inputs. More specifically, this means the following.

The automaton has a finite number of internal memory states. At each time instant i it is in one of these states, say qi. The state qi + 1 at the next time instant is determined by qi and by the input at given at time instant i. The output at time instant i is determined by the state qi (or by qi and ai, together).

A GENERAL MODEL OF COMPUTATION

As is true for all our models of computation, a Turing machine also operates in discrete time. At each moment of time it is in a specific internal (memory) state, the number of all possible states being finite. A read-write head scans letters written on a tape one at a time. A pair (q, a) determines a triple (q′, a′, m) where the q's are states, a's are letters, and m (“move”) assumes one of the three values l (left), r (right), or 0 (no move). This means that, after scanning the letter a in the state q, the machine goes to the state q′ writes a′ in place of a (possibly a′ = a, meaning that the tape is left unaltered), and moves the read-write head according to m.

If the read-write head is about to “fall off” the tape, that is, a left (resp. right) move is instructed when the machine is scanning the leftmost (resp. rightmost) square of the tape, then a new blank square is automatically added to the tape. This capability of indefinitely extending the external memory can be viewed as a built-in hardware feature of every Turing machine. The situation is depicted in Figure 4.1.

BACKGROUND AND CLASSICAL CRYPTOSYSTEMS

It might seem strange that a chapter on cryptography appears in a book dealing with the theory of computation, automata, and formal languages. However, in the last two chapters of this book we want to discuss some recent trends. Undoubtedly, cryptography now constitutes such a major field that it cannot be omitted, especially because its interconnections with some other areas discussed in this book are rather obvious. Basically, cryptography can be viewed as a part of formal language theory, although it must be admitted that the notions and results of traditional language theory have so far found only few applications in cryptography. Complexity theory, on the other hand, is quite essential in cryptography. For instance, a cryptosystem can be viewed as safe if the problem of cryptanalysis—that is, the problem of “breaking the code”—is intractable. In particular, the complexity of certain number-theoretic problems has turned out to be a very crucial issue in modern cryptography. And more generally, the seminal idea of modern cryptography, public key cryptosystems, would not have been possible without an understanding of the complexity of problems. On the other hand, cryptography has contributed many fruitful notions and ideas to the development of complexity theory.

PETRI NETS

The purpose of this chapter is to give an overview of some currently active topics in automata and language theory. The overview is by no means intended to be exhaustive: Some topics have been entirely omitted, and the material within the topics presented has been chosen to give only a general idea of most representative notions and results. As the title of this chapter indicates, the attention is restricted to topics in automata and language theory.

The style of presentation in this chapter is somewhat different from that used in the previous chapters. Most of the proofs are either omitted or only outlined. Sometimes notions are introduced in a not entirely rigorous manner, and results are presented in a descriptive way rather than in the form of precise mathematical statements. We begin with a discussion of Petri nets.

In a customary model for computing, the notion of a state is quite essential. This is certainly true of most of the models discussed earlier. The notion of a state introduces, at least implicitly, a specific discrete linear time scale for all considerations involved: Time instants can be identified with the current states. Such a linear time scale is not desirable in all considerations. For instance, we might want to model systems where many processors operate independently and in parallel and where some partial computations depend (perhaps in a complicated way) on the outcome of some other computations.

The basic question in the theory of computing can be formulated in any of the following ways: What is computable? For which problems can we construct effective mechanical procedures that solve every instance of the problem? Which problems possess algorithms for their solutions?

Fundamental developments in mathematical logic during the 1930s showed the existence of unsolvable problems: No algorithm can possibly exist for the solution of the problem. Thus, the existence of such an algorithm is a logical impossibility—its nonexistence has nothing to do with our ignorance. This state of affairs led to the present formulation of the basic question in the theory of computing. Previously, people always tried to construct an algorithm for every precisely formulated problem until (if ever) the correct algorithm was found. The basic question is of definite practical significance: One should not try to construct algorithms for an unsolvable problem. (There are some notorious examples of such attempts in the past.)

A model of computation is necessary for establishing unsolvability. If one wants to show that no algorithm for a specific problem exists, one must have a precise definition of an algorithm. The situation is different in establishing solvability: It suffices to exhibit some particular procedure that is effective in the intuitive sense. (We use the terms algorithm and effective procedure synonymously.

The last twenty years have witnessed most vigorous growth in areas of mathematical study connected with computers and computer science. The enormous development of computers and the resulting profound changes in scientific methodology have opened new horizons for the science of mathematics at a speed without parallel during the long history of mathematics.

The following two observations should be kept in mind when reading the present monograph. First, various developments in mathematics have directly initiated the “beginning” of computers and computer science. Second, advances in computer science have induced very vigorous developments in certain branches of mathematics. More specifically, the second of these observations refers to the growing importance of discrete mathematics—and we are now witnessing only the very beginning of the influence of discrete mathematics.

Because of reasons outlined above, mathematics plays a central role in the foundations of computer science. A number of significant research areas can be listed in this connection. It is interesting to notice that these areas also reflect the historical development of computer science.

1. The classical computability theory initiated by the work of Gödel, Tarski, Church, Post, Turing, and Kleene occupies a central role. This area is rooted in mathematical logic.

2. In the classical formal language and automata theory the central notions are those of an automaton, a grammar, and a language.

BASIC IDEAS AND AXIOMATIC THEORY

The classification of mathematical problems into decidable and undecidable ones has been discussed quite extensively in previous chapters. Indeed, from the mathematical point of view, this classification is the most fundamental one. It is also of definite practical significance in discouraging attempts to design too-general systems, such as systems for deciding the equivalence of programs or the halting of a program. There are, in fact, instances of such attempts in the past!

However, this classification is too coarse in many respects. In Chapter 4 we considered a finer classification of undecidable problems in terms of reducibilities and degrees. We shall now discuss a finer classification of decidable problems in terms of their complexity. Two problems might both be decidable and yet one might be enormously more difficult to compute, which in practice might make this problem resemble an undecidable one. For example, if instances of reasonable size of one problem take only a few seconds to compute, whereas instances of comparable size of the other problem take millions of years (even if best computers are available), it is clear that the latter problem should be considered intractable compared with the former one. Hence, having established the decidability of a particular problem, we should definitely study its complexity—that is, how difficult it is to settle specific instances of the problem.

Introduction

Having established the framework for the phased development of a system we now go on to look at the techniques that are available to you during those phases.

The purpose of this chapter is not to present all known techniques in an encyclopaedic way. Rather, it is to present sufficient information on a representative selection to allow you to make a first selection of a subset for your own project. As you read each précis, you can decide which of the techniques presented are not of interest and those that might be.

In the subsequent phase-orientated chapters each technique is presented with further detail in the context of the phase or phases where it is of use. Thus techniques applicable to, say, the System Definition Phase can be read and compared. Should you still feel that a particular technique is or may be of use, you can refer for complete information to the source material listed in the bibliography.

Similarly, all of the descriptions of the techniques in later chapters are necessarily simplifications. Remember that they are given not so that you can learn how to use the technique – for that you must turn to the authoritative references and suppliers. The purpose is solely to give you sufficient flavour of each technique for you to judge whether further evaluation could be worthwhile.

For each candidate technique you should aim to adopt, adapt or reject it.