Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$.

I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the language is regular. Can anyone please tell me that what should I consider it as. And does that happens?


2 Answers 2


$W_1 = \{a^5 . a^*\}$ is a regular language.

$W_2 = \{a^m b^m \mid m\le 5\}$ is a regular (finite) language.

Thus $W = W_1.W_2$ is a regular language.

Something is wrong in your proof.


The key result of finite automata is that deterministic finite automata, nondeterministic finite automata and regular expressions all define exactly the same set of langauges: the regular languages.

So there must be a mistake somewhere. In this case, your pumping lemma proof is wrong because the language is regular. Hint: to accept, you only need to consider whether the number of $a$s is 0, 1, ..., 9, or "10 or more" and whether the number of $b$s is 0, 1, ..., or 5.


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.