Prove that the language is not regular using pumping lemma

Question

Could anyone explain me how to prove that this language is not regular using pumping lemma? I can prove easier examples but with this one I do not even know with which word i should start proving it.

$$ L = \left\{ aavau \mid u,v \in \{b,c\}^* \wedge 3\lvert u \rvert_b = 2 \lvert v \rvert_b \wedge \lvert v \rvert > 1 \right\} $$

Answer 1

We assume $L$ is regular. Then by the pumping lemma we have a constant pumping length $p \ge 1$, on which the granted split $$ aavau = x y z $$ for all word $aavau \in L$ with $\lvert aavau \rvert \ge p$ will feature repetition within the first $p$ symbols in the sense of $$ \forall i \in \mathbb{N}_0: \, x y^i z \in L \quad (*) $$ where $\lvert x y \rvert \le p$ and $\lvert y \rvert \ge 1$.

$u$ and $v$ will feature only non-$a$ symbols, $v$ at least one, $u$ might be empty.

Let us examine the word $$ w = aa\underbrace{b^{3p}}_va\underbrace{b^{2p}}_u\in L $$ We have $\lvert w \rvert = 3 + 5p \ge p$, so the pumping lemma will grant the split $$ w = x y z $$

If $y$ contains an $a$, then $y^4$ will contain at least four of them breaking the $aavau$ pattern with exactly three $a$ symbols.

If $y$ contains a $b$ then $y$ will contain

1. just part of the first group $b^{3p}$ or
2. just part of the second group $b^{2p}$ or
3. parts of both groups.

In the first or second case, repetition $y^i$ will affect only one group ($u$ or $v$) and the condition $3\lvert u \rvert_b = 2 \lvert v \rvert_b$, which links the number of $b$ symbols for both $u$ and $v$ will get violated for some $i$.

In the third case, the $a$ between the two groups will be contained in $y$ and thus again the pattern $aauav$ with excatly three $a$ symbols will be violated by $y^i$ for some $i$.

Thus $w \in L$ and $L$ assumed to be regular will imply (via the pumping lemma) that words outside the intended set of $L$ have to be elements of $L$, thus $L$ can not be regular.

Answer 2

Recall the pumping lemma:

If $L$ is a regular language then there exists $p\geq1$ such that for all $w\in L$ such that $\lvert w\rvert\geq p$, $w$ can be written as $w=xyz$ where $\lvert xy\rvert\leq p$, $\lvert y\rvert\geq1$ and for all $n\geq0$, $xy^nz\in L$.

Assume that your language $L$ is regular and let $p\geq1$ be as in the pumping lemma.

• Explain why $w=a^2b^{3p}ab^{2p}\in L$ and why $\lvert w\rvert\geq p$;
• Decompose $w$ as $w=xyz$ with $\lvert y\rvert\geq1$ and $\lvert xy\rvert\leq p$.
  • If $y$ contains an $a$, $xz\not\in L$ since $xz$ will contain less than three $a$'s, yet the words of $L$ contain exactly three $a$'s;
  • Otherwise, $y$ contains no $a$'s and $k$ letters $b$ (with $1\leq k\leq p$, and these letters must hence be consecutive since $y$ contains no $a$'s), and there are two cases: either the $b$'s are within the first group or they are within the second group. In the former case, $xz=a^2b^{3p-k}ab^{2p}\not\in L$ and in the latter case, $xz=a^2b^{3p}ab^{2p-k}\not\in L$.
• Conclusion: it's impossible to write $w=xyz$ with $\lvert y\rvert\geq1$ and $\lvert xy\rvert\leq p$ such that $xz\in L$.

Hence $L$ doesn't fulfill the requirements of the pumping lemma, hence $L$ is not regular.