6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Do you mean $L=\{ a^ib^jc^k : (i=1 \text{ & }j=k>=0) \text{ | } (i \neq 1 \text{ & } j,k >= 0)\}$ If so, then here's a hint: your $i\neq 1$ case is correct, and you can take advantage of a language you presumably already know not to be regular, using closure properties of regular languages, without explicitly invoking a pumping lemma. $\endgroup$ May 1, 2012 at 17:03

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

The pumping lemma can only be used to show that a language is not regular, not that it is regular. This is, I think, the fundamental misunderstanding here... that you are unable to use the pumping lemma to prove a language irregular does not constitute a proof of irregularity.

A language is regular if, equivalently,

  • it can be accepted by an NFA
  • it can be generated by a regular grammar
  • it can be described by a regular expression
  • it can be partitioned into finitely many equivalence classes under the indistinguishability relationship (as per the Myhill-Nerode theorem)

This last point can usually be pretty helpful in cases where the pumping lemma fails. Here, you merely need to demonstrate that there are infinitely many equivalence classes for strings in your language; you could argue that strings of the form $ab^nc$ constitute separate classes for all $n$.

Furthermore, as pointed out in the comments, you can often use closure properties of language classes in order to demonstrate that a particular language isn't in the class. For instance, you know that regular languages are closed under intersection. Using that fact, you could show that your language can't be regular, since if it were, the language $ab^nc^n$ would be regular (a contradiction, since you know that language isn't regular... you could even prove this easier version with the pumping lemma).

EDIT: Just in case how to apply the pumping lemma here is unclear, I'll give an example.

Choose the string $uvw = ab^pc^p$. Since $|uv| < p$ and $v > 0$, $v$ must be some non-empty string possibly beginning with a single $a$, followed by multiple $b$'s. If $v$ contains the $a$, pumping will cause there to be a different number of $a$'s, so we get a string not in the language. If the string does not contain the $a$, it consists only of $b$'s, and pumping will cause the number of $b$'s to be different from $n$. The resulting string is not in the language since the number of $b$'s is not equal to the number of $c$'s. Therefore, this string cannot be pumped to another string in the language, a contradiction of the assumption the language was regular; hence, the language is not regular.

$\endgroup$
3
  • $\begingroup$ Must have added my answer in parallel. I need to stop leaving these windows open. : P +1 for Myhill-Nerode for nonregularity proofs, though! $\endgroup$
    – Lucas Cook
    May 2, 2012 at 5:35
  • $\begingroup$ I see. I don't think exhibiting how PL works on another language is more helpful than providing a link to our reference question. $\endgroup$
    – Raphael
    May 2, 2012 at 19:45
  • $\begingroup$ @Raphael I only did the example since I mentioned using the PL on that language in my answer... it's not just some random language. Since it's an organic part of the answer, I's say it's distinctly more helpful than linking to unrelated examples of using the PL. $\endgroup$
    – Patrick87
    May 2, 2012 at 19:55
6
$\begingroup$

I'm assuming that the language is like David Lewis posted in the comments. $$L=\{ a^ib^jc^k : (i=1 \text{ & }j=k>=0) \text{ | } (i \neq 1 \text{ & } j,k >= 0)\}$$

This language is not regular, but cannot be proven non-regular using the standard version of the regular pumping lemma (as seen in the Sipser text or on wikipedia) because you can always pump the first character. If your division is $w = xyz$, let $x = \epsilon$ and $y$ be the first character. This division will always meet the constraints of the pumping lemma, since:

  • If $y = b$, pumping doesn't matter because the number of $a$'s is zero so $j$ can be different than $k$.
  • If $y = a$, pumping doesn't matter because turns the string from the case $(i=1 \text{ & }j=k>=0) $ to $(i \neq 1 \text{ & } j,k >= 0)$.

(This is why the pumping lemma is not an "if and only if" statement. There are languages that meet the pumping lemma's criteria but are still not regular.)


To prove that the language is not regular, use closure properties. An intersection and a homomorphism / substitution will turn it into $\{0^n 1^n ~:~ n \geq 0\}$ easily.

Alternatively, you can use a generalized version of the pumping lemma that allows you to focus on a chosen substring of length $p$ or more.

$\endgroup$
2
  • 1
    $\begingroup$ the pumping lemma has several variants. The above $L$ cannot be proven not-regular only using the simple (and most common) pummping lemma, but can be proven using a more general version of the pumping lemma (in which the part you pump needs not be in the beginning, but can be anywhere in $w$). $\endgroup$
    – Ran G.
    May 2, 2012 at 2:53
  • $\begingroup$ @RanG. Yes, thanks for noting that. I'll modify the answer. I went with the simple standard one (as on wikipedia or the Sipser text). $\endgroup$
    – Lucas Cook
    May 2, 2012 at 5:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.