Pushdown Automata (PDA)

Back to Automata Theory
Arjit Sharma
01 Min

Finite automata are great for flat, linear patterns like checking if a string ends with 01. But they can’t handle nested structures like -

pushdown-automata

  • Matching parentheses: ( ( ) ( ) )
  • Balanced aⁿbⁿ: aabb, aaabbb
  • Simple arithmetic like a + (b * c)

To recognize such patterns, the machine needs memory to keep track of context, and that’s where Pushdown Automata comes in.

What Is a Pushdown Automaton?

pda

A Pushdown Automaton (PDA) is like a DFA but with an extra component: a stack.

This allows the PDA to Push symbols onto the stack , Pop symbols and Peek at the top symbol. It makes decisions based on the current state, input symbol, and top of the stack.

How a Pushdown Automata Works ?

Imagine trying to match balanced parentheses:

( ( ) )

balancing-parnethesis-detailed

  1. When it sees a ( → it pushes it onto the stack
  2. When it sees a ) → it pops a ( from the stack
  3. If the stack is empty at the end, and the input is consumed, the input is accepted

This memory (the stack) is what makes the PDA capable of recognizing context-free languages.

Example

push-down-automata

Next →