- The following is a deterministic PDA for the language:
- The following is a deterministic PDA for the language:
An alternative deterministic PDA for the same langauge is the following:

- The following is a nondeterministic PDA for the language.

- The language
L = {a
^{n}b^{n}a^{n}| n >= 0} is not context-free. This can be proved by using the Pumping Lemma. Given an arbitrary n, take u = a^{n}b^{n}a^{n}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:- 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
^{k}xy^{k}z cannot belong to L because it contains more than n a's in the first part and n a's in the last part. - w contains some a's and some b's.
Then for k>1
vw
^{k}xy^{k}z cannot belong to L because it contains a substring of the form a...ab...ba...ab...b - 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
^{k}xy^{k}z cannot belong to L because it contains more than n b's and only n a's in the first part. - 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
^{k}xy^{k}z cannot belong to L because it contains more than n a's in the last part and n a's in the first part.

- 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
- The language
L = {a
^{n}a^{n}b^{n}| n >= 0} is context-free. A grammar which generates it isS -> aaSb | lambda

- 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^{n}b^{n}a^{n}b^{n}a^{n}b^{n}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:- 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
^{k}xy^{k}z = vxz cannot belong to L because the first half of vxz ends with b's, and the second half too. - w contains some a's from the third block. Then
for k=0
vw
^{k}xy^{k}z = 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. - 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.
- 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.

- 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