Problem Detail: I took my theory of computation exams a few weeks ago, and this was one of the questions:
Assume language $L={(a^nb^m)^r mid n,m,rge 0}$ Is L regular? If yes provide a regular expression or an automaton for it.
After I briefly asked him the answer after the exam, it appears it really is regular (I believe he said the expression is the simple $(a^*b^*)^*$). However I cannot seem to understand why that is. The way I see it, its concatenating $a^nb^m$ r times, like this:
$a^nb^ma^nb^ma^nb^m…a^nb^ma^nb^m$,
which isn’t regular since there is no way for an automaton to recall n and m every time. Where am I at fault here? EDIT: I talked to the professor again, he admitted it was a mistake. The language is indeed not regular.
Asked By : Exci
Answered By : Yuval Filmus
The language $L$ is not regular, as can be proved using Nerode’s method. Consider the following words $w_n = a^n b$ for $n in mathbb{N}$. Then $w_n^2 in L$, but for $n neq m$, $w_n w_m notin L$. Hence any automaton for $L$ must be in a different state after reading each $w_n$, which contradicts its finiteness.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/4837
