Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular?
I believe the answer is NO, but it is hard to make a formal demonstration of it, even a NON formal demonstration :P.
Any ideas on how to approach this?
This language complies with the pumping lemma. I have a formal demonstration of that, so you have to find other ways to prove it not regular. The main idea of the demonstration is that if you have string that belongs to the language, you can split it in the first character and the rest of the string. By pumping in that character you will always get a string with the same number of ab & ba, it doesn't matter if the first character is a a, b or c. If you have any other ideas, please let me know. Thanks and regards!!, Alex.
Best Answer
Suppose that the language is recognized by an automaton having $n$ states. Consider the $n+1$ words $(abc)^k$ where $k$ ranges from 0 to $n$. By the pigeonhole principle, there are two different words $(abc)^i$ and $(abc)^j$ which produce the same state when read by the automaton.
Since the word $(abc)^i (bac)^i$ is recognized, $(abc)^j (bac)^i$ must also be recognized, which is a contradiction.