Pushdown Automata (()PDA)

2y ago
7 Views
2 Downloads
266.11 KB
37 Pages
Last View : 17d ago
Last Download : 2m ago
Upload by : Adele Mcdaniel
Transcription

Pushdown Automata (PDA)()Reading: Chapter 61

PDA - the automata for CFLs What is? FA to Reg Lang,Lang PDA is to CFLPDA [ -NFA “a stack” ]Wh a stack?Whyt k?Inputstring -NFAAccept/rejectA stack filled with “stack symbols”2

Pushdown Automata Definition A PDA P : ( Q, , , δ,q0,Z0,F ): Q: : :δ:q0:Z0:F:states of the -NFAinput alphabetstack symbolstransition functionstart stateInitial stack top ssymbolmbolFinal/accepting states3

old stateinput symb. Stack topnew state(s) new Stack top(s)δ : Q x x Q x δ : The Transition Functionδ(q,a,X) {(p,Y), }1.state transition from q to p2.a is the next input symbol3.X is the current stack top symbol4.Y is the replacement for X;it is in * (a string of stacksymbols)i.Set Y for: Pop(X)ii.If Y X: stack top isunchangediii.If Y Z1Z2 Zk: X is poppedand is replaced by Y inreverse order (i.e., Z1 will bethe new stack top)qaXYpY ?Actioni)Y Pop(X)ii)Y XPop(X)Push(X)iii)Y ZYZ1Z2.ZZkPop(X)Push(Zk)Push(Zk-1) Push(Z2)Push(Z1)4

ExampleLet Lwwr {wwR w is in (0 1)*} CFG for Lwwr :S 0S0 1S1 PDA for Lwwr : P : ( Q, , , δ,q0,Z0,F ) ( {q0, q1, q2},{0,1},{0,1,Z0},δ,q0,Z0,{q2})5

