Chapter 05. Nondeterministic Automata

Models of Language Recognition: Automata

1

5. Nondeterministic Automata The computational machine models that we studied in Chapter 4 are deterministic in the sense that the next move (i.e., the effect) of the automata is uniquely determined by the current state and the input (i.e., the cause), including the stack-top for the case of DPDA. Thus, the state transition graphs of DFA's, for example, have at most one outgoing edge for each input symbol. For a state p and an input symbol a of a DFA, the transition function δ (p, a) gives no more than one next state, for example, δ (p, a) = q. Deterministic machines follow our intuition that for a given cause the effect is uniquely determined. In this chapter we will study the computational models whose transitions do not go along with our deterministic intuition. They are allowed to take more than one action in a move. More specifically, for the same state and an input symbol (or a stack symbol for the pushdown automata), we allow the automata to take more than one transition simultaneously. For example, a nondeterministic finite state automaton (NFA) can have a nondeterministic transition, like δ (p, a) = {q, r), i.e., reading symbol a in state p, the machine enters two different states q and r simultaneously. Likewise, nondeterministic pushdown automata (NPDA) can have δ (p, a, A) = {(q, BA), (r, ε )}, i.e., they can push and pop simultaneously, possibly entering different states. Nondeterministic linear bounded automata (NLBA) and nondeterministic Turing machines (NTM) can have nondeterministic transitions, like δ (p, a) = {(q, b, R), (q, b, L)}. Nondeterministic automata involve a conceptual model that cannot be implemented with current technology. However, we will see that once we understand the underlying concept of these nondeterministic automata, we can use them as a powerful tool for the design and analysis of deterministic machines. Now, we will study these nondeterministic models beginning with NFA, and then NPDA, NLBA, and NTM, in this order.

2

Nondeterministic Automata 5.1 NFA (Nondeterministic Finite Automata) 126 Definition and examples 5.2 NPDA (Nondeterministic Pushdown Automata) 132 Definition and examples 5.3 NTM (Nondeterministic Turing Machines) and NLBA (Nondeterministic Linear Bounded Automata) 139 5.4 Nondeterministic Computing 140 Nondeterministic computing Example 5.5 NFA and ε -transitions 145 ε -transitions in an FA Eliminating ε -transitions Rumination 154 Exercises 156

Today’s Quote

Break Time

I pay very little regard to what any young person says on the subject of marriage. If they profess a disinclination for it, I only set it down that they have not seen the right person. - Jane Austen – Love is the difficult realization that something other than oneself is real. - Iris Murdoch -

3

Nondeterministic Automata

5.1 Nondeterministic Finite Automata (NFA) Figure (a) below shows the state transition graph of an NFA that has nondeterministic transitions in states q0 and q2, i.e., δ (q0, b) = {q0 , q1},

δ (q2, a) = {q0 , q1}.

For the input string bba, this NFA takes multiple sequences of transitions simultaneously as shown in figure (b), which we shall call state transition profile for the given input. Notice that a root-to-leaf path corresponds to a full sequence of transition for the input. (In the figure, X denotes the dead state.) q0 b b a,b q1 q1 b b q0 b b q0

a

a a

q2

(a) An NFA M.

a q1

q0

q1

a

X

q2

(b) State transition profile of M for bba. 4

Nondeterministic Automata

NFA

The accepting condition of an NFA is defined as follows. An NFA accepts the input if and only if the transition profile has an accepting leaf node (i.e., state). (All the other non-accepting leaf nodes are ignored.) In other words the input string is accepted by an NFA if and only if there is a sequence of transitions finally entering an accepting state. According to this definition, the input string bba is accepted by M. a,b

q1

b q0

a q2

(a) An NFA M

q0

b q0 b

a

a a

b

q1

q0

q1

b q1 a

b X

q2

(b) Transition profile of M for bba. 5

Nondeterministic Automata

NFA

Figure (b) below shows the transition profile for the input string bbb. This profile has no root-to-leaf path ending in an accepting state. Hence, by definition the input is rejected by M. a,b

q1

b q0

b

b q0 b

a

a

b a

