ANSWERS TO EXERCISES ON GRAMMAR




 1. (a)  bb, bbcab, bbbcacab, bbbbcacacab, bbbbbcacacacab,
         bbbbbbcacacacacab, ...
         Any string in the language must begin and end with a "b".  In
         between there is a string of k "b"s followed by k "ca"s for some k.

    (b)  The language is context-free because it can be generated by a
         context-free grammar.  In general, it's much easier to test if a
         *grammar* is context-free (check that it follows the rules) than
         to test if a *language* is (find grammar or prove that none exists).  


 2. See Appendix A13 in K+R for the C grammar.

                             expression
                                 |
                        assignment-expression
                     /           |             \
    unary-expression     assignment-operator     assignment-expression
          |                                                |
   postfix-expression            =                  unary-expression
          |                                                |
   primary-expression                              postfix-expression
          |                                                |
      identifier                                   primary-expression
                                                           |
                                                      identifier


 3. bbbcacacacab.  There have to be more "b"s than "ca"s, not counting 
    the "b"s at the start and at the end.