CFG to PDA algorithm #
Starting from a CFG and going to a PDA is a lot easier than going the other way.
Lets start out with this grammar:
\( S \to AB \\ A \to aA \mid \lambda \\ B \to bB \mid \lambda\)We can start our PDA by drawing 3 states, one start and one accept.
The first transition triple is \( \lambda, \empty, S \empty \) , and the second transition is \( \lambda, \empty, \empty \) .
In the middle there will be a self loop with a bunch of triples. For example, if we had a production \( X \to \alpha \) , then the triple will be \( \lambda, X, \alpha \) . “If the top of the stack is a non-terminal, we can replace it with a terminal.”
Another rule to follow is that for all terminals we use the triple \( a, a, \lambda \) (if \( a \) is a terminal).
We can follow this same pattern for the other productions.
So we have 5 productions, so we have 5 triples of that form.
\( \lambda, S, AB \\ \lambda, A, aA \\ \lambda, A, \lambda \\ \lambda, B, bB \\ \lambda, B, \lambda\)We also have the triples
\( a, a, \lambda \\ b, b, \lambda\)
This PDA simulates a derivation, for example \( aab \) :
\(S \to AB \to aAB \to aaAB \to aaB \to aabB \to aab\)Note: A PDA simulates a leftmost derivation.
Another pumping lemma example with a context-free language #
For the language \( L = \{ww \mid w \in \{0,1\}* \} \)
Theorem: \( L \) is not context-free
Proof:
Assume for contradiction that \( L \) is context free.
Let \( p \) be \( L \) ’s pumping length. Consider the string \( w = 0^p 1^p 0^p 1^p \) , which is length at least \( p \) and is in \( L \) .
The pumping lemma says there exists \( w = uvxyz \) where \( v \) and or \( y \) is not empty, \( |vxy| \leq p \) and \( uv^ixy^iz \) is in \( L \) for all \( i \) .
If \( vxy \) is entirely in the first set of \( p \) 0’s, then the pumped \( v \) and \( y \) will create string that isn’t in the language \( L \) .