patternMinor
Irregularity of $\{a^ib^jc^k \mid \text{if } i=1 \text{ then } j=k \}$
Viewed 0 times
textirregularitymidthen
Problem
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.
$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.
Solution
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,
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| 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.
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| 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.
Context
StackExchange Computer Science Q#1616, answer score: 7
Revisions (0)
No revisions yet.