Automata and Computability

The goal of this course is to understand the foundations of computation. We will ask some very basic questions, such as What does it mean for a function to be computable?Are there any noncomputable functions?How does computational power depend on programming constructs?a useful feature of the book: the exercises These questions may appear simple, but they are not. They have intrigued scientists for decades, and the subject is still far from closed.

A decision problem is a function with a one-bit output: “yes” or “no.” To specify a decision problem, one must specify the set A of possible inputs, andthe subset B ⊆ A of “yes” instances

Intuitively, a state of a system is an instantaneous description of that system, a snapshot of reality frozen in time. A state gives all relevant information necessary to determine how the system can evolve from that point on. Transitions are changes of state; they can happen spontaneously or in response to external inputs.

Here is another example of a regular set that is a little harder than the example given last time. Consider the set 4.1 $$\left\{ {x \in {{\left\{ {0,1} \right\}}^*}|x{\mkern 1mu} represents{\mkern 1mu} a{\mkern 1mu} multiple{\mkern 1mu} of{\mkern 1mu} three{\mkern 1mu} in{\mkern 1mu} binary} \right\}$$ (leading zeros permitted, ∈ represents the number 0).

Nondeterminism is an important abstraction in computer science. It refers to situations in which the next state of a computation is not uniquely determined by the current state. Nondeterminism arises in real life when there is incomplete information about the state or when there are external forces at work that can affect the course of a computation. For example, the behavior of a process in a distributed system might depend on messages from other processes that arrive at unpredictable times with unpredictable contents.

Formal Definition of Nondeterministic Finite Automata A nondeterministic finite automaton (NFA) is a five-tuple $$N = \left( {Q,\sum , \Delta ,S,F} \right),$$ where everything is the same as in a deterministic automaton, except for the following two differences.

What happens when one types rm * in UNIX? (If you don’t know, don’t try it to find out!) What if the current directory contains the files and one types rm *. dvi? What would happen if there were a file named.dvi?

