Question 1.29: Use the pumping lemma to show that the following languages a...
Use the pumping lemma to show that the following languages are not regular.
a. A_{1} = \left\{0^{n}1^{n}2^{n}\mid n\geq 0 \right\}
c. A_{3} = \left\{a^{2^{n} }\mid n \geq 0 \right\} (Here, a^{2^{n} } means a string of 2^{n} a’s.)
(a) Assume that A_{1} = \left\{0^{n}1^{n}2^{n}\mid n\geq 0 \right\} is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string 0^{p}1^{p}2^{p} Because s is a member of A_{1} and s is longer than p, the pumping lemma guarantees that s can be split into three pieces, s=xyz, where for any i ≥ 0 the string xy^{2} z is in A_{1}.
Consider two possibilities:
- The string y consists only of 0s, only of 1s, or only of 2s. In these cases, the string xyyz will not have equal numbers of 0s, 1s, and 2s. Hence xyyz is not a member of A_{1}, a contradiction.
- The string y consists of more than one kind of symbol. In this case, xyyz will have the 0s, 1s, or 2s out of order. Hence xyyz is not a member of A_{1}, a contradiction.
Either way we arrive at a contradiction. Therefore, A_{1} is not regular.
(c) Assume that A_{3} = \left\{a^{2^{n} }\mid n \geq 0 \right\} is regular. Let p be the pumping length given by the pumping lemma. Choose s to be the string a^{2^{p} }. Because s is a member of A_{3} and s is longer than p, the pumping lemma guarantees that s can be split into three pieces, s= xyz, satisfying the three conditions of the pumping lemma.
The third condition tells us that \left|xy\right| \leq p. Furthermore, p\lt 2^{p} and so \left|y\right| \lt 2^{p}.
Therefore, \left|xyyz\right| = \left|xyz\right| + \left|y\right|\lt 2^{p}+2^{p} = 2^{p+1}. The second condition requires \left|y\right| \gt 0 so 2^{p}\lt \left|xyyz\right| \lt 2^{p+1}. The length of xyyz cannot be a power of 2. Hence xyyz is not a member of A_{3}, a contradiction. Therefore, A_{3} is not regular.