q2

(a) An NFA M

q0

q0

q0

b q1

b q1

q1

b X

b X

(b) Transition profile of M for bbb.

6

Nondeterministic Automata

NFA

Formally, an NFA M is defined with the quintuple as follows. M = (Q, Σ , δ , q0, F ), where all the elements are the same as the ones for DFA’s, except for the state transition function δ , which is defined as follows. δ

: Q × Σ → 2Q

That is, the automaton, reading the input symbol in a state, takes transitions simultaneously to every state in a subset of Q. (Recall that 2Q denotes the set of subsets of Q.) For a string x, let δ (p, x) denote the set of states reachable from state p after reading the input string x. Then the language L(M) is defined as follows. L(M) = {x| x ∈ Σ *, δ (q0, x) = S, and S ∩ F ≠ ∅} Notice that S ∩ F ≠ ∅ implies that the transition profile for the string x has an accepting leaf node, i.e., there is a sequence of transitions ending in an accepting state. 7

NFA

Nondeterministic Automata

Designing an NFA Example 1. Construct an NFA which recognizes L = {xaa | x ∈ {a, b}*}. This language is the set of strings in {a, b}* ending with aa. The figure below shows an NFA which recognizes L. This NFA, reading b, stays in state 1, while reading a, takes nondeterministic transitions to state 1 and 2. Because of this nondeterministic transition, it is guaranteed that if the input string contains aa, the machine enters the accepting state 3 by reading the second a. Hence, if the second a is the last symbol of the input string, then by the definition, it is accepted. Notice that together with this accepting sequence of transitions, there are other nonaccepting sequences of transitions ending in a non-accepting state that we ignore by the definition.

a, b

a 1

a 2

3

8

NFA

Nondeterministic Automata

Example 2. Construct an NFA to recognize the following language. L = {xaaybbz | x, y, z ∈ {a, b}*} This language is the set of strings in {a, b}*, each having aa followed by bb, not necessarily consecutive. We use the same idea that we used for Example 1. We connect two transition graphs; one for recognizing xaa followed by the other for ybb, and then let the automaton read off the part z in an accepting state.

b a, b

a

a

b a, b

a, b

Nondeterministic transitions do not give any additional power for recognizing a language, i.e., NFA’s and DFA’s recognize the same languages. We will learn why in Chapter 8. Actually we will study how to transform an NFA to a DFA which recognizes the same language. 9

Nondeterministic Automata

5.2 Nondeterministic Pushdown Automata (NPDA) Since PDA’s have the stack, they can do more works in a move than NFA’s. Therefore they can take more diverse nondeterministic moves at a time. For example, in a move they can enter different states simultaneously as well as change the stack top with different contents, as the following examples show. δ (p, a, Z) = {(q, aZ), (r, aZ)} δ (s, b, Z) = {(t, ε ), (t, bZ), (t, cZ)} The power of nondeterministic transitions of an NPDA is best shown by the following simple example.

10

Nondeterministic Automata

NPDA

Example 1. Construct an NPDA to recognize the following language. L = {aibjck| i, j, k > 0, and i = j or j = k }. This language is the union of the following two languages. L1 = {aibjck| i, j, k > 0, i = j } L2 = {aibjck| i, j, k > 0, j = k } We first construct DPDA’s M1 and M2 , respectively, recognizing L1 and L2. (a, a/ aa)

(b, a/ε )

(b, a/ε )

(a, Z0/aZ0) start

(c, Z0/ Z0) (a) M1

(c, Z0/ Z0) (b, b/bb)

start

(ε , Z0/ Z0)

(a, Z0/Z0) (a, Z0/Z0)

(b, Z0/bZ0)

(c, b/ ε )

(c, b/ ε )

(b) M2 11

Nondeterministic Automata

NPDA L = {aibjck| i, j, k > 0, and i = j or j = k }.

It is proven that no DPDA can recognize L. However, as the following figure shows, we can simply construct an NPDA, which can recognize L, by combining the two DPDA’s M1 and M2 with a nondeterministic transition.

(a, a/ aa) (a, Z0/aZ0) start

