1. Consider the context-free grammarS -> S S + | S S * | a
   • Show how the string aa+a* can be generated by this grammarS -> S S * -> S a * -> S S + a * -> S a + a * -> a a + a *
   • Construct a parse tree for this stringOmitted because I don’t want to draw it in paint.
   • What language does this grammar generate?All additions and multiplications of n or more as, in postfix notation
2. What language is generated by the following grammars?
   • S -> 0 S 1 | 0 1All strings of n 0s followed by n 1s, for n >= 1
   • S -> + S S | – S S | aAll additions and subtractions of as, in prefix notation
   • S -> S ( S ) S | eAll properly-balanced parentheses
   • a S b S | b S a S | eI think this is all strings with equal numbers of as and bs, but I can’t say it very convincingly. I don’t have the tools, yet, to prove anything non-trivial about a grammar that isn’t provable by contradiction.
   • S -> a | S + S | S S | S * | ( S )This one is confusing. I jotted down “All sums and stars of any number of as, optionally paranthesized.” I’m not sure how I feel about that – I think that

     S -> a | S + S | ( S )

     is sufficient for all sums of as in any combination, but I’m not really clear on how the other productions come into play beyond what I’ve said.

3. Which of the grammars in 2) are ambiguous?a, c and d, definitely. Possibly e, which I don’t understand very clearly, but I don’t believe so. I am pretty confident saying b is unambiguous. I had listed a erroneously because in my notes I had incorrectly written down the problem with the empty string as a production for S.
4. Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.
   • Arithmetic expressions in postfix notation

     S -> S N + | S N - | S N * | S N / | N
     N -> N D | e
     D -> 0 | 1 | 2 .. | 9

   • Left-associative lists of identifiers separated by commas

     left -> left__, ID | ID | e
     left__ -> left__ ID , | e

     This seems pretty crappy… but maybe it’s reasonable? Sorry about the poor naming, too.

     As a note, it’s easier for non-empty left-associative lists:

     left -> left, ID | ID

   • Right-associative lists of identifiers separated by commassee above but with ID before right
   • Arithmetic expressions of integers and identifiers with the four binary operators +, -, *, /.

     S -> ( S ) | S OP S | ID | INT
     OP -> + | - | * | /

     I am not very confident on this one, and even less so on the next:

   • Add unary plus and minus to the arithmetic operators of the previous question

     S -> ( S ) | S OP S | ID | INT | UNARY
     UNARY -> - ID | - INT | + ID | + INT | - ( S ) | + ( S )

     I’m really uncomfortable with this answer.

5. • Show that all binary strings generated by the following grammar have values divisble by 3.

     num -> 11 | 1001 | num 0 | num num

     11 is divisible by 3, 1001 is divisible by 3. The other forms numbers can take are one of those followed by a 0, which is a left-shift, which is a multiplication by 2, which does not affect divisibility by three; and a valid number of one of those types followed by another valid number of one of those types; since each of the first types can be expressed as 3k, this is (3k1 * n + 3k2), which is divisible by 3.

   • Does the grammar generate all binary strings with values divisble by 3?I think so. You get 3, 6, 9, and all combinations of multiples of two of those two strings… it *feels* like enough.
6. Construct a context-free grammar for roman numeralsThe question is malformed.

This stuff is cool, I like learning about grammars. However, I wish I had a reference implementation of the answers somewhere – I really am unclear on a few of my answers, and have not yet come up with a satisfactory answer for 4e. I hope that the text develops the skills necessary to make convincing proofs of these statements soon!