Menu
You must print this sheet out and write/type answers on it!
  1. Write down the 4-tuple for a grammar Gλ such that L(Gλ) = { λ }
     
  2. Write down the 4-tuple for a grammar Ga such that L(Ga) = { a }
     
  3. Write down the 4-tuple for a grammar G∅ such that L(G∅) = { }
     
  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.
    1. draw the expression tree for E
    2. work from the leaves up to the root, replacing each sub-tree/sub-RE 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.
    3. 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.
     
  5. Use the above procedure to convert the regular expression a(a|b)* to a grammar. Show your work!