1. [Points 10] Enrich the grammar for the language of English sentences seen in class so to generate also negative and interrogative sentences, like ``the cat does not drink the milk'', and ``does the cat drink the milk?''.

   The grammar for the English sentences given in class can be found at the address http://www.cse.psu.edu/~catuscia/teaching/cg428/00Spring/lecture_notes/Example_English.html

2. [Points 10] Define a grammar that generates the language of all strings on {a,b} of the form aⁿ bⁿ, where n is an arbitrary natural number.

   Notation: a⁰b⁰ represents the empty string, a¹b¹ represents the string ab, a²b² represents the string aabb, etc.

   Note: The set {a,b} is the set of terminal symbols for this language. Such set is also called ``alphabet''.

3. [Points 20] Define a grammar that generates the language of all strings on {a,b} which contain exactly the same number of a's and b's.

   Examples of strings in this language: the empty string, ab, ba, aabb, abab, baba, bbaa, baab, aaabbb, etc.

4. [Points 30] Consider the following grammar for "boolean expressions":

      BExp ::= true | false | not BExp | BExp and BExp | BExp -> BExp
   

   • Show that this grammar is ambiguous
   • 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.

5. [Points 30] 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 represented as a non-empty sequence of digits starting with a positive digit.