Theory of Computation

Course note based on Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, 2nd edition, authored by Martin Davis, Ron Sigal, and Elaine J. Weyuker.

course note prepared by TyngRuey Chuang Week 8, Spring 2010

About This Course Note It is prepared for the course Theory of Computation taught at the National Taiwan University in Spring 2010. It follows very closely the book Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, 2nd edition, by Martin Davis, Ron Sigal, and Elaine J. Weyuker. Morgan Kaufmann Publishers. ISBN: 0-12-206382-1. It is available from Tyng-Ruey Chuangs web site: http://www.iis.sinica.edu.tw/~trc/ and released under a Creative Commons Attribution-ShareAlike 3.0 Taiwan license: http://creativecommons.org/licenses/by-sa/3.0/tw/

1
1.1

Preliminaries (1)
Alphabets and Strings (1.3)

Alphabets and Strings An alphabet is a nite nonempty set A of symbols. An n-tuple of symbols of A is called a word or a string on A. In stead of writing a word as (a1 , a2 , . . . , an ) we write simply a1 a2 . . . an . 1

 If u = a1 a2 . . . an , then we say that n is the length of u and we write |u| = n. We allow a unique null word, written 0, of length 0. The set of all words on the alphabet A is written as A . Any subset of A is called a language on A or a language with alphabet A. Alphabets and Strings, More If u, v A , then we write uv for the word obtained by placing the string v after the string u. For example, if A = {a, b, c}, u = bab, and v = caa, then uv = babcaa. Where no confusion can result, we write uv instead of uv. It is obvious that, for all u, u0 = 0u = u, and that, for all u, v, w, u(vw) = (uv)w. If u is a string, and n N, n > 0, we write u[n] = uu . . . u
n

We also write n

[0]

= 0.

If u A , we write uR for u written backward; i.e., if u = a1 a2 . . . an , then uR = an . . . a2 a1 . Clearly, 0R = 0, and (uv)R = v R uR for u, v A .

2
2.1

Regular Languages (9)

Finite Automata (9.1)

The Concept of Finite Automata A nite automaton has a nite number of internal states that control its behavior. The states function as memory in the sense that the current state keeps track of the progress of the computation. The automaton begins by reading the leftmost symbol on a nite input tape, in a specic state called the initial state. If at a given time, the automaton is in a state qi , reading a given symbol sj on the input tape, the machine moves one square to the right on the tape and enters a state qk . The current state plus the symbol being read from the tape completely determine the automatons next state. When all symbols have been read, the automaton either stops at an accepting state or a non-accepting state. 2

Denition of Finite Automaton Denition. A nite automaton M consists of an alphabet A = {s1 , s2 , . . . , sn }, a set of states Q = {q1 , q2 , . . . , qm }, a transition function that maps each pair (qi , sj ), 1 i m, 1 j n, into a state qk , a set F Q of nal or accepting states, and an initial state q1 Q. We can represent the transition function using a state versus symbol table. What Does This Automaton Do? The nite automaton M has alphabet A = {a, b}, the set of states Q = {q1 , q2 , q3 , q4 }, q1 the transition function dened by the following table: q2 q3 q4 the set F = {q3 } as the accepting states, and q1 as the initial state. What Does Automaton M Do? For strings aabbb, baba, aaba, and abbb, the nite automaton M accepts aabbb as M terminates in state q3 , which is an accepting state; rejects baba as M terminates in state q4 , which is not an accepting state; rejects aaba as M terminates in state q4 , which is not an accepting state; accepts abbb as M terminates in state q3 , which is an accepting state. a q2 q2 q4 q4 b q4 q3 q3 q4

Function (qi , u) If qi is any state of M and u A , we shall write (qi , u) for the state which M will enter if it begins in state qi at the left end of the string u and moves across u until the entire string has been processed. (q1 , aabbb) = q3 , (q1 , baba) = q4 , (q1 , aaba) = q4 , (q1 , abbb) = q3 . Denition of Function (qi , u) A formal denition of function (qi , u) is by the following recursion: (qi , 0) = qi , (qi , usj ) = ( (qi , u), sj ). Obviously, (qi , sj ) = (qi , sj ). We say that M accepts a word u provided that (q1 , u) F . M rejects a word u means that (q1 , u) Q F .

Regular Languages The language accepted by a nite automaton M , written L(M ), is the set of all u A accepted by M : L(M ) = {u A | (q1 , u) F }. A language is called regular if there exists a nite automaton that accepts it. What Language Does This Automaton Accept? The nite automaton M has the alphabet A = {a, b}, the set of states Q = {q1 , q2 , q3 , q4 }, q1 the transition function dened by the following table: q2 q3 q4 the set F = {q3 } as the accepting states, and q1 as the initial state. a q2 q2 q4 q4 b q4 q3 q3 q4