1

(b, a/ε ) (b, a/ε ) (c, Z0/ Z0)

2 (c, Z0/ Z0) (b, b/bb)

(a, Z0/Z0)

3

(a, Z0/Z0)

(ε , Z0/ Z0)

(b, Z0/bZ0) (c, b/ ε )(c, b/ ε )

12

NPDA

Nondeterministic Automata

A simple idea for identifying whether an automaton is deterministic or not is to check if the δ function of the automaton is one-to-one, i.e., the function gives no more than one value. However this idea is not sufficient for NPDA. As we mentioned in Chapter 4 studying DPDA, if a PDA has two transitions from a state, one reading the input and the other not reading, with the same stack-top symbol, then the PDA is an NPDA. For example, if the transition function δ of a PDA has two transitions shown below, then it is an NPDA. In state p, with B on the stack-top, the machine is taking two contradictory transitions; reading and not reading the input. δ (p, a, B) = (q, AB)

δ (p, ε , B ) = (q, AB)

Let’s see how we can utilize such nondeterministic transitions to design an NPDA that can recognize a language, but no DPDA can recognize it.

13

Nondeterministic Automata

NPDA

Example 2. Construct an NPDA which recognizes the following language. L = {xxR | x ∈ {a, b}+ } This is a typical context-free language for which it is impossible to design a DPDA to recognize (see Appendix D for a proof). If there were a marker, say #, at the center of every string as shown in the language L’ below, it would be trivial to construct a DPDA. This DPDA, reading the part x (till it reads #), pushes all the symbols into the stack, and then pops the stack-top for every matching symbol read from the second half (i.e., xR) until it sees the stack empty. L’ = {x#xR | x ∈ {a, b}+ } (Y, X/YX ) ( ε , Z0/Z0 )

(X, Z0/X Z0 ) start

