**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.