Pushdown Automata

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) −

  1. Q: Finite number of states
  2. ∑: Input alphabet
  3. S: Stack
  4. δ: Transition function: Q × (∑ ∪ {ε}) × S × Q × S*
  5. q0: Initial state (q0 ∈ Q)
  6. I: Initial stack top symbol (I ∈ S)
  7. F: Final state

PDA = FSM + Stack

Where, FSM for finite state machine.

Components of PDA are,

  1. Input tape
  2. Control unit
  3. Stack