Topics

• Using regular expressions and context free grammars with Lex and Yacc to build complex programs quickly. A calculator example.
• Chomsky Normal Form (Finish problems on Chomsky Normal Form that we didn't get to last time,
  i.e. all of them ;-)
• Push Down Automata.

Problems to work on

1. Give a grammar for the language {aⁱ b^j | i <= j <= 2i}.
2. Consider the grammar

   S --> z A s 
   A --> xb B yz
   B --> cd A q | epsilon
   

   Play around with this grammar and try to guess what a pumping lemma for CFG's might look like.
3. Construct a PDA for {0ⁿ1ⁿ | n >= 0} without looking at your notes.
4. Construct a PDA for {0ⁿ1^m0^m1ⁿ | n,m >= 0}