I've being trying to understand this statement for quite a long time especially the "number of positions" part, but i can't seem to interpret it correctly.What i understand is that the statement means that there should be two 0's seperated by a number of symbols that are multiples of 4 i-e (0 , 4 , 8 , 16...), according to my understanding the string "01110", should not be in the language as the 0's are seperated by three 1's which is clearly not a multiple of 4, but the solution to the problem i've seen here:


enter image description here

Suggests that "01110" is in the language.

Can someone please help me with understanding what the question statement means?


Your interpretation is correct. It looks to me like the "solution" is wrong (and the solution isn't strictly a DFA).

Assuming you don't mind an NFA (getting a DFA is a bit fiddly, but obviously doable), you can fix the solution by removing the $(q_{4},0) \rightarrow q_{5}$ transition, and adding $(q_{5}, 0) \rightarrow q_{5}$ and $(q_{5}, 1) \rightarrow q_{5}$ transitions.

After some fiddling, it seems like a minimal DFA for this has 23 states... not so much fun.


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.