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
Commented May 19, 2013 at 21:25
• Yes. I tried the pumping lemma, without success. I also cannot see any applicable closure properties. And I couldn't get my head round the Myhill–Nerode theorem. Also thanks for the LaTeX. I tried applying it myself, but it split the description akwardly across multiple lines. Commented May 19, 2013 at 21:29
• Probably there should be an additional $0$ loop at $q5$? Commented May 20, 2013 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.". Commented May 20, 2013 at 9:44
• @Juho: "How to prove that a language is not regular"? Step 1: Pick a language that is not regular. That's where such a proof fails in this case. Commented Nov 12, 2017 at 15:30

An answer extracted from the question.

Yes, it is regular; below is an automaton that accepts it.

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

• 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
Commented Jun 18, 2013 at 15:41
• I think you could merge $q_5$ and $q_2$. Is that right? Commented Aug 13, 2013 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.

We can write every string in $$\{0,1\}^*$$ in the form $$0^{i_0} 1 0^{i_1} 1 0^{i_2} \cdots 0^{i_{m-1}} 1 0^{i_m}$$ Here $$i_j \geq 0$$, and $$m$$ is the number of $$1$$s.

The number of copies of $$001$$ is the number of indices $$i_0,\ldots,i_{m-1}$$ which are at least $$2$$.

The number of copies of $$100$$ is the number of indices $$i_1,\ldots,i_m$$ which are at least $$2$$.

We conclude that the number of copies of $$001$$ is the same as the number of copies of $$002$$ iff $$i_0 \geq 2 \Leftrightarrow i_m \geq 2.$$ This leads to the following regular expression: $$0^* + (\epsilon+0)(10^*)^*1(\epsilon+0) + 000^*(10^*)^*1000^*.$$

$$L=\{\epsilon, 0, 1, 01, 10, 010, 101, 00, 000, 0000,..... , 1, 11, 11111,......, 01110, 1001, 00100,.........\}$$ The pattern I can observe here is whenever we see a '001' as a substring then it has to be followed by 00 to make $$n(001)=n(100)$$ and whenever we see '100' as a substring then it has to be followed by 1 to make it '1001' to make $$n(100)=n(001)$$

• Please tell me if I'm going wrong somewhere Commented May 10, 2020 at 12:45
• I'm having a hard time seeing how this answers the question. The question was, "is L regular?" A good answer should presumably say either "yes" or "no" and then provide justification for its answer. I can't tell whether you are trying to say that L is regular or L is not. If you just wanted to describe a pattern you observed, that does not count as an answer to the question and should not be posted in the 'Your Answer' box. (We want you to provide useful answers to other questions before you can leave incomplete observations in the comments.)
– D.W.
Commented May 14, 2020 at 17:58
• Also there is a picture of an automaton but with no explanation of what that is supposed to mean. We seek answers that come with explanation and/or justification. If you can edit your question to expand on these points, please do so.
– D.W.
Commented May 14, 2020 at 17:59
• isn't it obvious that if a language is regular then a FA exists for it? Commented May 15, 2020 at 3:55
• Please don't answer in the comments. Instead, edit your question to improve it based on the feedback here. Your question was flagged for possible deletion, so I'm offering some suggestions for how it can be improved. Personally, I prefer to see answers improved instead of deleted. It might help to make explicit the things that you find obvious. Also, it might help to explain why that automaton correctly recognizes the language, if there's a reasonable way to do that.
– D.W.
Commented May 15, 2020 at 5:04

Several years ago I and several colleagues generalized when the language of all strings with equal number of $$x$$ and $$y$$ substrings over an alphabet $$\Sigma$$ is regular: https://arxiv.org/abs/1804.11175. The condition depends on whether $$x$$ is "interlaced" by $$y$$ or vice versa. For $$x$$ to be "interlaced" by $$y$$, it must be the case that $$x$$ is a substring of every string in $$\Sigma^\star$$ that starts and ends with $$y$$. We also give a construction whenever the condition is satisfied.

In the case of $$x=001$$ and $$y=100$$ over $$\Sigma = \{0,1\}$$, every string that starts and ends with $$y=100$$ must have the form $$100\cdots100$$. No matter what, $$x=001$$ is a substring of it. Therefore, this language is regular.