Page 1 1 Pushdown Automata (PDA) Page 2 1 Pushdown Automata (PDA) 2 PDA - the automata for CFLs n What is? n FA to Reg Lang, PDA is to CFL n PDA == [ e -NFA + “a stack” ] n Why a stack? e-NFA A stack filled with “stack symbols” Input string Accept/reject Page 3 1 Pushdown Automata (PDA) 2 PDA - the automata for CFLs n What is? n FA to Reg Lang, PDA is to CFL n PDA == [ e -NFA + “a stack” ] n Why a stack? e-NFA A stack filled with “stack symbols” Input string Accept/reject 3 Pushdown Automata - Definition n A PDA P := ( Q, ?, G, d,q 0 ,Z 0 ,F ): n Q: states of the e-NFA n ?: input alphabet n G : stack symbols n d: transition function n q 0 : start state n Z 0 : Initial stack top symbol n F: Final/accepting states Page 4 1 Pushdown Automata (PDA) 2 PDA - the automata for CFLs n What is? n FA to Reg Lang, PDA is to CFL n PDA == [ e -NFA + “a stack” ] n Why a stack? e-NFA A stack filled with “stack symbols” Input string Accept/reject 3 Pushdown Automata - Definition n A PDA P := ( Q, ?, G, d,q 0 ,Z 0 ,F ): n Q: states of the e-NFA n ?: input alphabet n G : stack symbols n d: transition function n q 0 : start state n Z 0 : Initial stack top symbol n F: Final/accepting states d : The Transition Function d(q,a,X) = {(p,Y), …} 1. state transition from q to p 2. a is the next input symbol 3. X is the current stack top symbol 4. Y is the replacement for X; it is in G* (a string of stack symbols) i. Set Y = e for: Pop(X) ii. If Y=X: stack top is unchanged iii. If Y=Z 1 Z 2 …Z k : X is popped and is replaced by Y in reverse order (i.e., Z 1 will be the new stack top) 4 old state Stack top input symb. new state(s) new Stack top(s) d : Q x ? x G => Q x G q a X p Y Y = ? Action i) Y=e Pop(X) ii) Y=X Pop(X) Push(X) iii) Y=Z 1 Z 2 ..Z k Pop(X) Push(Z k ) Push(Z k-1 ) … Push(Z 2 ) Push(Z 1 ) Page 5 1 Pushdown Automata (PDA) 2 PDA - the automata for CFLs n What is? n FA to Reg Lang, PDA is to CFL n PDA == [ e -NFA + “a stack” ] n Why a stack? e-NFA A stack filled with “stack symbols” Input string Accept/reject 3 Pushdown Automata - Definition n A PDA P := ( Q, ?, G, d,q 0 ,Z 0 ,F ): n Q: states of the e-NFA n ?: input alphabet n G : stack symbols n d: transition function n q 0 : start state n Z 0 : Initial stack top symbol n F: Final/accepting states d : The Transition Function d(q,a,X) = {(p,Y), …} 1. state transition from q to p 2. a is the next input symbol 3. X is the current stack top symbol 4. Y is the replacement for X; it is in G* (a string of stack symbols) i. Set Y = e for: Pop(X) ii. If Y=X: stack top is unchanged iii. If Y=Z 1 Z 2 …Z k : X is popped and is replaced by Y in reverse order (i.e., Z 1 will be the new stack top) 4 old state Stack top input symb. new state(s) new Stack top(s) d : Q x ? x G => Q x G q a X p Y Y = ? Action i) Y=e Pop(X) ii) Y=X Pop(X) Push(X) iii) Y=Z 1 Z 2 ..Z k Pop(X) Push(Z k ) Push(Z k-1 ) … Push(Z 2 ) Push(Z 1 ) 5 Example Let L wwr = {ww R | w is in (0+1)*} n CFG for L wwr : S==> 0S0 | 1S1 | e n PDA for L wwr : n P := ( Q, ?, G, d,q 0 ,Z 0 ,F) = ( {q 0 , q 1 , q 2 },{0,1},{0,1,Z 0 }, d,q 0 ,Z 0 ,{q 2 })Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|43 docs|39 tests