Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Question

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.

Any ideas on how to approach this?

Answer 1

It's clearly not regular. How is an FA going to recognize (abc)^n c (cba)^n. Strings like this are in your language, right? The argument is a simple one based on the fact that there are infinitely many equivalence classes under the indistinguishability relation I_l.

Answer 2

The most common way to prove a language is NOT regular is using on of the Pumping Lemmas.

Using the lemma is a little tricky, since it has all those "exists" and so on. To prove a language L is not regular using the pumping lemma you have to prove that

for any integer p,
there is a word w in L of length n, with n>=p,  such that
for all possible ways to decompose w as xyz, with len(xy) <= p and y non empty
there exists an i such that x(y^i)z (repeating the y bit i times) is NOT in L

whooo!

I'l l show how the proof looks for the "same number of as and bs" language. It should be straighfoward to convert to your case:

for any given p, we can make a word of length n = 2*p
a^p b^p (p a's followed by p b's)
any way you decompose this into xyz w/ |xy| <=p, y will only contain a's.

Thus, pumping the the y part will make the word have more as than bs,
thus NOT belonging to L.

---

If you need intuition on why this works, it follows from how you need to be able to count to arbritrarily large numbers to verify if a word belongs to one of these languages. However, Regular Languages are described by finite automata and no finite automata can represent the infinite ammount of states required to represent all the numbers. (The Wikipedia article should have a formal proof).

---

EDIT: It looks like you can't straight up use the pumping lemma in this particular case directly: if you always make y be one character long you can never make a word stop being accepted (aba becoming abbbba makes no difference and so on).

Just do the equivalence class approach suggested by Patrick87 - it will probably turn out to be cleaner than any of the dirty hacks you would need to do to make the pumping lemma applicable here.