Prove $01^m2^{m+j+2}1^j$ is not a regular language.

Question

I am trying to prove that $01^m2^{m+j+2}1^j$ is not a regular language using the pumping lemma. I am having trouble splitting it into "xyz".

Answer 1

The method is similar to the one used in your other question.

---

To address the confusion, the idea is as follows:
You choose a string $w\in L$. An adversary splits this $w$ as $xyz$ (in whatever way they like). For any split that they do, you need to think of a $k$ so that $xy^kz\notin L$.

This is why we consider all possible splits $xyz$ below.

---

Assume $L$ to be regular. Let $n$ be the pumping lemma constant. Consider the string $w = 01^n2^{n+2}$ (here $j=0$). Then, the cases are:

• $y=0$.
• $y=01^m$ for some $m$ where $1\le m\le n-1$.
• $y=1^m$ for some $m$ where $1\le m\le n-1$.

In each case, $xy^0z\notin L$. Note that the last two cases arise only if $n\ge 1$.

This proves $L$ to be non-regular.