[Points 20] Do exercise 2.7 (page 47) in the Tucker and Noonan book.

1. Define a grammar which generates all strings of the form   aⁿb^n+ka^k   for n, k natural numbers. For instance, lambda, ab, ba, abba, aabb, aabbba, abbbaa, etc.

   Notation:   x^m stands for the string obtained by repeating x m times.

2. Define a grammar which generates all strings on {a,b} with length at least 5.

[Points 25] Consider the following grammar for "boolean expressions":

   BExp ::= false | true | BExp and BExp | BExp imp BExp | not BExp

1. Show that this grammar is ambiguous.
2. Define a non-ambiguous grammar for the same language by enforcing the following conventions:
   • "not" has highest priority. "and" has intermediate priority, and "imp" has lowest priority.
   • "and" is left-associative, and "imp" is right-associative.

[Points 30] The following grammar is motivated by declarations in C:

Non-terminals:  Declaration, Type, Declarator
Terminals:      int, char, *, number, name, '[', ']', '(', ')'

Declaration ::= Type Declarator 
       Type ::= int  |  char

Declarator  ::= * Declarator
              | Declarator '[' number ']'
              | Declarator '(' Type ')'
              | '(' Declarator ')'               
              | name

1. Prove that this grammar is ambiguous: that is, produce a word with two different derivation trees (draw the trees).
2. The constructs '[' number ']' and '(' Type ')' can be thought of as being postfix operators with a declarator as an operand. Suppose that * has lower precedence than these operators. Write an unambiguous grammar that generates the same strings as this grammar and make it easy to identify the components of a declarator.
3. Suppose that the first production for Declarator is changed to make * a postfix operator. That is, suppose that the first production for Declarator is changed into the following production:

   Declarator ::= Declarator *

   Why is the resulting grammar unambiguous?