Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

Problem Detail: 

I read on the site on how to use the pumping lemma but still I don't what is wrong with way I'm using it for proving that the following language is not a regular language:

$L = \{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$

for $i\neq1$ the language is obviously regular but in the case which $i=1$ , we get that the language is $a^1b^nc^n$, now for every division $w=xyz$ such that $|y|>0 , |xy|< p$ where p is the pumping constant I get the word $a^1b^pc^p$ would be out of the language. since $|xy|< p$ , $y$ may contains only $a's$ or $b's$ or both. if $x= \epsilon$ and $y=a$, pump it once and you're out of the language, if it contains only $b's$, pump it once and your'e out of the language, and if it contains both, pump it and you're out of the language again.

so, why does this language considered as not regular and cannot be proved for its irregularity by the pumping lemma? please point out my mistake.

Asked By : Jozef

Answered By : Gilles

The pumping lemma provides a sufficient condition for a language to be non-regular, it is not a necessary condition. This is an example of a language for which the pumping condition holds, so you cannot prove that it is non-regular with (the basic version of) the pumping lemma.

When you see this language definition, you should immediately think of breaking it up: $$ \begin{align*} L &= \{ a^i b^j c^k \mid \text{if \(i=1\) then \(j=k\)} \} = \{ a^i b^j c^k \mid i \ne 1 \vee j=k \} \\ &= \{ a^i b^j c^k \mid i \ne 1 \} \cup \{ a^i b^j c^k \mid j = k \} = (b^*c^* \cup aaa^*b^*c^*) \cup \{ a^i b^j c^k \mid j = k \} \\ \end{align*} $$ This is taking shape: we've expressed $L$ as the union of a regular language with a language that doesn't look regular (it looks a lot like the classical example of a non-regular language ${b^j c^k \mid j=k}$). We need to work a little more if we can hope to prove that $L$ isn't regular, however: the union of a regular language and a non-regular language can be regular (the union operation can "absorb" the irregularity).

So let's take a step back: what's the problem? In the decomposition above, we have the regular case, with words that begin with no $a$ or with $aa$; and we have the irregular case, where we don't know anything about the initial number of $a$'s. Really, the trouble comes from words that begin with a single $a$. If $L$ is regular, then its intersection $L'$ with the regular language $a(b|c)^*$ would also be regular. Well, $$L' = L \cap (a(b|c)^*) = \{ a b^j c^k \mid j = k \}$$ If we prove that this language is not regular, then we'll know that $L$ isn't regular either.

To prove that $L'$ is not regular, the pumping lemma works well, just like for $\{b^j c^k \mid j=k\}$. We no longer have this problem with the unbounded number of $a$'s. If $L'$ is regular, then we can find a pumping decomposition for $a b^p c^p$ where $p$ is the pumping length: $a b^p c^p = xyz$ with $y \ne \epsilon$, $|xy| \le p$ and $\forall i, x y^i z \in L'$.

• If $y$ contains the $a$, then $x z$ contains no $a$, which contradicts $x z \in L'$.
• If $y$ contains an unequal number of $b$'s and $c$'s, then $x z$ does not contain an equal number of $b$'s and $c$'s, which contradicts $x z \in L'$.
• If $y$ contains equal numbers of $b$'s and $c$'s and is not $a$, then $y = b^m c^m$ with $m \gt 0$ since $y$ is not empty. Then $x y^2 z$ contains the substring $c b$, which contradicts $x y^2 z \in L'$.

Applying the pumping lemma to $L'$ leads to a contradiction. Therefore the assumption that $L'$ is regular does not hold. Thus $L$ is not regular.

If you are willing to assume that $\{b^j c^k \mid j=k\}$ is not regular, another method to prove that $L'$ is not regular is to read it off an automaton. Suppose that $L'$ is regular; then there is a finite automaton $\mathcal{A}$ that recognizes it. Let $q$ be the state reached by this automaton on the input $a$, and let $\mathcal{A}'$ be this $\mathcal{A}$ with the initial state changed to $q$. If a word is of the form $a w$, then it is accepted by $\mathcal{A}$ if and only if $w$ is accepted by $\mathcal{A}'$. So the language recognized by $\mathcal{A'}$ is $\{w \mid a w \in L' \} = \{b^j c^k \mid j=k\}$. Since this language is known not to be regular, we have a contradiction; the assumption that $L'$ is regular must be false.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1616