Pushdown Automata

A pushdown automaton (or nondeterministic pushdown automaton) is a 7-tupleM = (Q, , , , q0, Z0, F), where

1)Q is a finite alphabet (the set of states),

2) is a finite alphabet ( the set of input symbols),

3) is a finite alphabet (the set of stack symbols),

4): Q({})2Q* is a function such that (q,a,Z) is finite for any qQ, a{}, and Z (the transition function),

5)q0 is a specified element of Q (the initial state),

6)Z0 is a specified element of  (the initial stack symbol), and

7)F is a subset of Q (the set of accepting states).

Input Tape x a y

Input Head

q Stack Head

Finite Control Z

Pushdown Store 

ID (Instantaneous Description) (q, ay, Z)

A PDA is nondeterministic by nature (NPDA). M is said to be deterministic (DPDA) if

i)|(q,a,Z)| 1 for any qQ, a{}, and Z, and

ii)if (q,,Z) , then (q,a,Z)= for any a.

An ID (instantaneous description) of M is an element of Q**. An ID (p,y,) means that M is currently in state p, the remaining input is y, and the content in the pushdown stack is , where the leftmost symbol of is the top symbol in the stack.

The initial ID for input x* is (q0,x,Z0).

An accepting ID is an ID of the form (f,, ) for some qＦand *, which menas that M is in an accepting state, and that the whole input has already been scanned, whereas the current stack content may bearbitrary.

Moves in M (a binary relation ├M, or simply├,on IDs)

For p,qQ, a{}, Z, ,*, we write (q,ax,Z) ├ (p,x,) if (q,a,Z) contains (p,).

├* is the reflexive transitive closure of ├.

A sequence of ID’s 1, 2, …, nis called a computation(of x) by M if i├i+1for each i(and 1=(q0,x,Z0)).

The Language accepted byM

L(M) = {x in * | (q0,x,Z0) ├* (f,,), fF, *} Acceptance by final state

N(M) = {x in * | (q0,x,Z0) ├* (q,,), qQ} Acceptance by empty stack

Examples and Exercises

1. An NPDA M=(Q,,,,q0,Z0,F)accepting D1

Q={q0,f}, ={[,]}, ={Z0,[},F={f},

(q0,[,Z0)={(q0,[Z0)}, (q0,[,[)={(q0,[[)}, (q0,],[)={(q0,)}, (q0,],Z0)={(q0,)},

(q0,,Z0)={(f,Z0)}.

Unnecessary for L(M)

M is not deterministic, since neither (q0,[,Z0)nor(q0,,Z0) are empty..

(q0, [1[2]3[4[5]6]7]9, Z0) ├(q0, [2]3[4[5]6]7]9, [1Z0) ├(q0, ]3[4[5]6]7]9, [2[1Z0)

├(q0, [4[5]6]7]9, [1Z0) ├(q0, [5]6]7]9, [4[1Z0) ├(q0,]6]7]9, [5[4[1Z0)

├(q0,]7]9, [4[1Z0) ├(q0, ]9, [1Z0) ├(q0, , Z0) ├(f, , Z0)

L(M) = {x in {[,]}* | #](y) #[(y) for any prefixy of x, and #[(x)=#](x)}.

N(M) = {x in {[,]}* | #](y) #[(y) for any prefix y of x}.

2. A DPDA for D1

(q0,[,Z0)=(q1,[Z0), (q1,[,[)=(q1,[[), (q1,],[)=(q1,), (q1,,Z0)=(q0,Z0).

q0 is the initial state and it is the unique accepting state, i.e,

M=({q0,q1},[[,]], {[,Z0],,q0,Z0,{q0}).

3. An NPDA forXXR={xxR | x in {a,b}*}

(q0,c,Z0)={(q0,cZ0)}, (q0,c,d)={(q0,cd), (q1,cd)}, (q1,c,c)={(q1,)},(q1,,Z0)=

{(q0,Z0)} for any c,d in {a,b}, where q0 is the initial state and the unique

accepting state.

M chooses this transition when it guesses that it has just reached

the center of xxR;otherwise M choosesthe otherone.

Ex. Modify M so that it accepts {x in {a,b}* | x=xR}.

Exercises

Give DPDAs or NPDAs for the following languages:

a) {anbmanbm |n,m0} b) {anbn | n0}{anb2n | n0}

c) {x in {a,b}* |#a(x)=#b(x)} d)(AnBn)*

Prove that for any NPDA M and DFAN there exists an NPDA accepting

L(M)L(N). Thus the class of CFLs is closed under intersection with

regular sets.

NPDAs = CFLs

Lemma 1. If L=L(M) for some NPDA M, then L=N(M’) for some NPDA M’. Conversely if L=N(M) for some NPDA M, then L=L(M’) for some NPDA M’.

Lemma 2. For any CFG G, there exists a NPDA M such that L(G)=N(M).

Lemma 3. For any NPDA M, there exists a CFG G such that L(G)=L(M).

THEOREM The following three statements are equivalent:

(1)L=L(M) for some NPDA M.

(2)L=N(M) for some NPDA M.

(3)L=L(G) for some CFG G, that is, L is a CFL.

Thus ℒ(NPDA)=ℒ2.

#008