So i am given this language:
L = { $c^ma^nb^n $ | $m≥ 1 $ and $n≥ 0$ } U { $a^mb^n$ | $m,n≥ 0$ }
And i have to prove that the pumping lemma property works on L.
Although pumping lemma can work, i then have to prove that L is not a Regular language.
Can anyone help me into proving this thing? And how is it possible that L would not be regular, but pumping lemma property worked?
Best Answer
The easiest way to show that $L$ is not regular is probably to use the Myhill-Nerode theorem, i.e. we have to show that the equivalence relation $$w \sim w' \text{ iff for all } x \in \Sigma^\ast, wx \in L \Leftrightarrow w'x \in L$$ has infinitely many equivalence classes.
Towards this, consider the words of the form $w_n = ca^n$. Now for $n \neq m$ we have that $w_nb^n \in L$ but $w_m b^n$ is not, so in particular we have $w_n \not\sim w_m$, i.e. all equivalence classes associated to the $w_n$ are pairwise distinct for all $n$, and hence the language is not regular as the Nerode relation has infinite index.
Another way would be to assume that $L$ is regular and showing that any DFA $\mathcal A$ for $L$ could be modified to be a DFA $\mathcal A'$ for the language $$ L' = \{c a^n b^n \mid n \in \mathbb N\}$$ which is non-regular, which is (probably) provable using the Pumping lemma. This is a contradiction and hence $L$ cannot be regular.