# Is the language of words containing equal number of 001 and 100 regular?

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.

• Did you see How to prove that a language is not regular? – Juho May 19 '13 at 21:25
• Why can't you answer your own solution? – Yuval Filmus May 19 '13 at 23:45
• @YuvalFilmus There's a delay for low-reputation users to answer their own question (8 hours if rep < 100). – Gilles May 20 '13 at 5:39
• Probably there should be an additional $0$ loop at $q5$? – Hendrik Jan May 20 '13 at 9:41
• A similar example of this phenomenon, but for the substrings "01" and "10" was discussed at our sister site Proving a language is regular or irregular. The answer has a similar remark as wece made in his comment: "That is, a 01 transition cannot be followed by another $01$ transition without an intervening $10$ transition.". – Hendrik Jan May 20 '13 at 9:44

An answer extracted from the question.

As pointed out by Hendrik Jan, there should be an additional 0 self-loop at q5.

• this is a construction, not a proof – vzn Jun 18 '13 at 15:24
• in CS classes for simple problems sometimes just DFAs are given, but it doesnt prove that it exactly accepts the language. you have to [somehow] show for every input string it functions correctly. "how does it work?" – vzn Jun 18 '13 at 15:41
• I think you could merge $q_5$ and $q_2$. Is that right? – J.-E. Pin Aug 13 '13 at 16:28

It's a trick question. Try constructing a string that contains two 001 and doesn't contain a 100, and see why you can't do it. If X = "number of 001", and Y = "number of 100", then X = Y or X = Y ± 1.

Once you realise the trick, it becomes highly unlikely that the language is irregular, and then constructing a DFA is quite simple. There are only 8 states with their transitions if the next symbol is 0/1:

State S0: Input is empty. -> S1/C0

State S1: Input is 0. -> C2/C0

State A: Y = X + 1, input ends in 00. -> A/C0

State B0: X = Y + 1, input ends in 1. -> B1/B0

State B1: X = Y + 1, input ends in 10. -> C2/B0

State C0: X = Y, input ends in 1. -> C1/C0

State C1: X = Y, input ends in 10. -> A/C0

State C2: X = Y, input ends in 00. -> C2/B0


The initial state is S0, and S0, S1, C0, C1, C2 are accepting states.