## Exercise 1

1. The following is a deterministic PDA for the language:

2. The following is a deterministic PDA for the language:

An alternative deterministic PDA for the same langauge is the following:

3. The following is a nondeterministic PDA for the language.

It's possible to show that there does not exist a deterministic PDA for this languge

## Exercise 2

1. The language L = {anbnan | n >= 0} is not context-free. This can be proved by using the Pumping Lemma. Given an arbitrary n, take u = anbnan in L. Consider five strings v,w,x,y,z such that u = vwxyz, |wxy|<=n and |wy|>0. Assume |w|>0. We have the following cases:
1. w contains only a's from the first part of u. Then y may contain a's from the first part, and/or b's, but not a's from the last part. Hence for k>1 vwkxykz cannot belong to L because it contains more than n a's in the first part and n a's in the last part.
2. w contains some a's and some b's. Then for k>1 vwkxykz cannot belong to L because it contains a substring of the form a...ab...ba...ab...b
3. w contains only b's. Then y may contain b's, and/or a's from the last part, but not a's from the first part. Hence for k>1 vwkxykz cannot belong to L because it contains more than n b's and only n a's in the first part.
4. w contains only a's from the last part of u. Then y may contain a's from the last part too. In any case, for k>1 vwkxykz cannot belong to L because it contains more than n a's in the last part and n a's in the first part.
The case in which |y|>0 is analogous.

2. The language L = {ananbn | n >= 0} is context-free. A grammar which generates it is
S -> aaSb | lambda
3. The language L = {xx~ | x in {a,b}*} is not context-free. This can be proved by using the Pumping Lemma. Given an arbitrary n, take u = anbnanbnanbn in L. Let us call "blocks" the six parts of only a's or only b's of which u is composed. Consider five strings v,w,x,y,z such that u = vwxyz, |wxy|<=n and |wy|>0. Assume |w|>0. We have the following cases:
1. w contains a's and/or b's from the first two blocks. Then y may contain a's from the first block, and/or b's from the second block, but nothing else. Hence for k=0 vwkxykz = vxz cannot belong to L because the first half of vxz ends with b's, and the second half too.
2. w contains some a's from the third block. Then for k=0 vwkxykz = vxz cannot belong to L because it contains less than n a's in the third block and n b's in the sixt block.
3. w contains some b's from the fourth block. Similar to Case 2: we conclude that vxz contains less than n b's in the fourth block and n a's in the first block.
4. w contains a's and/or b's from the last two blocks. Similar to Case 1: we conclude that the first half of xvy starts with a's, and the second half too.
The case in which |y|>0 is analogous.