Here are some interesting and important questions: How hard is it to determine whether a given string x matches a given pattern a? This is an important practical question. There are very efficient algorithms, as we will see.Is every set represented by some pattern? Answer: no. For example, the set is not represented by any pattern. We’ll prove this later.Patterns α and β are equivalent if L(α) = L(β). How do you tell whether α and β are equivalent? Sometimes it is obvious and sometimes notWhich operators are redundant? For example, we can get rid of ∈ since it is equivalent to ∼(#@) and also to φ*. We can get rid of @ since it is equivalent to #*. We can get rid of unary + since α+ is equivalent to αα*. We can get rid of #, since if Σ = {α₁, ..., α_n} then # is equivalent to the pattern {ie44-2}.

For small regular expressions, one can often see how to construct an equivalent automaton directly without going through the mechanical procedure of the previous lecture. It is therefore useful to try to simplify the expression first.

In Lecture 9, we gave a combinatorial proof that every finite automaton has an equivalent regular expression. Here is an algebraic proof that generalizes that argument. It is worth looking at because it introduces the notion of Kleene algebra and the use of matrices. We will show how to use matrices and Kleene algebra to solve systems of linear equations involving sets of strings.

A homomorphism is a map h: Σ* → Г* such that for all x, y ∈ Σ*, .

We have studied what finite automata can do; let’s see what they cannot do. The canonical example of a nonregular set (one accepted by no finite automaton) is $$B = \{ {a^n}{b^n}|n0\} = \{ \in ,ab,aabb,aaabbb,aaaabbbb,...\} $$ , the set of all strings of the form a*b* with equally many a’s and b’s.

Let’s use the pumping lemma in the form of the demon game to show that the set $$A = \{ {a^n}{b^m}|nm\} $$ is not regular. The set A is the set of strings in a*b* with no more b’s than a’s. The demon, who is betting that A is regular, picks some number k. A good response for you is to pick x = ak, y = bk, and z = ∈. Then xyz =akbk∈A and $$\left| y \right| = k$$ so far you have followed the rules. The demon must now pick u, v, w such that y=uvw and v ≠ ∈. Say the demon picks u, v, w of length j, m, n, respectively, with k= j + m + n and m > 0. No matter what the demon picks, you can take i = 2 and you win: $$xu{\upsilon ^2}\omega z = {a^k}{b^j}{b^m}{b^m}{b^n} = {a^k}{b^{j + 2m + n}} = {a^k}{b^{k + m}}$$ , which is not in A, because the number of b’s is strictly larger than the number of a’s.

By now you have probably come across several situations in which you have observed that some automaton could be simplified either by deleting states inaccessible from the start state or by collapsing states that were equivalent in some sense. For example, if you were to apply the subset construction to the NFA accepting the set of all strings containing the substring aba, you would obtain a DFA with 24 = 16 states. However, all except six of these states are inaccessible. Deleting them, you would obtain the DFA From left to right, the states of this DFA correspond to the subsets {s}, {s, t}, {s, u}, {s, t, v}, {s, u, v}, { s, v}.

Here is an algorithm for computing the collapsing relation ≈ for a given DFA M with no inaccessible states. Our algorithm will mark (unordered) pairs of states {p, q}. A pair {p, q} will be marked as soon as a reason is discovered why p and q are not equivalent.

Two deterministic finite automata $$ \begin{gathered} M = \left( {Q_M ,\sum ,\delta _M ,s_M ,F_M } \right), \hfill \\ N = \left( {Q_N ,\sum ,\delta _N ,s_N ,F_N } \right) \hfill \\ \end{gathered} $$ are said to be isomorphic (Greek for “same form”) if there is a one-to-one and onto mapping f: Q _M → Q _N such that f (s _M )=s _N f(δ _M (p,a) = δ _N (f(p, a) for all p ∈ Q _M , a ∈ Σ,andp (∈ F _M iff f(p) ∈F _N .

Let R ⊆ ∑* be a regular set. Recall from Lecture 15 that a Myhill—Nerode relation for R is an equivalence relation ∑* on Σ* satisfying the following three properties: (i)≡ is a right congruence: for any x, y ∈ Σ* and a ∈ Σ(ii)≡ refines R: for any x, y ∈ Σ*,(iii)≡ is of finite index; that is, ≡ has only finitely many equivalence classes.

With respect to minimization, the situation for nondeterministic automata is not as satisfactory as that for deterministic automata. For example, minimal NFAs are not necessarily unique up to isomorphism (Miscellaneous Exercise 60). However, part of the Myhill—Nerode theory developed in Lectures 13 through 16 does generalize to NFAs. The generalization is based on the notion of bisimulation, an important concept in the theory of concurrency [87]. In this lecture we briefly investigate this connection.

The theory of finite automata has many interesting and useful generalizations that allow more general types of inputs, such as infinite strings and finite and infinite trees. In this lecture and the next we will study one such generalization: finite automata on terms, also known as finite labeled trees. This generalization is quite natural and has a decidedly algebraic flavor. In particular, we will show that the entire Myhill—Nerode theory developed in Lectures 13 through 16 is really a consequence of basic results in universal algebra, a branch of algebra that deals with general algebraic concepts such as direct product, homomorphism, homomorphic image, and quotient algebra.

In the last lecture we generalized DFAs on strings to term automata over a signature Σ and demonstrated that automata-theoretic concepts such as “final states” and “run” were really more general algebraic concepts in disguise. In this lecture we continue to develop this correspondence, leading finally to a fuller understanding of the Myhill—Nerode theorem.

Two-way finite automata are similar to the machines we have been studying, except that they can read the input string in either direction. We think of them as having a read head, which can move left or right over the input string. Like ordinary finite automata, they have a finite set Q of states and can be either deterministic (2DFA) or nondeterministic (2NFA).

In this lecture we show that 2DFAs are no more powerful than ordinary DFAs. Here is the idea. Consider a long input string broken up in an arbitrary place into two substrings xz. How much information about x can the machine carry across the boundary from x into z? Since the machine is two-way, it can cross the boundary between x and z several times. Each time it crosses the boundary moving from right to left, that is, from z into x, it does so in some state q. When it crosses the boundary again moving from left to right (if ever), it comes out of x in some state, say p. Now if it ever goes into x in the future in state q again, it will emerge again in state p, because its future action is completely determined by its current configuration (state and head position). Moreover, the state p depends only on q and x. We will write T _x (q) = p to denote this relationship. We can keep track of all such information by means of a finite table , where Q is the set of states of the 2DFA M, and • and ⊥ are two other objects not in Q whose purpose is described below.

You may have seen something like the following used to give a formal definition of a language. This notation is sometimes called BNF for Backus—Naur form.

Intuitively, a string of parentheses is balanced if each left parenthesis has a matching right parenthesis and the matched pairs are well nested. The set PAREN of balanced strings of parentheses [ ] is the prototypical context-free language and plays a pivotal role in the theory of CFLs.

For many applications, it is often helpful to assume that CFGs are in one or another special restricted form. Two of the most useful such forms are Chomsky normal form (CNF) and Greibach normal form (GNF).

There is a pumping lemma for CFLs similar to the one for regular sets. It can be used in the same way to show that certain sets are not context-free. Here is the official version; there will also be a corresponding game with the demon that will be useful in practice.

A nondeterministic pushdown automaton (NPDA)is like a nondeterministic finite automaton, except it has a stack or pushdown store that it can use to record a potentially unbounded amount of information.

It doesn’t matter whether we take NPDAs to accept by empty stack or by final state; the two methods of acceptance are equivalent in the sense that each type of machine can simulate the other. Given an arbitrary NPDA M that accepts by final state or empty stack, we will show how to construct an equivalent NPDA M’ with a single accept state for which acceptance by empty stack and by final state coincide.

In this lecture and the next we will show that nondeterministic pushdown automata and context-free grammars are equivalent in expressive power: the languages accepted by NPDAs are exactly the context-free languages. In this lecture we will show how to convert a given CFG to an equivalent NPDA. We will do the other direction in Lecture 25.

We have shown that every CFL is accepted by some NPDA. Now we show conversely that NPDAs accept only CFLs. Thus NPDAs and CFGs are equivalent in expressive power. We will do this in two steps by showing that ievery NPDA can be simulated by an NPDA with one state; andiievery NPDA with one state has an equivalent CFG.

A deterministic pushdown automaton (DPDA) is an octuple where everything is the same as with NPDAs, except: i⊣ is a special symbol not in Σ, called the right endmarker, and iiδ is deterministic in the sense that exactly one transition applies in any given situation. This means that for any p ∈ Q, a ∈ ∪ {⊣}, and A ∈ Γ, δ contains exactly one transition of the form ((p, a, A), (q, β) or (p, ∈, A), (q, β).iiiδ is restricted so that 1 is always on the bottom of the stack. The machine may pop ⊥ off momentarily, but must push it directly back on. In other words, all transitions involving ⊥ must be of the form ((p,a,⊥), (q,β⊥)).

One of the most important applications of context-free languages and pushdown automata is in compilers. The input to a PASCAL compiler is a PASCAL program, but it is presented to the compiler as a string of ASCII characters. Before it can do anything else, the compiler has to scan this string and determine the syntactic structure of the program. This process is called parsing.

Given a CFL A and a string x ∈ Σ*, how do we tell whether x is in A? If A is a deterministic CFL and we are given a deterministic PDA for it, we can easily write a program to simulate the PDA. In fact, this is a good way to do it in practice and is done frequently in compilers; we saw an example of this in Lecture 26.

Let PAREN_n denote the language consisting of all balanced strings of parentheses of n distinct types. This language is generated by the grammar.

Here is a theorem that says a little more about the structure of CFLs. It says that for any CFL A, if we look only at the relative number of occurrences of terminal symbols in strings in A without regard to their order, then A is indistinguishable from a regular set.

In this lecture we introduce the most powerful of the automata we will study: Turing machines (TMs), named after Alan Turing, who invented them in 1936. Turing machines can compute any function normally considered computable; in fact, it is quite reasonable to define computable to mean computable by a TM.

Last time we defined deterministic one-tape Turing machines:

As mentioned, the concept of computability is remarkably robust. As evidence of this, we will present several different flavors of Turing machines that at first glance appear to be significantly more or less powerful than the basic model defined in Lecture 29 but in fact are computationally equivalent.

Now we come to a crucial observation about the power of Turing machines: there exist Turing machines that can simulate other Turing machines whose descriptions are presented as part of the input. There is nothing mysterious about this; it is the same as writing a LISP interpreter in LISP.

Here are some examples of decision problems involving Turing machines. Is it decidable whether a given Turing machine (a)has at least 481 states?(b)takes more than 481 steps on input e?(c)takes more than 481 steps on some input?(d)takes more than 481 steps on all inputs?(e)ever moves its head more than 481 tape cells away from the left endmarker on input e?(f)accepts the null string e?(g)accepts any string at all?(h)accepts every string?(i)accepts a finite set?(j)accepts a regular set?(k)accepts a CFL?(l)accepts a recursive set?(m)is equivalent to a Turing machine with a shorter description?

There are two main techniques for showing that problems are undecidable: diagonalization and reduction. We saw examples of diagonalization in Lecture 31 and reduction in Lecture 32.

Rice’s theorem says that undecidability is the rule, not the exception. It is a very powerful theorem, subsuming many undecidability results that we have seen as special cases.

In this lecture we show that a very simple problem about CFLs is undecidable, namely the problem of deciding whether a given CFG generates all strings.

In this lecture and the next we take a brief look at some of the other traditional formalisms that are computationally equivalent to Turing machines. Each one of these formalisms embodies a notion of computation in one form or another, and each can simulate the others. In addition to Turing machines, we’ll consider Post systems;type 0 grammars;μ-recursive functions (μ = “mu”, Greek for m);λ-calculus (λ = “lambda”, Greek for l);combinatory logic; andwhile programs.

The λ-calculus (λ = “lambda,” Greek for l) consists of a set of objects called λ-terms and some rules for manipulating them. It was originally designed to capture formally the notions of functional abstraction and functional application and their interaction.

We can relate the primitive and n-recursive functions of Gödel to more modern concepts. Consider a simple programming language with variables Var = {x, y...} ranging over N containing the following constructs: isimple assignmentsiisequential compositioniiiconditionalivfor loopvwhile loop

We know that virtually all interesting questions about Turing machines—whether a given TM halts on a given input, whether a given TM accepts a finite set, and so on—are undecidable. But are all these questions equally hard? For example, suppose by some magic we were given the power to decide the halting problem. Could we somehow use that power to decide if a given TM accepts a finite set? In other words, relative to the halting problem, is finiteness decidable?

In 1931 Kurt Gödel [50, 51] proved a momentous theorem with far-reaching philosophical consequences: he showed that no reasonable formal proof system for number theory can prove all true sentences. This result set the logic community on its ear and left Hilbert’s formalist program in shambles. This result is widely regarded as one of the greatest intellectual achievements of twentieth-century mathematics.

Gödel proved the incompleteness theorem by constructing, for any reasonable proof system, a sentence of number theory _w that asserts its own unprovability in that system: .

Gödel proved the incompleteness theorem by constructing, for any reasonable proof system, a sentence of number theory that asserts its own unprovability. Here is the essence of Gödel’s construction.