Equivalence Between PDA and CFGs

Pushdown Automata (PDA) and Context-Free Grammars (CFGs) are equivalent in their expressive power. This means that for every PDA, there exists a CFG that generates the same language, and for every CFG, there exists a PDA that recognizes the same language. This equivalence establishes the theoretical foundation for context-free languages (CFLs).

From CFG to PDA

A PDA can be constructed to recognize the language generated by a given CFG. The PDA simulates the derivation of strings in the CFG by using its stack to keep track of non-terminals and their replacements.

Steps to Convert CFG to PDA

  1. Start State: Initialize the stack with the start symbol of the CFG.
  2. Transitions for Non-Terminals: For each production A → α, create a transition that replaces A on the stack with α.
  3. Transitions for Terminals: For each terminal symbol a, create a transition that matches a from the input and pops it from the stack.
  4. Accept State: The PDA accepts if the input is fully consumed and the stack is empty.

Example: Convert the CFG:

</>
Copy
S → aSb | ε

Equivalent PDA:

</>
Copy
States: {q₀, q₁}
Start State: q₀
Stack Symbols: {S, a, b, Z₀} (Z₀ is the initial stack symbol)
Transitions:
  δ(q₀, ε, Z₀) = {(q₀, SZ₀)}   // Push S onto the stack
  δ(q₀, ε, S) = {(q₀, aSb)}    // Replace S with aSb
  δ(q₀, 'a', a) = {(q₀, ε)}    // Match 'a' and pop 'a' from stack
  δ(q₀, 'b', b) = {(q₀, ε)}    // Match 'b' and pop 'b' from stack
  δ(q₀, ε, Z₀) = {(q₁, Z₀)}   // Accept when stack returns to Z₀

The PDA pushes the start symbol S onto the stack, applies productions to expand it, and matches terminals with the input to verify acceptance.

From PDA to CFG

A CFG can be constructed to generate the language recognized by a given PDA. The grammar uses non-terminals to represent the state and stack behavior of the PDA.

Steps to Convert PDA to CFG

  1. Define Non-Terminals: For every pair of states q and r, define a non-terminal A[q,r], which generates all strings that take the PDA from state q to state r.
  2. Start Symbol: The start symbol is A[q₀, qᵃ], where q₀ is the start state and qᵃ is an accept state.
  3. Production Rules: For each transition of the PDA, define a production in the CFG:
    • If the PDA reads a terminal a, add a rule A[q,r] → a.
    • If the PDA pushes or pops stack symbols, add rules corresponding to the PDA’s stack operations.

Example: Convert the PDA:

</>
Copy
States: {q₀, q₁}
Transitions:
  δ(q₀, ε, Z₀) = {(q₀, SZ₀)}
  δ(q₀, 'a', ε) = {(q₀, ε)}
  δ(q₀, 'b', ε) = {(q₁, ε)}

Equivalent CFG:

</>
Copy
S → aSb | ε

The grammar produces the same language as the PDA.

Key Takeaways

  • Pushdown Automata (PDAs) and Context-Free Grammars (CFGs) are equivalent in their expressive power.
  • A PDA can be constructed from a CFG by simulating derivations using the stack.
  • A CFG can be constructed from a PDA by modeling the PDA’s state transitions and stack operations.
  • The equivalence is a cornerstone of formal language theory and highlights the power of context-free languages.