Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Problem 1
Write down the 4tuple for a grammar
Gλ such that
L(Gλ) = { λ }
Problem 2
Write down the 4tuple for a grammar
Ga such that
L(Ga) = { a }
Problem 3
Write down the 4tuple for a grammar
G∅ such that
L(G∅) = { }
Problem 4
We can convert a regular expression E to a grammar G
generating the same language (i.e. L(E) = L(G)) following
a procedure similar to the one we used to convert regular
expressions to NDFAs.
 draw the expression tree for E

work from the leaves up to the root, replacing each
subtree/subRE with an equivalent grammar using the
three grammars from above for leaf nodes, and using the
algorithms given in the lecture notes for interior
nodes. Note that every time you introduce a new symbol
"$\$$", call it $\$_i$ with a new
number i, so the symbols stay distinct.

The grammar at the root node is equivalent to the
input regular exression.
Here's an example of the process,
converting
ab*λ:
Draw a parse tree for the string
abb with this grammar.
Problem 5
Use the above procedure to convert the regular
expression a(ab)* to a grammar. Show your work!