1
$\begingroup$

Show the following language is not regular by using the pumping lemma

$A_1=\{0^n1^n2^n|n \geq 0\}$

Proof by Contradiction:

Assume $A_1$ is Regular.

Let M be the pumping length and let S be a string in $A_1$ such that $|S|\geq M$, so let $$S=0^M1^M2^M$$

Because of the pumping lemma, we can divide S into three pieces xyz, so let $S=xyz$ where $|y|>0$ and $|xy|\leq M$.

Let $xy=0^M$ and $z=1^M2^M$, so we can say $x=0^{M-1}$ and $y=0$.

Since the pumping lemma says that any $xy^iz\in A$ where $i\geq 0$, then $xy^2z\in A$. Therefore,

$$0^{M-1}0^21^M2^M=0^{M+1}1^M2^M\in A_1$$

Which is a contradiction to the original language. Therefore, $A_1$ is not regular.

Ho does that look?. This is my first proof with the pumping lemma.

$\endgroup$
1
$\begingroup$

Looks good otherwise, except you need to show that there is no eligible $xyz$ division. You've only shown that $x = 0^{M-1}$ and $y = 0$ is not eligible. Modifying the proof isn't hard though, just let $x = 0^{M-n-k}, y = 0^n, z = 0^k 1^M 2^M$ where $M \geq n > 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.