(#, X/X )

In the figure, X, Y ∈ {a, b}. (Y, X/YX ) is a shorthand for (a, a/aa), (a, b/ab), (b, a/ba), (b, b/bb).

(X, X/ε ) 14

Nondeterministic Automata

NPDA

Now, we will design an NPDA which uses the power of nondeterministic transitions to recognize L (see the figure below). The NPDA, reading the input symbols and pushing them onto the stack in state q1, guesses that from the next input symbol, the part xR will begin, and takes nondeterministic transitions to a popping state (q2 in the figure) while remaining in state q1. In the popping state the machine keeps popping the stack-top for each matching input symbol. Notice that in the same state q1 with the same stack-top X, the NPDA takes reading and not-reading transitions simultaneously, the one entering q1 and the other entering q2.

L = {xxR | x ∈ {a, b}+ } (Y, X/YX ) (X, Z0/X Z0 ) start

q0

( ε , Z0/Z0 )

q1 (ε , X/X )

q2

q3

In the figure X, Y ∈ {a, b}. (Y, X/YX ) is a shorthand for (a, a/aa), (a, b/ab), ( b, a/ba), (b, b/bb). (X, X/ε ) is a shorthand for (a, a /ε ), (b, b /ε )

(X, X/ε ) 15

NPDA

Nondeterministic Automata

Palindrome is a word or phrase that reads the same forwards and backwards (with case insensitive and spaces ignored). For example, “Madam” and “sums are not set as a test on Erasmus” are palindromes. The language L = {xxR | x ∈ {a, b}+ } is a language of palindromes. Every language of palindromes (with case sensitive and spaces excluded) is a context-free language. In Chapter 15 we will learn that the every context-free language can be recognized by an NPDA. However, there are context-free languages that cannot be recognized by any DPDA. The language L above is an example. It is a challenging problem to prove that for a given context-language, whether or not it can be recognized by a DPDA. Appendix D shows a proof that there is no DPDA that can recognize L. Actual Signs

Break Time

In a non-smoking area: “If we see you smoking, we will assume you are on fire and take appropriate action.” In the front yard of a funeral home: “Drive carefully. We’ll wait.” On a maternity room door: “Push, Push, Push.” On an optometrist’s office: “If you don’t see what you’re looking for, you’ve come to the right place.” On a butcher’s window: “Let me meat your needs.” - Anonymous -

16

Nondeterministic Automata

5.3 Nondeterministic Turing Machines (NTM) and Nondeterministic Linear Bounded Automata (NLBA) The figure below shows a part of the state transition graph of an NTM (or an NLBA). Notice the various nondeterministic transitions in states 1, 2 and 4. In a move, the machine enters more than one state (from state 1 in the figure), write different symbols (in state 2) and/or move in different directions (in state 4). Though it would be tedious, we can show that given a NTM M, we can build a DTM M’ which simulates M by systematically keeping track of every nondeterministic transition of M. NTM’s and DTM’s are computationally equivalent, i.e., they accept the same class of type 0 languages. (a, b, R) (a, b, R) 1

2 (a, c, R) 3

(a, b, R)

4

(a, b, R), (a, b, L) 5 17

Nondeterministic Automata

5.4 Nondeterministic Computing

Sometimes it may help to think that whenever a nondeterministic move occurs, the original machine makes a copy for each instance of the move. For example, suppose that an NFA M, in state p, reads symbol a and takes a nondeterministic move to q and r, i.e., δ (p, a ) = {q, r}. Then, conceptually it is clear to think that two copies of the machine, one in state q and the other in r, are created and proceed independently. The same concept applies to the other nondeterministic automata and algorithms. a b A M

N I

p

δ (p, a) = {q, r)

M1

a b

a b

q

r M2 18

Nondeterministic Automata

Nondeterministic Computing

For a finite set S, define a function nondet_choose (S), which returns every element in S simultaneously. The figure below illustrates conceptually how a program works with a nondeterministic function returning multiple values simultaneously. Executing the function nondet_choose, for each of the function values returned, a copy of the process (i.e., the current instance of the executable program) is generated (i.e., forked). Then, all the process copies proceed independently, with the function value assigned. . A

N I

. x = nondet_choose (q, r) ; .

.

.

.

.

.

x = nondet_choose (q, r) ;

x = nondet_choose (q, r) ;

{ compute with x = q }

{ compute with x = r }

.

. 19

Nondeterministic Computing

Nondeterministic Automata

Using the function nondet_choose we can quickly search the solution space of a problem by nondeterministically forking (i.e., making a copy of the program and let them proceed independently). If there is any sequence of computation that gives the solution, we say the program solves the problem, ignoring the unsuccessful computations. Otherwise, we say the program fails to find it. There are many, so-called, NP-hard problems for which no polynomial-time algorithm (i.e., which gives an answer in O(nk) time, for some constant k ) is available. The sum-of-subset problem, which is defined as follows, is one of them. Given a set S of N integers and an integer M, is there a subset S’ ⊆ S such that the sum of elements in S’ is equal to M? For example let S = {8, 21, 13, 20, 7, 11, 5} and M = 34. Since 8 + 21 + 5 = 34, the answer is “yes.”

20

Nondeterministic Computing

Nondeterministic Automata

Here is a nondeterministic algorithm which solves the sum-of-subset problem in time proportional to the problem size (i.e., in time linear to the number of given integers), assuming that the nondeterministic function takes a constant time. // S is an integer array of size n. This algorithm tests if there is a // subset of the numbers in S whose sum is equal to M. 1. Nondet-Sum-of-Subset (int S[ ], int n, int M) { 2. int i, sum = 0; 3. boolean selected; 4. for ( i = 0; i < n; i++) { 5. selected = nondet_choose(true, false); 6. if (selected) sum += S[i]; } 7. if (sum = = M) return “yes”; 8. else return “no”; }

21

Nondeterministic Automata

Nondeterministic Computing

Notice that whenever the statement selected = nondet_choose(true, false) is executed, two processes are created, one with selected = true, and the other with selected = false. Let 1 and 0, respectively, denote true and false, and suppose |S| = 3. Then the initial process will be forked down to three levels, summing up all the selected (= true) elements by the statement in line 6. The statement in line 7 makes the final decision. Notice that there are 8 leaf nodes (processes) in the decision tree. Each leaf node of the tree corresponds to one of the 8 possible subsets of the set of size 3. If there is a subset whose summation is equal to the given number M, one of the processes at the leaf nodes will output “yes.” The figure shows a successful selection sequence 011 and the leaf node which will output “yes” for the given set S. 0

i=0

0

1

0

2

0 000

1 001

1 0

S

1 0

2

34 7 12

M = 19

1

0 1

1

1

0

010 011 100 101 110

1

1: true 0: false 111 22

Nondeterministic Automata

5.5 ε -transitions in an FA Consider a part of a state transition graph of an FA shown in figure (a) below. In state q1, if the input is a, the automaton remains at state q1, and if the input is b, it enters state q2. Now, we assume that while the automaton does not read the input, it remains in the current state. To denote such idling transition to the current state lets add a self-loop labeled by ε to every state as shown in figure (b). Clearly, such modification does not affect the computational capability of an FA. ε

a

a q1

b (a)

q2

q1 ε

b

q2

(b)

23

Nondeterministic Automata

ε -transitions

Now, we define a “spontaneous” transition between two different states of an FA. For example, δ (p, ε ) = q denotes a spontaneous transition from state p to q without reading the input. We shall use the label ε on the state transition graph to denote such spontaneous transitions (also called ε -transitions) as shown in figure (c) below. In this figure, if we take into account of the self-loop labeled with ε that we have introduced for the case of no input, we see that this machine has nondeterministic transitions on input ε . That is, δ (q1, ε ) = {q1, q2}. So, if an FA has an ε transition between two different states, it is an NFA. (As usual we shall not explicitly show the self-loop labeled with ε . Only the ε -transitions between two different states will be shown.)

ε

a

a q1

b (a)

q2

q1 ε

b (b)

q2

ε

a q1

ε

q2

ε (c)

24

Nondeterministic Automata

Eliminating ε -transitions from an FA An NFA with ε-transitions are very convenient model for designing a DFA, which can be implemented in the real application, or solving other problems concerning regular languages. However, the ε-transitions in an NFA need to be eliminated before converting the NFA to a DFA. It is possible to remove all the ε-transitions, if any, from an NFA without changing the language of the automaton. We will shortly learn how. Before we introduce a method for eliminating ε -transitions from an NFA, we need to extend the transition function δ as follows. For a subset A of the set of states Q of an NFA (i.e., A ⊆ Q) and an input string x, let δ (A, x) denote the set of states reachable from each state in A reading the string x. For example, in the following FA, we get δ ({1, 3}, ab) = {1, 2, 3}. 1 start

a a, b

2

b

a

3 b

4

a

25

Nondeterministic Automata

Eliminating ε -transitions

Example 1. Eliminate the ε -transition from the NFA shown below without affecting the language recognized by the automaton. This example would be enough to understand the basic idea for eliminating ε transitions from an NFA. For the method we need the following property of the regular expressions involved with the null character ε , where t is an input symbol. ε = ε ε = ε *, t = ε t = tε = ε tε = ε *tε *. We will also use the property that for a subset A ⊆ Q and two input strings x and y, δ (A, xy) = δ (δ (A, x), y). Let M be the given NFA and M ' be the FA that we get by eliminating the ε -transitions from M. b a start

q0

ε

q2

For each state qi and for each input symbol t ∈ {a, b}, we compute the set of states S that can be reachable by reading t, i.e., δ (qi, ε *tε * ) = S. (Notice that instead of t, we use ε *tε *, because M has ε -transitions.) We let this S be the states reachable from qi in M' by reading t, i.e., δ '(qi, t) = δ (qi, ε *tε * ) = S. 26

Nondeterministic Automata

Eliminating ε -transitions

The figure below shows in detail how we build the transition function δ ' of M' with δ of M to eliminate the ε -transitions from state q0. (Recall that on each state there is a self-loop labeled with ε . b

a start

q0

ε

(a) M

a q1

start

a, b

q0

q1

A N I

(b) building M'

δ '(q0, a) = δ (q0, ε *aε * ) = δ (δ ( q0, ε * ), aε * ) = δ ({q0, q1}, aε * ) = δ ( δ ( {q0, q1}, a), ε * ) = δ ( {q0}, ε δ '(q0, b) = δ (q0, ε *bε * ) = δ (δ ( q0, ε

*

*

) = { q0, q1 }

), bε

*

)=

δ ({q0, q1}, bε * ) = δ ( δ ( {q0, q1}, b), ε * ) = δ ( {q1}, ε * ) = { q1 } 27

Nondeterministic Automata

Eliminating ε -transitions

This figure shows the part for eliminating ε -transitions from state q1 to construct δ '. b b a a b a a, b a, b ε q q1 q q 1 q1 0 0 q0 start start start (a) M

(b) Building M'

δ '(q1, a) = δ (q1, ε *aε

*

(c) Final M'

) = δ (δ ( q1, ε * ), aε * ) = δ ({q1}, aε * ) =

