Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Aug 14 '11 at 3:42

This question came from our site for theoretical computer scientists and researchers in related fields.

    
Wikipedia claims, that regular languages are closed under inverse homomorphism. I thought about possibility of using this property to replace ab and ba with new symbols d and e respectively and then use pumping lemma. However, I do not see how to avoid problems with the words like aba which belong to L. (If I use f(d)=ab, f(e)=ba, f(a)=a, f(b)=b, f(c)=c then $f^{-1}(L)$ contains not only the words with the same number of d's and e's, which was what I wanted to achieve.) –  Martin Sleziak Aug 14 '11 at 5:38
add comment

3 Answers 3

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.

share|improve this answer
add comment

Let $L$ be the language described in the question. Consider $L' = L \cap \{ (abc)^*ccc(bac)^* \} $. Thus $L' = \{ (abc)^nccc(bac)^n | \; n \in \mathbb{Z} \}$. You can apply pumping lemma straight to $L'$ or use Martin Sleziak's observation to replace $abc$ by $g$ and $bac$ by $h$ to give you $L'' = \{ g^nccch^n | \; n \in \mathbb{Z} \}$ which is obviously not regular. Since intersect and homomorphism preserve regularity, this means the original $L$ was also not regular.

share|improve this answer
1  
+1. Applying the pumping lemma to the intersection is a nice idea. –  Dave Radcliffe Aug 14 '11 at 6:29
add comment

I believe the simplest way of proving this language is not regular is using Myhill–Nerode theorem since it allows you to focus on an "easy" set of words.

Let's define $w_{n} = (abc)^nc$, i.e. $w_n$ has exactly $n$ occurrences of "ab" and no occurrences of "ba" (since after b comes c). Now it's very easy to show that for every pair of words $w_n, w_m$ with $n\ne m$ we have the separating word $z=(bac)^n$ (so that $w_nz$ is in the language but $w_mz$ is not).

share|improve this answer
    
Now I see that this is the essence of Dave's solution as well. –  Gadi A Aug 14 '11 at 13:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.