Pumping Lemma to prove language not regular, formatting $x$

30 Views Asked by At

I need help with a question/verification I'm even thinking about it correctly.

I'm trying to use the PL to prove $L$ is not regular. $L = \{\{a,b,c\}^* \mid |a| < |b| \wedge |a| < |c|\}$. This is what I've done so far:

$$s = \boldsymbol b^j \boldsymbol a^k \boldsymbol c^p \text{ where } j,p>k$$

$$x = b^j, y = a^k, z=c^p$$

I don't really understand how to to pick the exponent variables correctly, but my last logical step was stating that it $j=2, p=2, k=1$ ($bbacc$) and it were pumped $2$ times then the string would be $bbaacc$ which isn't a member of $L$, therefore since it could not be pumped for all length, $L$ was not regular

1

There are 1 best solutions below

0
On

Your definition of $L$ makes absolutely no sense as written. I suspect that you mean that

$$L=\big\{w\in\{a,b,c\}^*:|w|_a<|w|_b\text{ and }|w|_c<|w|_b\big\}$$

and will proceed on that assumption. To use the pumping lemma to show that $L$ is not regular, suppose that $L$ is regular and let $p$ be the pumping length. Let $s=a^pb^{p+1}$; then $|s|_a=p$, $|s|_b=p+1$, and $|s|_c=0$, so $s\in L$. The pumping lemma then says that $s$ has at last one decomposition $s=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. The pumping lemma does not allow you to pick $x,y$, and $z$: all that you are allowed to assume about them are that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$.

However, since we know that $|xy|\le p$, we know that $xy$ lies entirely within the first $p$ characters of $s$, i.e., within the string of $p$ $a$s. Thus, there must be non-negative integers $r$ and $s$ such that $x=a^r$ and $y=a^s$, where $r+s\le p$. Moreover, we know that $|y|\ge 1$, so $s\ge 1$. Of course $z$ must be the rest of $s$, so $z=a^{p-r-s}b^{p+1}$.

The pumping lemma says that $xy^kz\in L$ for each $k\ge 0$, so

$$xy^kz=a^ra^{ks}a^{p-r-s}b^{p+1}=a^{p+(k-1)s}b^{p+1}\,.$$

If we pump $s$ up to $xy^2z$, taking $k=2$, we get $xy^2z=a^{p+s}b^{p+1}$. And $s\ge 1$, so

$$\left|xy^2z\right|_a=p+s\ge p+1=\left|xy^2z\right|_b\,,$$

and therefore $xy^2z$ is not in fact in $L$: it does not have more $b$s than $a$s. This contradiction shows that $L$ cannot have been regular in the first place.