0
$\begingroup$

I'm trying to prove that L = {$0^n1^m0^n | m,n >= 1$} in NOT regular but I am struggling with the demostration process.

I know the conditions are that:

  • $|y| > 0$; $'y'$ can't be empty
  • $|xy| <= p$(word/string length)
  • for all $i$ > 0, $xy^iz$ must be in L

Lets choose the string $s = 0^p10^p$.

The first condition states that: $y = 0^k$ for $k > 0$

Being $x$ and $y$ composed of zeros such that complies with the second condition.

At $i = 0$, the string should be in L, thus $xy^0z = xz = 0^{p-k}10^p$ but $y$ can't be empty, right?

From now on, I get lost in the demostration and require help to properly prove it is not regular.

$\endgroup$
1
  • $\begingroup$ If $p$ is the pumping length, then splitting the string $w=0^p10^p$ as per the pumping lemma must have $y \in 0^+$, and thus $z$ must be a finite suffix of the form $0^*10^p$. But then $w_i = xy^iz$ has a longer $0$-prefix than $0$-suffix when $i \geq 2$, creating a contradiction as all $w_i$ are supposed to be in $L$. $\endgroup$
    – Yonatan N
    Mar 28 at 21:16

1 Answer 1

2
$\begingroup$

First of all, the empty pump matters (in fact, sometimes the empty pump, e.g. the case $i=0$ is the simplest way to prove the non-regularity). Thus, the third condition is actually "for all $i\geq 0$ $x y^i z\in L$". The condition "$y$ can't be empty" is not about the iterations number (e.g. the string $y^i$), it states that the word $y$ itself is not empty. Otherwise, every language is trivially pumped if we choose $y=\varepsilon$ and the lemma is meaningless.

Thus, your proof is correct, using the empty pump. If you do not like the case $i=0$, you may choose $i=2$ and get another word $0^{p+k}10^p\notin L$, but imo your choice is nice enough.

The only imprecise part is about the order of the applications of 1st and 2nd conditions. If you do not apply the condition $|xy|\leq p$ to the word $0^p 1 0^p$, you cannot know in advance that $y$ consists of zeros. There are many non-empty subwords of $0^p 1 0^p$ containing also $1$. The condition $|y|>0$ determines that $y=0^{k}$, $k>0$ only after the second condition determines that $y\in 0^*$.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer, may I ask for an example/elaboration on how for each i, the word has the same number of 0s and 1s? Thus demonstrating that contradicts due to y>=1?. Sorry to bother if I ask too much. Thanks again for the help. $\endgroup$ Mar 28 at 21:21
  • $\begingroup$ @BadProgrammer I cannot see from the description of your language that the number of 1 and 0 must be equal or unequal. The only condition is that the number of zeros before 1 is the same as the number of zeros after 1. Thus, $0^{p+i*k}10^p$ is not in $L$ for all $i\neq 0$ (e.g., for all $y^j$, where $j\neq 1$). The pump throws us out of the language, and since all regular languages can be pumped, this language is not regular. $\endgroup$
    – Tonita
    Mar 28 at 21:53
  • $\begingroup$ Oh! I see now. Apologies, I am pretty new to this subject matter. Thanks $\endgroup$ Mar 29 at 7:17

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.