1
$\begingroup$

there is some thing in pumping lemma that I don't understand it.
I think about application to prove irregularity of language.
We have for each word (actual length) find partition: $xyz$ such that $\forall i \ge 0 xy^iz \in L$.
So we can find word, but tell me - if we can choose partition ? (so choose $y$) ? Maybe we should check each possible partition ?

$\endgroup$
0
$\begingroup$

Recall that all regular langauges satisfy the pumping lemma, which we capture by the following informal proposition: $$\text{regular}\implies\text{pumping lemma}.$$ Applying modus tollens (a.k.a. contrapositive), we get $$\neg\text{pumping lemma}\implies\neg\text{regular}.$$ Therefore, to prove a language is not regular, it suffices to show that it does not satisfy the pumping lemma. For any regular language $L$, the pumping lemma states the following: $$ \exists p\geq1(\forall w(\left|w\right|\geq p\Rightarrow\exists x,y,z(w=xyz\wedge\left|y\right|\geq1\wedge\left|xy\right|\leq p\wedge\forall i\geq0(xy^{i}z\in L)))) $$ Taking the negation of this statement, $$ \forall p\geq1(\exists w(\left|w\right|\geq p\wedge\forall x,y,z(w=xyz\Rightarrow(y=\epsilon\vee\left|xy\right|>p\vee\exists i\geq0(xy^{i}z\notin L))))) $$ As you can see, we have to show that for all pumping lengths $p$, there exists a word $w$ at least as long as the pumping length $p$ such that for all partitions $w=xyz$, at least one of the following is true: (i) $y$ is the empty string (i.e. $w=xz$), (ii) $|xy|$ is greater than the pumping length, or (iii) there exists an $i$ such that the pumped string $xy^{i}z$ is not in $L$.

If any one of (i) or (ii) is true for a partition, we need not consider it in our proof by contradiction. Therefore, we can look only at partitions for which (i) and (ii) are false, and try to show that (iii) is true. The example on Wikipedia is quite helpful in demonstrating this. It is paraphrased below:

Let $L=\{a^{n}b^{n}\colon n\geq0\}$ be a language, which we will prove to be not regular. Suppose $L$ satisfies the pumping lemma. Let $p$ be an arbitrary pumping length. Let $w=a^{p}b^{p}$, and note that $|w|\geq p$. Let $w=xyz$ be an arbitrary partition of $w$. Suppose $y$ is not empty and $|xy|\leq p$. Since $|xy|\leq p$ and $w=a^{p}b^{p}$, $y=a^{k}$ for some $1\leq k\leq p$. We can now "pump" to conclude that $w^\prime=xy^{2}z$ is a word in the language $L$. This is, however, a contradiction, since $w^\prime$ has more $a$ characters than $b$ characters.

$\endgroup$
  • $\begingroup$ So always it is sufficient to check (iii) ? Why didn't you check (i) or (ii) in example ? $\endgroup$ – user343207 Jun 27 '16 at 11:05
  • $\begingroup$ Fix a partition $w=xyz$. If any one of (i) and (ii) are true, then $y=\epsilon\vee\left|xy\right|>p\vee\exists i\geq0(xy^{i}z\notin L)$ is true. Therefore, suppose neither (i) nor (ii) are true, we need to show (iii) to show that the statement is true. $\endgroup$ – parsiad Jun 27 '16 at 14:35
  • $\begingroup$ What about version for CFG languages ? $\endgroup$ – user343207 Jun 27 '16 at 20:57
  • $\begingroup$ You would just take the negation of the statement on this page: en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages $\endgroup$ – parsiad Jun 27 '16 at 21:06

Your Answer

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