Exercise 1

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ⁿbⁿbⁿ | n >= 0} is context-free. A grammar which generates it is

   S -> aSbb | lambda

3. The language L = {aⁿbⁿbⁿ | n >= 0} 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.

   Exercise 2

   One solution is represented by the following table for the transition function. Columns are the symbols of the tape, rows are the states, and the three symbols in each box represent the result of the transition. Empty positions correspond to undefined results. D stands for "Delta" (i.e. blank). h is the halting state

        \symbol
    state\    a       b       c       d       A       B       X       D
          \_______________________________________________________________
          |       |       |       |       |       |       |       |       |       
        0 |       |       |       |       |       |       |       | D 1 R |      
          |_______|_______|_______|_______|_______|_______|_______|_______|  
          |       |       |       |       |       |       |       |       |       
        1 | A 2 R | B 4 R |       |       |       |       | X 1 R | D h S | 
          |_______|_______|_______|_______|_______|_______|_______|_______|  
          |       |       |       |       |       |       |       |       | 
        2 | a 2 R | b 2 R | X 3 L |       |       |       | X 2 R |       |
          |_______|_______|_______|_______|_______|_______|_______|_______|
          |       |       |       |       |       |       |       |       |  
        3 | a 3 L | b 3 L |       |       | A 1 R |       | X 3 L |       |
          |_______|_______|_______|_______|_______|_______|_______|_______|
          |       |       |       |       |       |       |       |       |  
        4 |       | b 4 R |       | X 5 L |       |       | X 4 R |       |  
          |_______|_______|_______|_______|_______|_______|_______|_______|
          |       |       |       |       |       |       |       |       |  
        5 |       | b 5 L |       |       |       | B 1 R | X 5 L |       |  
          |_______|_______|_______|_______|_______|_______|_______|_______|