Exercise 1

1. No. It can be shown by using the Pumping Lemma: for any positive n, consider the string x = ((...(p)...)) where the symbol "(" occurs n times. Let uvw = x with |uv| not greater than n, and |v| > 0. Then v contains only the symbol "(". By the Pumping Lemma, xv²w should be in the language, but that's not possible because xv²w contains more "(" than ")".
2. There are several cases of ambiguity: associativity of the operators "and", "or" and "implies", and precedence between them. The following is an example of ambiguity related to precedence, showing that the string "p and q or r" has two different derivation trees:

            S            S
          / | \        / | \
         S  or S      S and S
       / | \   |      |   / | \
      S and S  r      p  S  or S
      |     |            |     |
      p     q            q     r    
   

3. A possible grammar is the following:

      S -> T implies S | T
      T -> T or U | U
      U -> U and V | V
      V -> p | q | r | (S)
   

Exercise 2

1. The grammar is ambiguous because of the associativity problem with the concatenation (production S -> SS). For instance, the string ( )( )( ) has two different derivation trees:

            S              S
          /   \          /   \
         S     S        S     S
       /  \   /|\      /|\   /  \
      S    S ( S )    ( S ) S    S
     /|\  /|\  |        |  /|\  /|\    
    ( S )( S )            ( S )( S )      
      |    |                |    |
   

2. A possible non-ambiguous grammar G for the same language is:

      S -> lambda | ( S ) S 
   

   We prove now G is not ambiguous. By structural induction: Consider a string x in L(G). We have two cases:

   • Base: x = lambda. In this case there is only one possible derivation for x: S -> lambda. Hence there is only one derivation tree as well.
   • Inductive step: x = ( y ) z, with y, z in L(G). Observe that y and z are uniquely defined by these properties. Namely, if x = a v b w, with v, w in L(G), then y = v and z = w.
     In fact, assume by contradition that y and v are different, and consider the case that y is a prefix of v. But then we must have v = y b v' for some v'. By definition of L, #₍(y) >= 1 + #₎(y) holds, which implies that y is not in L. Contradiction.
     The case in which v is a prefix of y is analogous.
     Since y and v are equal, also z and w must be equal.
     Now, by inductive hypothesis, y and z must have each a unique derivation tree. Let us call these trees ty and tz respectively. We have that x admits only one derivation tree, which is the following one:

                S
             // | \
           ( S  )  S
             |     |
             ty    tz
         

Exercise 3

1. A possible grammar G is the following:

      S -> a b b | a S b b
   

   We prove now that L(G) = L where L = {aⁿb²ⁿ | n > 0}

   • L(G) is included in L, namely, for every x in L(G), we have that there exists n such that x = aⁿb²ⁿ. We can prove this by structural induction.
     • Base: x = a b b. In this case, x satisfies the property with n = 1.

     • Inductive step: x = a y b b, with y in L(G). By inductive hypothesis we have that y = a^mb^2m for some m. Hence x = a y b b = a a^mb^2m b b and therefore x satisfies the property with n = m + 1.

   • L is included in L(G), namely, for every n > 0, we have that if x = aⁿb²ⁿ then x is in L(G). We can prove this by mathematical induction.
     • Base: x = a¹b². Then x has the derivation S -> a b b

     • Inductive step: x = aⁿb²ⁿ. Define y = a^n-1b^2(n-1). We have that x = a y b b. By inductive hypothesis we also have that y is in L(G), namely S ->^*y. Hence S -> a S b b ->^*a y b b, namely x is in L(G).

2. A possible grammar G is the following:

      S -> T U
      T -> lambda | a T b
      U -> lambda | b U c
   

   We show now that L(G) = L, where L = {a^kb^mcⁿ | m = k + n}.

   Let G₁ be the subgrammar with productions

      T -> lambda | a T b
   

   and let G₂ be the subgrammar with productions

      U -> lambda | b U c
   

   Clearly, L(G) = L(G₁)L(G₂). In fact, x is in L(G) iff S -> T U ->^* x, but this is possible iff there exist y, z such that T ->^* y, U ->^* z, and x = y z.

   Let L₁ be the language {a^kb^k | k >= 0} , and let L₂ be the language {bⁿcⁿ | n >= 0}. We are going to show that L(G₁) = L₁ and L(G₂) = L₂. Since L = L₁L₂, we can conclude that L(G) = L.

   • Proof that L(G₁) = L₁.
     • L(G₁) is included in L₁, namely, for every x in L(G₁), we have that there exists k such that x = a^kb^k. We can prove this by structural induction.
       • Base: x = lambda. In this case, x satisfies the property with n = 0.

       • Inductive step: x = a y b, with y in L(G₁). By inductive hypothesis we have that y = a^mb^m for some m. Hence x = a y b = a a^mb^m b and therefore x satisfies the property with k = m + 1.

     • L is included in L(G), namely, for every k >= 0, we have that if x = a^kb^k then x is in L(G₁). We can prove this by mathematical induction.
       • Base: x = a⁰b⁰. Then x has the derivation T -> lambda

       • Inductive step: x = a^kb^k. Define y = a^k-1b^k-1. We have that x = a y b. By inductive hypothesis we also have that y is in L(G₁), namely T ->^*y. Hence T -> a T b ->^*a y b, namely x is in L(G₁).

   • Proof that L(G₂) = L₁.
     This proof is similar to the previous proof, just substitute "b" by "c", and "a" by "b".