5.4CFG = PDA

Previously, we saw that finite automata and regular expressions are equivalent in the sense that the set of languages that finite automata can recognize is equal to the set of languages that can be generated by regular expressions. These are the regular languages. It turns out that non-deterministic pushdown automata and context-free grammars are also equivalent.

The proof of this theorem is by showing that a context-free grammar can be turned into an equivalent non-deterministic pushdown automaton and vice versa.

In this section, we will give a sketch of one of the directions. Henceforth, we write PDA as short for “non-deterministic pushdown automata”.

5.4.1Example: Balanced Parentheses¶

A canonical context-free language is the language of balanced parentheses. The alphabet of the language consists of the parentheses symbols ( (called ‘open parenthesis’) and ) (called ‘close parentheses’). A string of parentheses is balanced if every open parenthesis is matched by a close parenthesis.

For example, $\epsilon$, (), (()), ()(()()) are all in the language but not (, (().

A CFG for balanced parentheses is^[1]:

Here’s the PDA for it described using the framework in High Level Framework for Automata. Note that some of the blocks use $ε$-transition to push symbols onto the stack: namely, the Start and PushRule blocks as they do not contain the Move Right statement.

Start:
  Push S
  Goto StackNotEmpty

StackNotEmpty:
  If input = 'S':
    Fork:
      Move Right
      Push 'S'
      Goto StackNotEmpty
    Fork:
      Move Right
      Pop
      Push ')'
      Goto PushRule(S)2
  If stack empty:
    Goto StackEmpty
  If input = 'End':
    Reject

PushRule(S)2:
  Push 'S'
  Goto PushRule(S)3

PushRule(S)3:
  Push '('
  Goto StackNotEmpty

StackEmpty:
  If input != 'End':
    Move Right
    Goto Invalid
  If input = 'End':
    Accept

Invalid:
  If input != 'End':
    Move Right
    Goto Invalid
  If input = 'End':
    Reject