13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Did you see How to prove that a language is not regular? $\endgroup$ – Juho May 19 '13 at 21:25
  • 2
    $\begingroup$ Why can't you answer your own solution? $\endgroup$ – Yuval Filmus May 19 '13 at 23:45
  • 1
    $\begingroup$ @YuvalFilmus There's a delay for low-reputation users to answer their own question (8 hours if rep < 100). $\endgroup$ – Gilles May 20 '13 at 5:39
  • 1
    $\begingroup$ Probably there should be an additional $0$ loop at $q5$? $\endgroup$ – Hendrik Jan May 20 '13 at 9:41
  • 1
    $\begingroup$ 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.". $\endgroup$ – Hendrik Jan May 20 '13 at 9:44
3
$\begingroup$

An answer extracted from the question.

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

automaton

$\endgroup$
  • $\begingroup$ this is a construction, not a proof $\endgroup$ – vzn Jun 18 '13 at 15:24
  • $\begingroup$ 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?" $\endgroup$ – vzn Jun 18 '13 at 15:41
  • 2
    $\begingroup$ I think you could merge $q_5$ and $q_2$. Is that right? $\endgroup$ – J.-E. Pin Aug 13 '13 at 16:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.