HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
containingthenumberequalwordsregularlanguage100001and

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#12139, answer score: 6

Revisions (0)

No revisions yet.