## 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, xv2w should be in the language, but that's not possible because xv2w 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 = {anb2n | n > 0}

• L(G) is included in L, namely, for every x in L(G), we have that there exists n such that x = anb2n. 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 = amb2m for some m. Hence x = a y b b = a amb2m 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 = anb2n then x is in L(G). We can prove this by mathematical induction.
• Base: x = a1b2. Then x has the derivation S -> a b b

• Inductive step: x = anb2n. Define y = an-1b2(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 = {akbmcn | m = k + n}.

Let G1 be the subgrammar with productions

```   T -> lambda | a T b
```
and let G2 be the subgrammar with productions
```   U -> lambda | b U c
```
Clearly, L(G) = L(G1)L(G2). 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 L1 be the language {akbk | k >= 0} , and let L2 be the language {bncn | n >= 0}. We are going to show that L(G1) = L1 and L(G2) = L2. Since L = L1L2, we can conclude that L(G) = L.

• Proof that L(G1) = L1.
• L(G1) is included in L1, namely, for every x in L(G1), we have that there exists k such that x = akbk. 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(G1). By inductive hypothesis we have that y = ambm for some m. Hence x = a y b = a ambm 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 = akbk then x is in L(G1). We can prove this by mathematical induction.
• Base: x = a0b0. Then x has the derivation T -> lambda

• Inductive step: x = akbk. Define y = ak-1bk-1. We have that x = a y b. By inductive hypothesis we also have that y is in L(G1), namely T ->*y. Hence T -> a T b ->*a y b, namely x is in L(G1).

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