COMS W3261 CS Theory
Lecture 7: Context-Free Grammars

1. Definition of Context-Free Grammar

2. Derivations Using a Grammar

3. Leftmost and Rightmost Derivations

4. Parse Trees

5. Ambiguity

6. Practice Problems

  1. Construct a CFG that generates the language { anbn | n ≥ 0 }.
  2. Prove that the language generated by the grammar G1 in section 2 consists of all and only all strings of balanced parentheses.
  3. Construct a CFG that generates ELP = { wwR | w is any string of a's and b's }. This is the language of even-length palindromes over the alphabet {a, b}. A palindrome is a string that reads the same in both directions.
  4. Prove that ELP is not a regular language.
  5. Construct an unambiguous CFG for all regular expressions over the alphabet {a, b}.

7. Reading


aho@cs.columbia.edu
verma@cs.columbia.edu