Intro to Theory of Computation
Trist1111
PDAs.pptx1
Pushdown Automata PDAs
2
Pushdown Automaton -- PDA
Input String
Stack
States
3
Initial Stack Symbol
Stack
Stack
bottom
special symbol
stack
head
top
4
The States
Input
symbol
Pop
symbol
Push
symbol
Or equivalently
5
top
input
stack
Replace
6
Push
top
input
stack
7
Pop
top
input
stack
8
No Change
top
input
stack
9
Pop
top
input
stack
A Possible Transition
empty
10
input
A Bad Transition
The automaton Halts in state
and Rejects the input string
Empty stack
HALT
11
input
A Bad Transition
The automaton Halts in state
and Rejects the input string
Empty stack
HALT
12
No transition is allowed to be followed
When the stack is empty
Empty stack
13
Pop
top
input
stack
A Good Transition
14
Non-Determinism
These are allowed transitions in a
Non-deterministic PDA (NPDA)
15
NPDA: Non-Deterministic PDA
Example:
16
Execution Example:
Input
current
state
Time 0