Skip to content
Tutorials Center
My learning

Topics

Lesson 56 of 59 ยท Practice and Review

Practice: Grammars and Pushdown Automata

Practice designing context-free grammars and pushdown automata, prove languages are not context-free, and check every answer with a PDA simulator and a grammar tester.

Context-free grammars and pushdown automata are two views of the same family of languages, and designing them is a skill you build by repetition. This lesson gives a set of classic problems, explains the thinking that leads to each solution, and then checks every solution mechanically: a nondeterministic PDA simulator runs your automata, and a grammar tester generates the language of each grammar and compares it with the property it should have.

If you are rusty, review how a PDA moves: in each step it reads an input symbol (or none, an ฮต-move), looks at the top of the stack, pops it, and pushes a string of symbols while changing state.

Thinking patterns

  • Matching pairs such as a^n b^n: use a rule of the form S -> aSb, or push on a and pop on b.
  • Mirror structures (palindromes): S -> aSa | bSb | ..., or push the first half, guess the middle, then pop while matching.
  • Independent counts joined by "or": write two grammars and take the union, or branch nondeterministically at the start of the PDA.
  • Counting comparisons (equal numbers of two symbols in any order): the stack stores the surplus of whichever symbol is currently ahead.

Problems on pushdown automata

Design a PDA for each language.

  • P1. { a^n b^n : n โ‰ฅ 0 }
  • P2. Even-length palindromes { w w^R : w โˆˆ {a, b}* }
  • P3. Strings over {a, b} with the same number of as and bs
  • P4. { a^i b^j c^k : i = j or j = k }

Ideas.

  • P1: push one marker per a, pop one per b; accept when the markers are gone.
  • P2: push each symbol of the first half; nondeterministically guess the middle by an ฮต-move; then each input symbol must match the top of the stack. A PDA for palindromes needs nondeterminism, because it cannot know where the middle is.
  • P3: the stack holds the surplus. If the top is the same as the input (or the stack is empty), push; if it is the opposite, pop.
  • P4: at the start, guess which equality to check. Branch one pushes for as and pops for bs, then skips the cs; branch two skips the as, pushes for bs and pops for cs.

The simulator below stores transitions as tuples (state, input_symbol_or_empty, stack_top, new_state, string_to_push). The stack top is the first character of the stack string and $ marks the bottom. A word is accepted when the machine reaches state qf with all input consumed.

Python A nondeterministic PDA simulator checking four PDAs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Problems on grammars

Write a context-free grammar for each language.

  • G1. { a^n b^n : n โ‰ฅ 0 }
  • G2. All palindromes over {a, b} (odd and even length)
  • G3. Strings with equal numbers of as and bs
  • G4. { a^n b^{2n} : n โ‰ฅ 0 }
  • G5. { a^i b^j c^k : i = j or j = k }

Solutions.

TEXT
G1:  S -> a S b | ฮต
G2:  S -> a S a | b S b | a | b | ฮต
G3:  S -> a S b S | b S a S | ฮต
G4:  S -> a S b b | ฮต
G5:  S -> X C | A Y
     X -> a X b | ฮต        C -> c C | ฮต
     A -> a A | ฮต          Y -> b Y c | ฮต

For G3 the idea is: any non-empty balanced string starts with a or b; the first a is matched by a later b, splitting the string into "inside" and "after" parts that are balanced themselves. In G5, X C covers the case i = j (the cs are free) and A Y covers j = k.

The next program tests each grammar. It generates the language by expanding the leftmost nonterminal (a brute-force search of all sentential forms up to a size bound) and compares the result with a predicate. It then counts the leftmost derivations of a few strings, which reveals ambiguity: abc has two derivations under G5, one through each branch, because i = j = k.

Python Testing grammars by generating their language

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The language G5 is a standard example of an inherently ambiguous context-free language: every grammar for it is ambiguous, because strings with i = j = k fall in both cases.

Problems on non-context-free languages

The pumping lemma for context-free languages says: if L is context-free there is p such that every s โˆˆ L with |s| โ‰ฅ p can be written s = uvxyz with |vxy| โ‰ค p, |vy| โ‰ฅ 1, and u v^i x y^i z โˆˆ L for all i โ‰ฅ 0.

Problem 13. Show { a^n b^n c^n : n โ‰ฅ 0 } is not context-free. Take s = a^p b^p c^p. Since |vxy| โ‰ค p, the window vxy cannot contain both an a and a c: it touches at most two of the three blocks. Pumping up (or down) changes the count of at most two letters but not the third, so the three counts become unequal. Contradiction.

Problem 14. Show { ww : w โˆˆ {a, b}* } is not context-free. Take s = a^p b^p a^p b^p. The window vxy of length at most p lies within at most two adjacent blocks. Pumping it destroys the equality of the two halves in every case. Contradiction.

Closure properties give quicker proofs

Context-free languages are closed under union, concatenation, star and intersection with a regular language, but not under intersection or complement. Here is a proof that exploits this: L1 = { a^n b^n c^m } and L2 = { a^m b^n c^n } are both context-free, yet L1 โˆฉ L2 = { a^n b^n c^n } is not. So the class of context-free languages is not closed under intersection. And since A โˆฉ B = complement(complement(A) โˆช complement(B)), it cannot be closed under complement either.

Deterministic PDAs are strictly weaker than nondeterministic ones: the palindrome language needs the guess of the middle. Deterministic context-free languages are closed under complement, which is why parser generators (LR parsers) are built on them.

More problems to try

  1. Write a grammar for { a^i b^j : i < j } and a PDA for it.
  2. Convert the grammar S -> aSb | ab to a PDA using the standard construction: one state, pop the nonterminal and push the right-hand side, match terminals.
  3. Is { a^n b^m c^n d^m } context-free? (It is not: the crossing dependencies need two independent stacks.)
  4. Find the leftmost derivation and the parse tree of aabbab in G3.
  5. Remove ฮต-rules and unit rules from G5 and convert it to Chomsky normal form with the grammar toolkit.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does a PDA for even-length palindromes need nondeterminism?

    Without knowing the middle the machine cannot tell when to stop pushing and start matching, so it guesses with an ฮต-move.
  2. 2. In the grammar S -> aSbS | bSaS | ฮต, what do the two S's after the pair represent?

    The first symbol is matched by a later opposite symbol; between them and after them the strings are balanced, each generated by an S.
  3. 3. In the pumping lemma proof for a^n b^n c^n, why is the window vxy never able to contain both an a and a c?

    Between the last a and the first c there are p b's, so any window of length at most p touches at most two adjacent blocks.
  4. 4. Which closure property fails for context-free languages?

    a^n b^n c^m and a^m b^n c^n are context-free, but their intersection a^n b^n c^n is not.
  5. 5. The language { a^i b^j c^k : i = j or j = k } is described as inherently ambiguous because

    Strings with i = j = k satisfy both conditions, and every grammar must derive them in more than one way.

Summary

  • Match structure to mechanism: pairs use S -> aSb, palindromes need a guessed middle, "or" conditions branch.
  • A PDA simulator over configurations (state, position, stack) lets you test every design on all short strings.
  • Grammars can be tested by generating their language and comparing it with a predicate.
  • Non-context-freeness is shown with the CFL pumping lemma or with closure properties such as non-closure under intersection.
  • Inherent ambiguity exists: some context-free languages have no unambiguous grammar.

Next: Practice: Turing Machines and Decidability