A Pushdown automata (PDA) works similar as DFA.
A DFA can remember a finite amount of information, but a PDA can remember an infinite amount of information.
A PDA can be formally described as a 7-tuple (Q, ∑, S, δ, q0, I, F) −
- Q: Finite number of states
- ∑: Input alphabet
- S: Stack
- δ: Transition function: Q × (∑ ∪ {ε}) × S × Q × S*
- q0: Initial state (q0 ∈ Q)
- I: Initial stack top symbol (I ∈ S)
- F: Final state
PDA = FSM + Stack
Where, FSM for finite state machine.
Components of PDA are,
- Input tape
- Control unit
- Stack