1. [Points 18] Consider the alphabet (set of terminal symbols) {a,b}
   1. Define a grammar which generates all strings on {a,b} of the form   ww^r   where   w^r   is the reverse of w. For instance, lambda, aa, bb, abba, baab, aaaa, abaaba, etc.

   2. 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.

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

2. [Points 18] Exercise 2.15 in Sethi's book.

Note1: in this exercise, the terminals are the words in boldface, *, and the symbols between quotes (parentheses and brackets). The syntactic categories are in italics (Declaration, Type, and Declarator) .

Note 2: In Sethi, "parse tree" means the same as "derivation tree".

Note 3: In Question (c), the sentence "Suppose that the first production for Declarator is changed so to make * a postfix operator" means:"Suppose that the first production for Declarator is changed into the following production:

Declarator ::= Declarator *

3. [Points 32] Consider the following grammar for "boolean expressions":

      BExp ::= true | false | not BExp | BExp and BExp | BExp -> 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 "->" has lowest priority.
      • "and" is left-associative, and "->" is right-associative.

4. [Points 32] Give a non-ambiguous grammar for expressions containing natural numbers and the binary operators +, -, *, /, and ^, and such that:
   • ^ has highest priority, * and / have intermediate priority, and + and - have lowest priority.
   • +, -, * and / are left associative. ^ is right-associative.
   • Expressions can contain parentheses, but it is not obligatory.

   Examples of expressions in this language:

   • 5 + 2 - 3   (structured as (5 + 2) - 3)
   • 5 - 2 + 3   (structured as (5 - 2) + 3)
   • 5 - (2 + 3)
   • 50

Note that among the symbols with equal priority, like + and -, and * and /, the precedence is determined by the associativity rule. Thus 50 * 2 / 4 is structured as (50 * 2) / 4, and 50 / 2 * 4 is structured as (50 / 2) * 4.

The natural numbers should be generated by a finite set of productions. A natural number should be either 0 or a positive number, represented as a non-empty sequence of digits starting with a positive digit.