Initial state of the PDA:PDA for Lwwr1.2.3.4.5.6.δ(q0,0, Z0) {(q0,0Z0)}δ(q0,1, Z0) {(q0,1Z0)}δ(q0,0,0 0) {(q0) {(q0,00)}00)}δ(q0,0, 1) {(q0,01)}δ(q0,1, 0) {(q0,10)}δ(q0,1, 1) {(q0,11)}StackkSttopZ0q0First symbol push on stackGrow the stack by pushingnew symbols on top of old((w-part)t)δ(q0, , 0) {(q1, 0)}δ(q0, , 1) {(q1, 1)}δ(q0, , Z0)) {(q{(q1, Z0)}Switch to popping mode, nondeterministically(boundary between w and wR)11.δ(q1,0, 0) {(q1, )}δ(q1,1, 1) {(q1, )}Shrink the stack by popping matchingsymbolsy(w( R-part)p )12.δ(q1, , Z0) {(q2, Z0)}Enter acceptance state7.8.99.10.6

PDA as a state diagramδ(qi,a, X) {(qj,Y)}CurrentstateNextinputsymbolCurrent StackstackToptopReplacement(w/ string Y)a, X / YqiqjNextstate7

PDA for Lwwr: Transition Diagram {0, 1} {Z0, 0, 1}Q {q0,qq1,qq2}Grow stack0, Z0/0Z01, Z0/1Z00, 0/000, 1/011, 0/101, 1/11 , Z0/Z0q0Pop stack formatching symbols0, 0/ 1, 1/ , Z0/Z0 , 0/0 , 1/1q1 , Z0/Z0q2G to acceptanceGoSwitch topopping modeThis would be a non-deterministic PDA8

Examplep 2: languageg g ofbalanced paranthesisPop stack formatching symbolsGrow stack(, Z0 / ( Z0(, ( / ( ( , Z0 / Z0q0 { (, ) } {Z0, ( }Q {q0,qq1,qq2}), ( / ), ( / q1 , Z0 / Z0Switch topopping mode(, ( / ( ((, Z0 / ( Z0 , Z0 / Z0q2Go to acceptance (byG(b fifinall state))when you see the stack bottom symboTo allow adjacentblocks of nested paranthesis9

Example 2: language of balancedparanthesis (another design) { (, ) } {Z0, ( }Q {q0,qq1}(,Z0 / ( Z0(,( / ( (), ( / start ,Z0/ Z0q0 ,Z0/ Z0q110

PDA’s InstantaneousDescription (ID)A PDA has a configuration at any given instance:(q,w,y) q - current statew - remainder of the input (i.e., unconsumed part)y - current stack contents as a string from top to bottomoff stackt kIf δ(q,a, X) {(p, A)} is a transition, then the following are also true: (q, a, X ) --- (p, ,A) (q,( aw, XB ) --- (p,w,AB)() --- sign is called a “turnstile notation” and representsone move ---* sign represents a sequence of moves11

How does the PDA for Lwwrwork on input “1111”?All moves made by the non-deterministic PDA(q0,1111,Z0)(q0,111,1Z0)(q0,11,11Z11 11Z0)(q0,1,111Z0)(q1,1111,Z0)(q1,111,1Z111 1Z0)Path dies Path diesdies (q1,11,11Z0)(q1,1,111Z0)(q1,1,1Z0)Acceptance byfinal state:( 1, ,1111Z(q1111Z0)(q1, ,11Z 11Z0)(q1, ,Z Z0)Path dies Path dies emptyt inputitANDfinal state(q0, ,1111Z0)(q2, ,Z0)12

Principles about IDs Theorem 1: If for a PDA,(q, x, A) ---* (p, y, B), then for any stringw * andd *, * it iis alsol ttrue ththat:t (q, x w, A ) ---* (p, y w, B )Theorem 2: If for a PDA,(q, x w,, A)) ---* (p, y w,, B),), then it is also truethat: (q, x, A) ---* (p, y, B)13

There are two types of PDAs that one can design:those that accept by final state or by empty stackAcceptance by PDAs that accept by final state: For a PDA P, the language accepted by P,ddenotedt dbby L(P) byb finalfi l state,t t is:iChecklist: {w (q0,w,Z0) ---* (q, , A) }, s.t., q F- input exhausted?- in a final state?PDAs that accept by empty stack: For a PDA P, the language accepted by P,denoted by N(P) by empty stack, is: {{w (q0,,w,Z, 0) ---* (q, ,, )) }, for anyy q QQ.Checklist:Q) Does a PDA that accepts by empty stackneed any final state specified in the design? - input exhausted?- is the stack empty? 14

Example:p L of balancedparenthesisPDA that accepts by final statePF:start Z0/ Z0 ,Zq0((,ZZ0 / ( Z0(, ( / ( (), ( / ,Z0 / PN:(,Z0 / ( Z0(,( / ( (), ( / ,Z0/ Z0An equivalent PDA thataccepts by empty stackstartq1 Z0/ Z0 ,Zq0How will these two PDAs work on the input: ( ( ( ) ) ( ) ) ( )15

PDA for Lwwr: Proof ofcorrectness Theorem: The PDA for Lwwr accepts a string xby final state if and only if x is of the formwwR.Proof: (if-part)(ifpart) If the string is of the form wwR then thereexists a sequence of IDs that leads to a final state:(q0,wwR,Z0) ---* (q0,wR,wZ0) ---* (q1,wR,wZ0) ---*(q1, ,Z Z0) -- * (q2, ,Z Z0)(only-if part) Proof by induction on x 16

PDAs accepting by final state and emptystack are equivalent PF PDA accepting by final state PN PDA accepting by empty stack PF (QF, , , δF,q0,Z0,F)PN (QN, , , δN,q0,Z0)ThTheorem: (PN PF) For every PN, there exists a PF s.t. L(PF) L(PN) (PF PN) For every PF, there exists a PN s.t. L(PF) L(PN)17

How to convert an empty stack PDA into a final state PDA?PN PF construction Whenever PN’s stack becomes empty, make PF go toa final state without consuming any addition symbolTo detect empty stack in PN: PF pushes a new stacksymbol X0 (not in of PN) initially before simultatingPNPN:PF:Newstart , X0 / X0 , X0/ X0 , X0/Z0X0p0q0 PF (QN U {p0,pf}, , P N U {X0}, δF, p0, X0, {pf}) , X0/ , X0/ X0 , X0/ X0pfX018

Example: Matching parenthesis “(” “)”PN:( {q0}, {(,)}, {Z0,Z1}, δN, q0, Z0 )Pf:( {p0,q0 ,pf}, {(,)}, {X0,Z0,Z1}, δf, p0, X0 , pf)δN :δN(q0,(,Z0) { (q0,Z1Z0) }δN(q0,(,Z( Z1) { (q0, Z1Z1) }δf:δf(p0, ,X0) { (q0,Z0) }δf(q0,(,Z( Z0) { (q0,ZZ1 Z0) }δf(q0,(,Z1) { (q0, Z1Z1) }δf(q0,),Z1) { (q0, ) }δf(q0, ,Z0) { (q0, ) }δf(p0, ,X0) { (pf, X0 ) }δN(q0,),Z1) { (q0, ) }δN(q0, ,Z0) { (q0, ) }(,Z0 /Z1Z0(,Z1 /Z1Z1),Z1 / ,Z0 / start(,Z0/Z1Z0(,Z1/Z1Z1),Z1/ ,ZZ0/ startq0Accept by empty stackp0 ,X /Z X000q0 ,X / X0Accept by final state0pf19

How to convert an final state PDA into an empty stack PDA?PF PN construction Main idea: Whenever PF reaches a final state, just make an -transition into anew end state, clear out the stack and acceptDanger: What if PF design is such that it clears the stack midwaywithout entering a final state? to address this,, add a new start symbolyX0 ((not in of PF)PN (Q U {p0,pe}, , U {X0}, δN, p0, X0)PN:Newstart , X0/Z0X0p0q0 , any/ , any/ , any/ pe , any/ PF20

Equivalence of PDAs andCFGs21

CFGs PDAs CFLsPDA byfinal state PDA byempty stack?CFG22

This is same as: “implementing a CFG using a PDA”Converting CFG to PDAMain idea: The PDA simulates the leftmost derivation on a givenwPDA((acceptanceby emptystack)acceptrejectOUTPPUTINPUUTw, and upon consuming it fully it either arrives at acceptance (byempty stack) or nonnon-acceptance.acceptanceimplementsCFG23

This is same as: “implementing a CFG using a PDA”Converting a CFG into a PDAMain idea: The PDA simulates the leftmost derivation on a given w,and upon consuming it fully it either arrives at acceptance (byemptyp y stack)) or non-acceptance.pSteps:1.2.3.Push the right hand side of the production onto the stack,with leftmost symbol at the stack topIf stack top is the leftmost variable, then replace it by all itsproductions (each possible substitution will represent adistinct path taken by the nonnon-deterministicdeterministic PDA)If stack top has a terminal symbol, and if it matches with thenext symbol in the input string, then pop itSStateiis iinconsequentiali l ((onlyl one state iis needed)d d)24

Formal construction of PDANote: Initial stack symbol (S)from CFGsame as the start variablei thinthe grammar Before:Given: G (V,T,P,S)Output: PN ({q}({q}, TT, V U TT, δ,δ q,q S)δ: A Before:a δ(q ,A)δ(q,A) { (q(q, ) “AA ” P} δ(q,a,a) { (q, ) } After:a a pop For all a T, add the followingtransition(s) in the PDA:After: For allll A V , addFdd ththe ffollowingll itransition(s) in the PDA:25

Example: CFG to PDA G ( {S,A}, {0,1}, P, S)P: 1,1 / 0,0 / ,A / 01 ,A / A1 ,A / 0A1 S/ ,S ,S / ASS AS A 0A1 A1 01 ,S / SPDA ({q},({ } {0,1},{0 1} {0{0,1,A,S},1 A S} δ,δ q, S)δ: qδ(q, , S) { (qδ(q(q, AS)AS), (q(q, )}δ(q, , A) { (q,0A1), (q,A1), (q,01) }δ(q, 0, 0) { (q, ) }δ(q, 1, 1) { (q, ) } How will this new PDA work?Lets simulate string 001126

Simulatingg stringg 0011 on thenew PDA Leftmost deriv.:1,111/ 0,0 / ,A / 01 ,A / A1 ,A / 0A1 ,S, / ,S / ASPDA (δ):δ(q, , S) { (q, AS), (q, )}δ(q, , A) { (q,0A1), (q,A1), (q,01) }δ(q, 0, 0) { (q, ) }δ(q, 1, 1) { (q, ) } ,S / SStack moves (shows only the successful path):SAS0A1SA1S011S0S AS 0A1S 0011SS AS 0A1S 0011S 0011q11S1SS011 Accept byempty stack 001127

Proof of correctness for CFG PDAconstructionClaim: A string is accepted by G iff it isaccepted (by empty stack) by the PDAProof: (only-if part) Prove by induction on the number of derivation steps(if part) If (q,( wx, S) - * (q,x,B)(B) thenth S *lm wBB28

Converting a PDA into a CFGMain idea: Reverse engineer theproductions from transitionsIf δ(q,a,Z) (p, Y1Y2Y3 Yk): 1.2.3. Action: Create a ggrammar variable called“[qZp]” which includes the followingproduction: State is changed from q to p;Terminal a is consumed;Stack top symbol Z is popped and replaced with asequence of k variables.[qZp] a[pY1q1] [q1Y2q2] [q2Y3q3] ] [qk-1Ykqk]Proof discussion (in the book)29

Example: Bracket matching To avoid confusion, we will use b “(“ and e “)”PN:( {q0}, {b,e}, {Z0,Z1}, δ, q0, Z0 )1.2.δ(q0,b,Z0) { (q0,Z1Z0) }δ(q0,b,Z1) { (q0,Z1Z1) }3.4.δ(q0,e,Z1) { (q0, ) }δ(q(q0, ,,Z0) { (q0, ) }0.11.2.3.S [q0Z0q0][q0Z0q0] b [q0Z1q0] [q0Z0q0][q0Z1q0] b [q0Z1q0] [q0Z1q0][q0Z1q0] e4.[q0Z0q0] Let A [q0Z0q0]Let B [q0Z1q0]If you were to directly write a CFG:S b S e S 0.1.2.3.4.S AA b B AB b B BB e Simplifying,0.1.S b B S B b B B eA 30

Two ways to build a CFGBuild a PDAConstructCFG from PDADerive CFG directlySimilarly Two ways to build a PDAConstructDerive a CFGPDA ffrom CFGDesign a PDA directly(indirect)(direct)(indirect)(direct)31

Deterministic PDAs32

This PDA for Lwwr is non-deterministicGrow stack0, Z0/0Z01, Z0/1Z00, 0/000, 1/011, 0/101, 1/11q0Why does it haveto be nondeterministic?Pop stack formatching symbols0, 0/ 1,, 1/ , Z0/Z0 , 0/0 , 1/1Switch topopping modeq1 , Z0/Z0q2AAcceptsbby fifinall stateTo removeguessing,impose the userto insert c in themiddle33

Example shows that: Nondeterministic PDAs D-PDAsD PDA for Lwcwr {wcwR c is someD-PDAspecial symbol not in w}Note:Grow stackPop stack formatching symbols0, Z0/0Z01, Z0/1Z00, 0/000, 1/011, 0/101, 1/11q0 all transitions havebecome deterministic0, 0/ 1, 1/ c, Z0/Z0c, 0/0c, 1/1Switch topopping modeq1 , Z0/Z0q2Accepts bAbyfinal state34

Deterministic PDA: Definition A PDA is deterministic if and only if:11.δ(q,a,X)δ(qa X) has at most one member for anya U { } If δ(q,a,X) is non-empty for some a ,then δ(qδ(q, ,X) X) must be emptyempty.35

PDA vs DPDA vs RegularglanguagesLwcwrRegular languagesLwwrD-PDAnon-deterministic PDA36

SummaryPDAs for CFLs and CFGs Non-deterministicDeterministicPDA acceptance types 1.2.By final stateBy empty stackPDA IDs, Transition diagramEquivalence of CFG and PDA CFG PDA constructionPDA CFG construction37

Main idea: The PDA simulates the leftmost derivation on a given w, and upon consuming it fully it either arrives at acceptance (by emppyty stack) or non-acceptance. Steps: 1. Push the right hand side of the production onto the stack, .File Size: 266KB

Related Documents:

Pushdown Automata A pushdown automaton (PDA) is a finite automaton equipped with a stack-based memory. Each transition is based on the current input symbol and the top of the stack, optionally pops the top of the stack, and optionally pushes new symbols onto the stack. Initially, the stack holds a s

Pushdown Automata (PDA) If the input symbol is a and the top stack symbol is x then q1 to q2, pop x, push y, advance read head q2 a, x y q1 If a ℇ do not advance read head If x

4. From a CFG to an equivalent PDA ¾ Given a CFG G , we can construct a PDA P such that N( P ) L( G ). ¾ The PDA will simulate leftmost derivations of G. ¾ Algorithm to construct a PDA for a CFG o Input: a CFG G (V, T, P, S). o Output: a PDA P such that N( P )

Regular Expressions (RE) Context free langauges o Context free grammars o Pushdown automata q Definition of PDA q Computation PDA q Design of PDA q PDA and CFG q DPDA vs NPDA o Non-context free languages q Limitations of CFLs q Pumping lemma for CFL q Closure properties for CFL Ø Goals:

Finite automata and pushdown automata are two classes of the simplest mathematical models of computation. The present Chapter is a systematic exposition of automata theory based on quantum logic. We introduce the no-tions of orthomodular lattice-valued (quantum) nite and pushdown automa-ton. The classes of languages accepted by them are de ned.

Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata

Switching and automata theory Language theory and formal semantics Operating Systems Background to Distributed Computing: . Finite automata; Pushdown automata; Linear-bounded automata. PODC 2008, Toronto, Canada, August 20, 2008 Evolution of Distributed Computing Theory. Outline

PDA Estimating Guidelines Introduction to PDA Facility Considerations The PDA Facility Considerations document is intended to complement the Preliminary Damage Assessment (PDA) and for use in collecting sufficient information to estimate the type, quantity, and cost of eligible damage