3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I forgot that requirement. $\endgroup$ – mvw Dec 23 '16 at 12:29
  • $\begingroup$ And now we have the same answer… note that the violation always occurs with $i=0$. $\endgroup$ – gniourf_gniourf Dec 23 '16 at 12:47
  • 1
    $\begingroup$ That is a good sign. $\endgroup$ – mvw Dec 23 '16 at 13:58
  • $\begingroup$ @mvw When i look at it again i'm kind of confused now. Should not be exponents of those u, v be different? because when u put p = 1 then u have aabbbabb which is not true for the given condition since 3 != 2. I think the condition says multiply v by 3 and multiplay u by 2 and get the same amount of b. So you choosed the word which is not from the language ? $\endgroup$ – kvway Dec 23 '16 at 14:10
  • $\begingroup$ $u = bb$, $v=bbb$ then we have $3\cdot 2 = 2 \cdot 3$ which is true statement. $\endgroup$ – mvw Dec 24 '16 at 11:09
3
$\begingroup$

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.

$\endgroup$

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.