15
$\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$
6
  • $\begingroup$ Did you see How to prove that a language is not regular? $\endgroup$ – Juho May 19 '13 at 21:25
  • $\begingroup$ 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. $\endgroup$ – Ben Elgar May 19 '13 at 21:29
  • $\begingroup$ Your solution looks right since you don't really have to count in this language. There can't be two $001$ without a $100$ between them. $\endgroup$ – wece May 19 '13 at 22:46
  • 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
5
$\begingroup$

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.

automaton

$\endgroup$
2
  • 2
    $\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
4
$\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$
0
$\begingroup$

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^*. $$

$\endgroup$
0
$\begingroup$

$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)$

enter image description here

$\endgroup$
5
  • $\begingroup$ Please tell me if I'm going wrong somewhere $\endgroup$ – aditi19 May 10 '20 at 12:45
  • $\begingroup$ 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.) $\endgroup$ – D.W. May 14 '20 at 17:58
  • $\begingroup$ 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. $\endgroup$ – D.W. May 14 '20 at 17:59
  • $\begingroup$ isn't it obvious that if a language is regular then a FA exists for it? $\endgroup$ – aditi19 May 15 '20 at 3:55
  • $\begingroup$ 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. $\endgroup$ – D.W. May 15 '20 at 5:04

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.