What Language Does Automaton M Accept? The language it accepts is {a[n] b[m] | n, m > 0}. As the above language is accepted by a nite automaton, we say it is a regular language. State Transition Diagram Another way to represent the transition function is to draw a graph in which each state is represented by a vertex. The fact that (qi , sj ) = qk is represented by drawing an arrow from vertex qi to vertex qk and labeling it sj . The diagram thus obtained is called the state transition diagram for the given automaton. See Fig. 1.1 in the textbook (p. 240) for the state transition diagram for the nite automaton we just showed in the previous two slides.

2.2

Nondeterministic Finite Automata (9.2)

Nondeterministic Finite Automata We modify the denition of a nite automaton to permit transitions at each stage to either zero, one, or more than one states. That is, we make the the values of the transition function be sets of states, i.e., sets of elements of Q (rather than members of Q). The devices so obtained are called nondeterministic nite automata (ndfa). Sometimes the ordinary nite automata are then called deterministic nite automata (dfa). Denition of Nondeterministic Finite Automaton Denition. A nondeterministic nite automaton M consists of an alphabet A = {s1 , s2 , . . . , sn }, a set of states Q = {q1 , q2 , . . . , qm }, a transition function that maps each pair (qi , sj ), 1 i m, 1 j n, into a subset of states Qk Q, a set F Q of nal or accepting states, and an initial state q1 Q. 5

Denition of Function (qi , u) The formal denition of function (qi , u) is now by: (qi , 0) = {qi }, (qi , usj ) =
q (qi ,u)

(q, sj ).

A ndfa M with initial state q1 accepts u A if (q1 , u) F = . That is, at least one of the states at which M ultimately arrives belongs to F . L(M ), the language accepted by M , is the set of all strings accepted by M . What Does This Automaton Do? The nondeterministic nite automaton M has the alphabet A = {a, b}, the set of states Q = {q1 , q2 , q3 , q4 }, q1 the transition function dened by the following table: q2 q3 q4 the set F = {q4 } as the accepting states, and q1 as the initial state. For the state transition diagram of M , see Fig. 2.1 in the textbook (p. 243). What Strings Does Automaton M Accept? M accepts a string on the alphabet {a, b} just in case at least one of the symbols has two successive occurrence in the string. Why? Viewing dfa as ndfa Strictly speaking, a dfa is not just a special kind of ndfa. This is because for a dfa, (q, s) is a state, where for a ndfa it is a set of states. But it is natural to identify a dfa M with transition function , with the closely related ndfa M whose transition function is given by (q, s) = {(q, s)}, and which has the same nal states as M . It is obviously that L(M ) = L(M ). 6 a b {q1 , q2 } {q1 , q3 } {q4 } {q4 } {q4 } {q4 }

dfa is as expressive as ndfa Theorem 2.1. A language is accepted by a ndfa if and only if it is regular. Equivalently, a language is accepted by an ndfa if and only if it is accepted by a dfa. Proof Outline. As we have seen, a language accepted by a dfa is also accepted by an ndfa. Conversely, let L = L(M ), where M is an ndfa with transition function , set of states Q = {q1 , . . . , qm }, and set of nal states F . We will construct a dfa M such that L(M ) = L(M ) = L. The will be sets of states of M . idea of the construction is that the individual states of M Constructing M The dfa M consists of the same alphabet A = {s1 , s2 , . . . , sn } of the ndfa M , the set of states Q = {Q1 , Q2 , . . . , Q2m } which consists of all the 2m subsets of the set of states of the ndfa M , the transition function dened by (Qi , s) =
qQi

(q, s),

the set F of nal states given by F = {Qi | Qi F = }, the initial state Q1 = {q1 }, where q1 is the initial state of M .

Lemma 1. Let R Q. Then (

Qi R

Qi , s) =
Qi R

(Qi , s).

Proof. Let

Qi R

Qi = Q. Then by denition, (Q, s) =

qQ

(q, s) (q, s)
Qi R qQi

= =
Qi R

(Qi , s). 2

Lemma 2. For any string u, (Qi , u) =

qQi

(q, u).

Proof. The proof is by induction on |u|. If |u| = 0, then u = 0 and (Qi , 0) = Qi =

qQi

{q} =
qQi

(q, 0)

