NANJING UNIVERSITY Pushdown Automata Definition Moves of the PDA Languages of the PDA Deterministic PDA's .1
Definition Moves of the PDA Languages of the PDA Deterministic PDA’s Pushdown Automata 1
效绵鼎 Pushdown Automata The PDA is an automaton equivalent to the CFG in language-defining power. ■ Only the nondeterministic PDA defines all the CFL's. ■ But the deterministic version models parsers. Most programming languages have deterministic PDA's. 2
Pushdown Automata ◼ The PDA is an automaton equivalent to the CFG in language-defining power. ◼ Only the nondeterministic PDA defines all the CFL’s. ◼ But the deterministic version models parsers. Most programming languages have deterministic PDA’s. 2
效绵鼎 Intuition:PDa Think of an E-NFA with the additional power that it can manipulate a stack. Its moves are determined by: The current state(of its“NFA”), 2. The current input symbol (or E),and 3. The current symbol on top of its stack. 3
Intuition: PDA ◼ Think of an ε-NFA with the additional power that it can manipulate a stack. ◼ Its moves are determined by: 1. The current state (of its “NFA”), 2. The current input symbol (or ε), and 3. The current symbol on top of its stack. 3
赖绵县 Picture of a PDa Next input symbol 0111 Input State X Top of Stack Y Z Stack 4
Picture of a PDA 4 q 0 1 1 1 X Y Z State Stack Top of Stack Input Next input symbol
效绵鼎 Intuition:PDA-(2) Being nondeterministic,the PDA can have a choice of next moves. In each choice,the PDA can: 1.Change state,and also 2.Replace the top symbol on the stack by a sequence of zero or more symbols. u Zero symbols=“pop.” Many symbols=sequence of“pushes.” .5
Intuition: PDA – (2) ◼ Being nondeterministic, the PDA can have a choice of next moves. ◼ In each choice, the PDA can: 1. Change state, and also 2. Replace the top symbol on the stack by a sequence of zero or more symbols. u Zero symbols = “ pop.” u Many symbols = sequence of “pushes.” 5