1
$\begingroup$

To understand the Pumping Lemma, I'm going to prove that the language $L = \{0^n1^m0^n | n,m \geq0\}$ is not regular. I choose string $w = 0^{p/2}1^{p/2}0^{p/2}$, for any even number $p$. Clearly $|w| > p$. I use the following decomposition

  • $x = 0^{p/2}$
  • $y = 1^{p/2}$
  • $z = 0^{p/2}$

Clearly for any $i$, $xy^iz \in L$, because the number of $1$s is not important and it doesn't lead to a contradiction. I think there is something I didn't understand about the Lemma. I appreciated it if you let me know why while $L$ is not a regular language, but my decomposition didn't lead to non-regularity.

As another example, consider language $L_1 = \{0 ^{3n} | n \geq 0\}$. This language is clearly regular. I choose $w = 000000$, for $p=3,$ $x=0, y=00, z=000$. It is clear pumping $y$ in for $i=2$ $xy^iz = 00000000 \notin L_1$ while the language is regular. Why I could find a decomposition that shows it is non-regular while the language is regular?

Thanks in advance.

$\endgroup$
1
  • $\begingroup$ @Steven This is exact;y my problem. I appreciate it if you post this hint and clarify the prblem of my proof $\endgroup$
    – M a m a D
    Commented Apr 24, 2023 at 13:14

1 Answer 1

2
$\begingroup$

To show that a language $L$ is not regular you need to argue that the pumping lemma does not hold. That is, you want to show that for every $p$, there exists some word $w$ such that, for every decomposition of $w$ as $xyz$ with $|xy| \le p$ and $|y| \ge i$, there exists some $i \ge 0$ such that $xy^i z \not\in L$.

The quantifiers and their order are critical. What you can do is choose $w$ as a function of $p$. You don't get to choose a specific decomposition $xyz$, so you want to pick a $w$ that will make easy to argue about all possible decompositions.

In you first example $w = 0^{p/2} 1^{p/2} 0^{p/2}$ is not a great choice since there is a way to write $w$ as $xyz$ such tat $xy^i \in L$ for all $i \ge 0$. However, this doesn't tell you anything about the (non-)regularity of $L$ since there might be other choices of $w$.

Pick, for example, $w = 0^p 1^p 0^p$. Then, all decompositions are of the form $x= 0^{a}$, $y = 0^{b}$, $z=0^{p-a-b}1^p 0^p$, for some $a \ge 0$, $b \ge 1$ with $a+b \le p$. Therefore $xy^iz = 0^{p + (i-1)b} 1^p 0^p$. You can then pick $i=0$ (this is just an example, any $i\neq 1$ works in this case) to get $xy^0z = 0^{p-b}1^p0^p \not\in L$.


Conversely, if a language $L$ is regular, then there is some $p$, such that all $w \in L$ with $|w|\ge p$ admit some decomposition $w=xyz$ such that $xy^iz \in L$ for all $i$.

You don't get to choose the decomposition (as you have done) and, in general, you don't get to choose $p$. The pumping lemma only tells you that some $p$ exists.

Now, in your particular case it happens that the pumping length $p$ of $L$ is actually $3$ (this can be shown by arguing that a DFA with $3$ states can recognize $L$, you can't just blindly fix a value). Your example doesn't work because you picked the wrong decomposition of $w=000000$. Here is a decomposition that satisfies the pumping lemma: $x= \varepsilon$, $y=000$, $z=000$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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