2
$\begingroup$

Apply pumping lemma to each of these and prove that they are not regular.

$L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$

$L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$

Here my bad attempt at $L$.

Proof: Assume $L$ is regular let $m$ be the number from the pumping lemma.

Let $w = 0^m 1^m 2$ this is clearly in $L$.

By the pumping theorem there exist words $w_1$, $w_2$, $w_3$ such that $w = w_1w_2w_3, |w_2|>0, |w_1w_2| \le m$.

This how far I got; it's not very far but the text is far from clear how to do this.

$\endgroup$
7
  • $\begingroup$ What does the pumping lemma have to say further? $\endgroup$
    – Lord_Farin
    Apr 3 '13 at 7:49
  • $\begingroup$ You mean if I was to keep following my attempt? To be honest the Linz book that I am using makes it into a sort of game. Which makes it sort of hard to follow. My finished attempt would include (for all symbol)i such that (Natural numbers) w1*w2*w3 exist in L. So w2^l = a for some l exist in Natural numbers. With this it is easy however to pick an i such that w1*w2^i *w3 = 0^m * 1^m * 2 does not exist in L $\endgroup$
    – neuroh
    Apr 3 '13 at 7:54
  • $\begingroup$ The "formal statement" on Wikipedia is what you're talking about when you mean the pumping lemma, right? $\endgroup$
    – Lord_Farin
    Apr 3 '13 at 8:15
  • $\begingroup$ But if we let $w = 0^m1^{m-1}2$ with $m$ from the pumping lemma, then $w_1w_2$ as in pumping lemma consists of only zeroes. Hence $w_1w_3 = 0^k1^{m-1}2$ with $k < m$, hence not in $L$. $\endgroup$
    – Lord_Farin
    Apr 3 '13 at 8:42
  • $\begingroup$ @Lord_Farin: Yet another proof of my own illiteracy. ;-) $\endgroup$
    – user642796
    Apr 3 '13 at 8:46
2
$\begingroup$

A fairly complete proof that the first language is not regular.

If it were regular, then by the Pumping Lemma let $p$ be a pumping length for the language. Consider the string $w = \mathtt{0}^p\mathtt{1}^{p-1}\mathtt{2} \in L$. Since $|w| = p + (p-1)+ 1 = 2p \geq p$, by the Pumping Lemma $w$ may be written as $x y z$ where

  • $| x y | \leq p$;
  • $| y | > 0$; and
  • $x y^n z \in L$ for all $n \geq 0$.

Since $| x y | \leq p$, and $xy$ is an initial segment of $w$, it follows that $xy$ must consist entirely of $\mathtt{0}$s, so in particular $x = \mathtt{0}^i$ and $y = \mathtt{0}^j$ for $i,j$ with $i + j \leq p$ and $j > 0$. It also follows that $z = \mathtt{0}^{p-i-j} \mathtt{1}^{p-1} \mathtt{2}$. Note that $x y^0 z \in L$, however $$x y^0 z = xz = \mathtt{0}^i \mathtt{0}^{p-i-j} \mathtt{1}^{p-1} \mathtt{2} = \mathtt{0}^{p-j} \mathtt{1}^{p-1} \mathtt{2},$$ and $p-j \leq p-1$, contradicting that $x y^n z$ belongs to $L$!


The second language can be shown to be non-regular by assuming $p > 1$ is a pumping length for it. (Note that if $p$ is a pumping length for a language $L$ then every $p^\prime > p$ is also a pumping length for $L$, so the assumption $p > 1$ won't affect whether the language satisfies the conclusion of the Pumping Lemma.) Now look at the string $w = \mathtt{a}^p \mathtt{b}^p \mathtt{c}$.

$\endgroup$
2
  • $\begingroup$ Replacing $p$ by $p+1$ in both arguments will avoid the $p > 1$ condition. $\endgroup$
    – Lord_Farin
    Apr 3 '13 at 9:21
  • $\begingroup$ @Lord_Farin: I thought of that, but decided on this formulation. I'm still not certain which is better, though I think I will at least add a small note. $\endgroup$
    – user642796
    Apr 3 '13 at 9:25

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.