Log In
0 votes

Consider the following language:

L = {w| w $\epsilon$ {0,1}* ; w has equal number of occurances of ‘001’ and ‘010’ }

The solution they provided: The absolute difference between the number of occurrences of ‘001’ and ‘010’ is at most 1. Hence a DFA can be found.

I did not get the solution. How is it possible? How do we maintain the count of the occurrences of any of these strings?

One approach I did think: To move forward if we get ‘001’ and move backward if we encounter ‘010’. But still, this approach will work only if I know in advance that “after a maxm of X occurrences of ‘001’, I am definitely going to find an occurrence of ‘010’ (and vice-versa)). But, since such info is not given, so how this can be a regular language?

closed as a duplicate of: made easy test series
in Theory of Computation
closed by

1 Answer

0 votes
Best answer
When you write 001 twice 001001 there is 010 in between. If you write 010 twice 010010 you get 001 in between. So if you write n times anyone of the pattern the other pattern can be found either n+1 times or n times or n-1 times. You can construct nfa for this.

selected by

Related questions

4 votes
2 answers
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
asked May 26, 2019 in Theory of Computation Hirak 547 views