Problem Detail: I was wondering when languages which contained the same number of instances of two substrings would be regular. I know that the language containing equal number of 1s and 0s is not regular, but is a language such as $L$, where $L$ = ${ w mid$ number of instances of the substring “001” equals the number of instances of the substring “100” $}$ regular? Note that the string “00100” would be accepted. My intuition tells me it isn’t, but I am unable to prove that; I can’t transform it into a form which could be pumped via the pumping lemma, so how can I prove that? On the other hand, I have tried building a DFA or an NFA or a regular expression and failed on those fronts also, so how should I proceed? I would like to understand this in general, not just for the proposed language.
Asked By : Ben Elgar
Answered By : Juho
An answer extracted from the question. As pointed out by Hendrik Jan, there should be an additional 0 self-loop at q5. 
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12139
