Due

Solutions will be available.

Problem 0: Review old homeworks and exams.

Problem 1: Give a grammar that generates the same language as the regular expression (a + b)^*(a^* + (ba)^*).

Problem 2: Give a pushdown automaton that accepts the language {aⁿb^m | m > n >= 0}. Show that your PDA accepts aabbb and bbbb and that it rejects aaab.

Problem 3: For each language given below either give a context free grammar for that language or prove that it is not context free.

• {aⁿbⁿaⁿbⁿ | n >= 0}
• {aⁿb^n+ma^m | m, n >= 0}
• {aⁿbⁿa^mb^m | m, n >= 0}

Problem 4:

• Give a grammar that generates postfix expressions using operators +, -, *, and /. Use the terminal "id" to stand for any variable name and "lit" to stand for integer literals.
• Show a derivation of "id lit id + *" in your grammar.

Problem 5: Determine whether the grammar implicitly defined by the following rules is ambiguous. Prove your answer. If the grammar is ambiguous, determine whether the language it generates is inherently ambiguous.