Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
$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.