A N I

δ ( δ ({q1}, a), ε * ) = δ ( {}, ε * ) = {} = ∅ δ '(q1, b) = δ (q1, ε *bε * ) = δ (δ ( q1, ε * ), bε * ) = δ ({q1}, bε * ) = δ ( δ ( {q1}, b), ε * ) = δ ( {q1}, ε * ) = { q1 } Finally, if an accepting state is reachable by a sequence of ε -transitions (i.e., ε is in the language of M), we let the start state (q0) be an accepting state as shown in figure (c) above. 28

Nondeterministic Automata

Eliminating ε -transitions

Example 2. Eliminate the ε -transitions from the following NFA. a start

q0

ε

c

b ε

q1

q2

A N I

(a) M Computing δ ' for the state q0 and input symbol a. δ '(q0, a) = δ (q0, ε *aε * ) = δ (δ ( q0, ε * ), aε * ) = δ ({ q0, q1, q2 }, aε * ) = δ ( δ ( qa0, q1, q2}, a), ε * ) = δ ( q0, ε * ) = { q0, q1, q2 }. start

q0

a

q1

q2

a (b) M′ 29

Nondeterministic Automata

Eliminating ε -transitions

a start q0

ε

c

b q1

ε

q2

(a) M Computing δ ' for the state q0, and input symbol b and c. δ '(q0, b) = δ (q0, ε *bε * ) = {q1, q2 } δ '(q0, c) = δ (q0, ε *cε * ) ={ q2 } a start

