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 = {aⁿbⁿaⁿ | n >= 0} is not context-free. This can be proved by using the Pumping Lemma. Given an arbitrary n, take u = aⁿbⁿaⁿ 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 vw^kxy^kz 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 vw^kxy^kz 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 vw^kxy^kz 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 vw^kxy^kz 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 = {aⁿaⁿbⁿ | 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 = aⁿbⁿaⁿbⁿaⁿbⁿ 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 vw^kxy^kz = 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 vw^kxy^kz = 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.