I'm trying to understand how to use a contradiction proof via the Pumping Lemma to prove a language is not regular. Everybody always uses examples like $\{ 0^n1^n | n>=0\}$, where it can be broken up into two parts $xy$ and $z$ and where these parts are different. How can I apply it to a language consisting of the concatenation of 3 identical strings?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Pump the string $s=0^p10^p10^p1$. Then if we write s=$xyz$, where must the $xy$ part live? Argue to a contradiction. It's worth noting that the third $w$ makes no difference here; the same proof would apply to, say, the language $wwwwwwwwww$. $\endgroup$– Rick DeckerCommented Sep 30, 2016 at 17:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let's take the alphabets as a and b in-order to avoid confusion.
Suppose that A1 is a regular language. Let p be the “pumping length” of the Pumping Lemma. Consider the string $s = a^pba^pba^pb$. Note that $s ∈ A1$ since $s = (a^pb)^3$, and $|s| = 3(p + 1) ≥ p$, so the Pumping Lemma will hold.
Thus, we can split the string $s$ into 3 parts $s = xyz$ satisfying the conditions.
i. $xy^iz ∈ A1$ for each $i ≥ 0$
ii. $|y| > 0$,
iii.$ |xy| ≤ p.$
Since the first $p$ symbols of $s$ are all $a’s$, the third condition implies that $x$ and $y$ consist only of $a’s$. So $z$ will be the rest of the first set of $a’s$, followed by $ba^pba^pb$.
The second condition states that $|y| > 0$, so $y$ has at least one $a$. More precisely, we can then say that
$x = a^j$ for some $j ≥ 0$,
$y = a^k$ for some $k ≥ 1$,
$z = a^mba^pba^pb$ for some $m ≥ 0$.
Since $a^pba^pba^pb = s = xyz = a^ja^ka^mba^pba^pb = a^{j+k+m} ba^pba^pb$, we must have that $j + k + m = p$. The first condition implies that $xy^2z ∈ A1$, but
$xy^2z = a^ja^ka^ka^mba^pba^pb$
$ = a^{p+k}ba^pba^pb$
since $j + k + m = p$. Hence, $xy^2z$ not an element of $A1$ because $k ≥ 1$, and we get a contradiction. Therefore, $A1$ is a nonregular language.