q0 a, b

q1

q2

a, b, c (b) M′ 30

Nondeterministic Automata

Eliminating ε -transitions

Computing δ ' for the states q1 and q2 , and input symbols a, b, and c. δ '(q1, a) = Ø,

δ '(q1, b) = { q1, q2 },

δ '(q1, c) = { q2 },

δ '(q2, a) = Ø,

δ '(q2, b) = Ø,

δ '(q2, c) = { q2 }.

Finally, since the accepting state q2 is reachable by ε-transitions from the start state, we change the start state into an accepting state to get M′ as shown in figure (b). a start

q0

ε

a

c

b q1 (a) M

ε

q2

start

c

b q0

a,b

q1

b,c

q2

a,b,c (b) M′

31

Nondeterministic Automata

Rumination (1): Nondeterministic automata • The only difference between DFA’s and NFA’s is in the definitions of δ , as shown below. DFA δ

: Q × Σ →Q

NFA δ

: Q × Σ → 2Q

In other words, NFA’s take a transition to one or more states (i.e., a subset of Q), while DFA’s take transition to no more than one state. Hence, we can view a DFA as a special NFA, every transition of which goes to at most one state. • It is not easy to identify the language accepted by a DFA directly if the state transition graph of the automaton is not simple. It is more difficult to identify the language accepted by an NFA because for a given input string, there are multiple number of transition paths, some leading to an accepting state, while others not. In Chapter 7, we will learn a systematic way to transform the state transition graph of an FA (either DFA or NFA) to a regular expression which expresses the language recognized by the FA. • Since NFA’s are allowed to take multiple transitions simultaneously, they seem to be more powerful than DFA’s. In particular, we may raise the following question. Is there an NFA language that cannot be recognizable by any DFA? In Chapter 8 we will learn a method of transforming an NFA to a DFA that recognizes the same language. This implies that for FA’s, nondeterminism does not give any additional power for the language recognition. We may raise the same question for the PDA’s, the TM’s and the LBA’s. For PDA’s, the nondeterminism gives additional power (see Appendix D for the proof). We will see a couple of examples. However, for TM’s it doesn’t, and it is an open problem for LBA’s. • We will see that, once we get used to the nondeterminism, it is easier to design an NFA than DFA. We will also see that NFA is a powerful tool for solving many problems concerning regular languages and related models.

