 Consider the contextfree 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
a
s, in postfix notation
 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
a
s, in prefix notation  S > S ( S ) S  eAll properlybalanced parentheses
 a S b S  b S a S  eI think this is all strings with equal numbers of
a
s andb
s, but I can’t say it very convincingly. I don’t have the tools, yet, to prove anything nontrivial 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
a
s, optionally paranthesized.” I’m not sure how I feel about that – I think thatS > a  S + S  ( S )
is sufficient for all sums of
a
s in any combination, but I’m not really clear on how the other productions come into play beyond what I’ve said.
 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.  Construct unambiguous contextfree 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
 Leftassociative 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 nonempty leftassociative lists:
left > left, ID  ID
 Rightassociative 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.
 Arithmetic expressions in postfix notation

 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 leftshift, 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.
 Show that all binary strings generated by the following grammar have values divisble by 3.
 Construct a contextfree 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!