CS 314	Prof Steinberg	Fall 2005

Exercise Set 1

These problems are not to be turned in.  However, it is strongly suggested
that you do them.  They provide practice that is essential to doing well
on the exams.


1. Given grammar G: (capitals are non-terminals, everything else is a terminal)

    S -> A | S # S | S @ S	  <==== this line revised
    A -> C | C A
    C -> a | b | c
    
  for each of the strings below:
  - if it is in L(G) prove it by giving both
    - a leftmost derivation
    - a parse tree.  If it is ambiguous demonstrate that fact with parse trees.
 - if it is not in L(G) say so and explain why

a.  aa # bb
b.  a @ b # c
c.  ab

2.  Rewrite the grammar G above so that no string in its languge is
    ambiguous.  Make # have higher precidence than @ and make both #
    and @ be left-associative.

2.  Given grammar G':

     S -> A B
     A -> x | A a
     B -> y | b B
 
a. Give a string that is in L(G') and one that is not
b. Describe in English what strings are in L(G').