3
$\begingroup$

I got a problem to solve, which is to demostrate that the language $L$, given by:

$L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$

  1. Satisfies the pumping lemma.
  2. Is not regular.

For the question 1. I think it would suffice to demonstrate that for all $w \in L$, $w$ can be decomposed in the form $\alpha \beta \gamma$, where $|\beta| \neq 0$, and that every string $\alpha \beta^m \gamma \in L$, where $m \geq 0$, but after that I have no clear what I have to do, because I start thinking about cases, what if I have a string $w \in \{ab^nc^n\mid n \geq 0\}$... I should decompose it the way $\alpha = \epsilon, \beta = a$ and $\gamma = \text{the rest of the string}$ (because if we use $w = ab^0c^0 = a$, $\beta$ will have to be $a$, because we know that $\beta \neq \epsilon$), but in this case $\alpha \beta^m$ may not be in $L$, for example, if we choose $m = 0, \alpha \beta^m \gamma$ won't be in $L$, so I don't know what I'm doing wrong... perhaps I'm making mistakes in several steps.

Now, for the question 2. I don't even have an idea on how to start, if someone would help me I would really appreciate it

$\endgroup$
  • $\begingroup$ Perhaps you would care to define $L$ properly. What does $2$ mean in its definition? If it is supposed to mean that $k \geq 2$, then I think that the pumping lemma does work. $\endgroup$ – Yuval Filmus Apr 16 '15 at 7:26
  • $\begingroup$ possible duplicate of How to prove that a language is not regular? $\endgroup$ – David Richerby Apr 16 '15 at 7:59
  • $\begingroup$ @YuvalFilmus I edited the question as the definition of $L$ did not make sense. I did not use the definition of the existing answer (which I had not read). But I do not think it makes a difference. Hope you agree. $\endgroup$ – babou Apr 16 '15 at 10:42
  • 2
    $\begingroup$ Closely related: Languages that satisfy the pumping lemma but aren't regular? $\endgroup$ – Hendrik Jan Apr 16 '15 at 15:11
2
$\begingroup$

You are not supplying the definition of $L$, so here is one definition which works:

$$ L = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 1 \text{ and } w \in \Sigma^* \text{ doesn't start with $a$} \}. $$

Choose a pumping length of $2$. A word $ab^nc^n \in L$ can be pumped by pumping the $a$ part. A word $aaw$ can be pumped by pumping the $aa$ part. Finally, a word $bw$ or $cw$ can be pumped by pumping the $b$ part or $c$ part.

Your definition seems to be

$$ L' = \{ a b^n c^n : n \geq 0 \} \cup \{ a^k w : k \neq 2 \text{ and } w \in \Sigma^* \}, $$

but for this language the pumping lemma does work. Indeed, apply it to $ab^nc^n \in L'$ for large enough $n$. Then $ab^nc^n = xyz$ so that $|y| \geq 1$ and $xy^iz \in L'$ for all $i \geq 0$. Considering the case $i = 2$, we see that $y = a$ necessarily. But then, taking $i = 0$ we get $xz = b^nc^n \notin L'$.

Perhaps the exercise meant you to use the version of the pumping lemma in which $i \geq 1$ instead of $i \geq 0$.

We can show that $L$ is not regular in many ways:

  1. Use one of the many general versions of the pumping lemma which can force the $b^nc^n$ to be pumped. For example, the general version on Wikipedia states that there exists $p$ such that any word $uwv \in L$ with $|w| \geq p$ can be partitioned as $w = xyz$ so that $|xy| \leq p$, $|y| \geq 1$ and $uxy^iz \in L$ for all $i \geq 0$. Choose $u = a$, $w = b^nc^n$ for $n \geq p$ and $v = \epsilon$, and follow the usual argument.

  2. If $L$ were regular then $L \cap ab\Sigma^* = \{ ab^nc^n : n \geq 1 \}$ would also be regular, and you can prove that it isn't using the usual pumping lemma.

  3. Use the Myhill–Nerode criterion. The words $ab^n$ are pairwise inequivalent, and so $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.