Problem 1: Let L be the language with alphabet {0, 1, 2} consisting of strings that do not have any consecutive 0's, any consecutive 1's, or any consecutive 2's. L is a regular language, but it is rather hard to write a regular expression for L. On the other hand, it is fairly easy to write a context-free grammar for L. Please write one and explain why it works. It is sufficient to explain what each of your varibles is intended to generate, without giving a formal proof that they do so.

Problem 2: There are many ways to prove that every regular language is a context-free language. We want you to give a particular proof, in which you take a NFA for a regular language L and construct a CFG for L. Give a detailed proof, starting with the construction of the CFG. Then prove both directions of the equivalence: if the NFA accepts string w then the CFG generates w, and conversely. In each direction, state the inductive hypothesis and give the basis and inductive parts of the proof. Here is a Hint.

Problem 3: Arithmetic expressions with operator + and parentheses can be generated by the grammar

where a stands for any number. This grammar is ambiguous.

(a) Give an example of a string that has two or more leftmost derivations or parse trees.
(b) Design an unambiguous grammar for the same language.

Note: There are several examples like this one in the text. In a sense, you have only to translate what was done there to a simpler example.