Prove that the language is not regular using pumping lemma 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\}
$$
 A: 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


*

*just part of the first group $b^{3p}$ or 

*just part of the second group $b^{2p}$ or 

*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.
A: 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.