Proof. (Continued) If |u| = l + 1 and the result is known for |u| = l, we write u = vs, where |v| = l, and observe that, using Lemma 1 and the induction hypothesis, (Qi , u) = (Qi , vs) = ( (Qi , v), s) = ( (q, v), s)
qQi

=
qQi

( (q, v), s) (r, s)

qQi r (q,v)

= =
qQi

(q, vs) =
qQi

(q, u). 2

Lemma 3. L(M ) = L(M ). Proof. u L(M ) if and only if (Q1 , u) F . But, by Lemma 2, (Q1 , u) = ({q1 }, u) = (q1 , u). Hence, u L(M ) if and only if (q1 , u) F if and only if (q1 , u) F = if and only if u L(M ) 2 Note that Theorem 2.1 is an immediate consequence of Lemma 3.

2.3

Additional Examples (9.3)

Additional Examples Construct a dfa that accepts the language: {(11)[n] | n 0} The vendor machine example. (Fig. 3.2 in textbook, p. 248) Construct an ndfa that accepts all and only strings which end in bab or aaba. Construct an ndfa that accepts the language: {a[n1 ] b[m1 ] . . . a[nk ] b[mk ] | n1 , m1 , . . . , nk , mk > 0}.

2.4

Closure Properties (9.4)

Closure properties To show that the class of regular languages is closed under a large number of operations. To use deterministic or nondeterministic nite automata whenever necessary, as the two classes of automata are equivalent in expressiveness (Theorem 2.1). Nonrestarting dfa Denition. A dfa is called nonrestarting if there is no pair q, s for which (q, s) = q1 where q1 is the initial state. Theorem 4.1. There is an algorithm that will transform a given dfa M into a nonrestarting dfa M such that L(M ) = L(M ). Constructing a nonrestarting dfa from a dfa Proof of Theorem 4.1. From a dfa M , we can construct an equivalent nonrestarting dfa by adding a new returning initial state qn+1 , and by redening the transition function M accordingly. That is, for M , we dene the set of states Q = Q {qn+1 } the transition function by (q, s) = (q, s) if q Q and (q, s) = q1 qn+1 if q Q and (q, s) = q1

(qn+1 , s) = (q1 , s) F if q1 F F {qn+1 } if q1 F To see that L(M ) = L(M ) we observe that M follows the same transitions as M except enters qn+1 . whenever M reenters q1 , M 2 the set of nal states F = 9

 LL Theorem 4.2. If L and L are regular languages, then so is L L. Proof. Let M and M be nonrestarting dfas that accept L and L respectively. We now construct a ndfa M by merging M and M but with a new initial state q1 . That is, we dene M by the set of states Q = Q Q {1 } {q1 , q1 } q the transition function by {(q, s)} if q Q {q1 } {(q, s)} if q Q {1 } q q q (1 , s) = {(q1 , s)} {(1 , s)} (q, s) = the set of nal states F = F F {1 } {q1 , q1 } if q1 F or q1 F q F F otherwise

Note that once a rst transition has been selected, M is locked into either M or M . Hence L(M ) = L L. 2 A L Theorem 4.3. Let L A be a regular language. Then A L is regular. Proof. Let be exactly like M except that it accepts precisely M be a dfa that accept L. Let dfa M when M rejects. That is, the set of accepting states of M is Q F . Then L(M ) = A L. 2 L1 L2 Theorem 4.4. If L1 and L2 are regular languages, then so is L1 L2 . L1 , L2 A . Then, by the De Morgan identity, we have L1 L2 = A ((A L1 ) (A L2 )) Theorem 4.2 and 4.3 then give the result. 2

Proof. Let

and {0} Theorem 4.5. and {0} are regular languages. Proof. is clearly the language accepted by any automaton whose set of accepting states is empty. For {0}, we can construct a two-state dfa such that F = {q1 } and (q1 , a) = (q2 , a) = q2 for every symbol a A, the alphabet. Clearly this dfa accepts {0}. 2

10

Every nite subset of A is regular Theorem 4.5. Let u A . Then {u} is a regular language. Proof. Theorem 4.4 proves the case for u = 0. For the other case, let u = a1 a2 . . . al where l 1, a1 , a2 , . . . al A. We now construct a (l + 1)state ndfa M with initial state q1 , accepting state ql+1 , and the transition function given by (qi , ai ) = {qi+1 }, i = 1, . . . , l (qi , a) = for a A {ai }, Clearly L(M ) = {u}. 2

i = 1, . . . , l 2

Corollary 4.7. Every nite subset of A is regular.

11