ids for Finite Automata?

One might wonder why we did not introduce for finite automata a notation like the IDs we use for PDAs. Although a FA has no stack, we could use a pair (q,v]), where q is the state and w the remaining input, as the ID of a finite automaton,

While we could have done so, we would not glean any more information from reachability among IDs than we obtain from the д notation. That is, for any finite automaton, we could show that 5{q,w) - p ii and only if {q,wx) h {p,x) for all strings x. The fact that x can be anything we wish without influencing the behavior of the FA is a theorem analogous to Theorems 6.5 and 6.6.

Theorem 6.6: If P - (Q, E, Г, <5, o, o, F) is a PDA, and

(q,xv;,a)

then it is also true that {q,x,a) f {p, y,p)- □

6.1.5 Exercises for Section 6.1

Exercise 6.1.1: Suppose the PDA P = {{q,p},{0,l},{Zo,X},S,q,Zo,{p]] has the following transition fiinction:

1. S{q,0,Zo) = {{q,XZu)}.

2. 6{q,0..X){iq.XX)}.

3. e{q,l,X) = {{q,X)}.

4. 6{q,e,X) = {{p,()}.

5. S{p,e,X) = {ip,e)}.

6. S{p.l,X) = {{p,XX)}.

7. 5{p,l,Zo) = {(p,0}.

Starting from the initial ID (tf, w, Zq), show all the reachable IDs when the input w is;

* a) 01.

b) ООП,

c) 010.

6.2 The Languages of a PDA

We have assumed that a PDA accepts its input by consuming it and entering an accepting state. We call this approach acceptance by final state. There is a second approach to defining the language of a PDA that has important applications. We may also define for any PDA the language accepted by empty stack, that is, the set of strings that cause the PDA to empty its stack, starting from the initial ID.

These two methods are equivalent, in the sense that a language L has a PDA that accepts it by final state if and only if L has a PDA that accepts it by empty stack. However, for a given PDA P, the languages that P accepts by final state and by empty stack are usimlly different. We shall show in this section how to convert a PDA accepting L by final state into another PDA that accepts L by empty stack, and vice-versa.

6.2.1 Acceptance by Final State

Let P = {Q,i:,T,6,qo..Zo,F) be a PDA. Then L{P), the language accepted by p by final state, is

{xu I {qu,u),Z(,) (?,e,a)}

for some state g in F and any stack string a. That is, starting in the initial ID with w waiting on the input, P consumes w from the input and enters an accepting state. The contents of the stack at that time is irrelevant.

Example 6.7: We have claimed that the PD.A of Example 6.2 accepts the language L. the language of strings in {0,1}* that have the form uiw. Let us see why that statement is true. The proof is an if-and-only-if statement: the PD.A, P of Example 6.2 accepts string x by final state if and only if x is of the form ww.

(If) This part is easy; we have only to show the accepting computation of P. If X = ww, then observe that

(qo,ww,Zo) {qo,V!,wZo)\-{qi,iu,mZa) (</i, e, Zo) [-(2, б, Zo)

That is, one option the PD.A has is to road ui from its input and store it on its stack, in reverse. Next, it goes spontaneously to state q\ and matches on the input with the same string on its stack, and finally goes spontaneously to state q-2.

(Only-if) This part is harder. First, observe that the only way to enter accepting state у2 is to be in state and liave Zq at the top of the stack. Also, any accepting computation of P will start in state q, make one transition to q, and never return to q. Thus, it is sufficient to find the conditions on x such that {q(i,x, Zo) 1 {q\, e, Zq); these will be exactly the strings x that P accepts by final state. We shall show by induction on \x\ the slightly more general statement;

The Л in jV{P) stands for null stack, a synonym for empty stack.

If (qax.a) (tfi, е,а), then x is of the form ww.

BASIS: If a: - e, then x is of the form ww (with w -e). Thus, the conclusion is true, so the statement is true. Note we do not have to argue that the hypothesis (9o,e, ) 1 {qi,e,a) is true, although it is.

INDUCTION: Suppose x = аиа a for some n > 0. There are two moves that P can make from ID [да,х, a):

1. (qo,x,a) h {qi,x,a). Now P can only pop the stack wlien it is in state qi. P must pop the stack with every input symbol it reads, and \x\ > 0. Thus, if (qi.x.a) \- (qi,e,0), then /3 will be shorter than a and cannot be equal to a.

2. (0,aitt2 11,a) I- (9o> -2 aaia). Now the only way a sequence of moves can end in (qi,€,a) is if the last move is a pop:

{qi,an,aia) Ь (g-i.e.a)

In that case, it must be that ai = o . We also know that

{qo,a2---an,a-iQ.) {qi,a ,a\a)

By Theorem 6.6, we can remove the symbol from the end of the input, since it is not used. Thus,

((jo,a2---a i,aia) (<?;,£,ai)

Since the input for this sequence is shorter than n, we may apply the inductive hypothesis and conclude that щ--- a i is of the form yy for some y. Since x = щууа, and we know ai ~ an, we conchide that x is of the form wu)\ specifically w =а\у.

The above is the heart of the proof that the only way to accept x is for x to be equal to ivw for some w. Thus, we have the only-if part of the proof, which, with the if part proved earlier, tells us that P accepts exactly those strings in L,t,u.-r

6.2.2 Acceptance by Empty Stack

For each PDA P = (Q, £,Г,(5,чи, Zo, F), we also define

N{P) = {w\{qo,w,Zo)\ {q,,e)]

for any state q. That is, N{P) is the set of inputs w that P can consume and at the Simae time empty its stack,