32

Rumination: Nondeterministic automata

Nondeterministic Automata

• With nondeterministic automata, we can search the solution space of a problem by tracing diverse routes simultaneously, like in a parallel computer. But they are different from the parallel computers. While a parallel computer, out of the parallel search, generates the final result for the user, a nondeterministic automaton does not “announce” the final result. The user must make the final decision out of the many possible results. Nondeterministic automata cannot say “Yes, the input is accepted.” or “No, it is rejected.” Such final decisions are up to the user. • We learned that the stack operation mode restricted to either popping or pushing exactly one symbol in a move (see the rumination section at the end of Chapter 4). We can apply the same restriction to NPDA’s without affecting their capacity for language recognition. • Nondeterministic automata are different from the probabilistic machine, where a move takes place according to a given probabilistic rule. For example, in an NFA, δ (p, a) = {q, r} implies that in a state p, reading a symbol a, the machine certainly enters state q and r simultaneously. There is no coin-tossing. • From now on by TM, LBA, PDA and FA we denote those automata either deterministic or nondeterministic.

Ask God

Break Time

A person asked God, “What surprises you most about mankind?” And God answered: “That they lose their health to make money and then lose their money to restore their health. That by thinking anxiously about the future, they forget the present, such that they live neither for the present nor the future. That they live as if they will never die, and they die as if they had never lived ….” - Marty -

33

Exercises 5.1 For each of the strings given below, (i) show the state transition profile (the tree) of the FA shown below, and (ii) based on the profile, check whether the string is accepted by the automaton or not. a (a) aaabaa (b) aabaa a a

start

a

a

b

a 5.2 What is the language recognized by the NFA above? (i) Describe the language informally. Your answer should be clear. (ii) Express the language with a regular expression. 5.3 (a) Construct the state transition graph of an NFA which recognizes {aaxaa | x ∈{a, b, c}+ }. Your graph should have no more than 6 transition edges. (Do not count the implicit edges going to the dead state.) (b) Construct a DFA which recognizes the language given in part (a) . 5.4 For each of the following languages, construct a PDA (either NPDA or DPDA, whichever possible) which recognizes the language, and briefly explain how your PDA recognizes the language. For your PDA, it is enough to show the state transition graph. (a) L1 = {xyz | x, y, z ∈ {a, b}+, and y = zR }

(b) L2 = {xyz | x, y, z ∈ {a, b}+, and x = yR }

34

5.5 Given a directed graph G and two nodes s and t in G, the Hamiltonian path from s to t is a path that starts at node s and ends at node t visiting all the other nodes exactly once. For example, for the graph below and two nodes s = 4 and t = 7, a Hamiltonian path is 4 → 2 → 1 → 8 → 9 → 10 → 6 → 5 → 3 → 7. Given an arbitrary directed graph G and two node ids s and t, write a nondeterministic algorithm that checks if G has a Hamiltonian path from s to t. Your algorithm should take no more than a polynomial time, i.e., in time O(nk), for some constant k. (This is a challenging problem. Review the nondeterministic algorithm to solve the sum-of-subset problem that we studied in Section 5.4.)

2

s

1

7

t

4 3

8

10 5 6

9

35

5.6 Using the technique for eliminating ε -transitions from an NFA presented in Section 5.6, construct an NFA which recognizes the language of the following NFA with no ε -transitions. You should also show the procedure that you took to get your answer. b

a b

a,b

2

b

1

ε

4 a

start ε

5

3 a,b

36