Pumping Lemma problem

Question

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.

Answer 1

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}$.