115 views

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

closed

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

## Related questions

1
140 views
$L^{*}-\{{\epsilon }\}=L^{+}$. True or False? (Given L is a language)
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