As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible.
The required DFA is :
"The set of the strings with equal number of 0 and 1 such that for each prefix the difference between the number of 0's and the number of 1's is minor(<) than 2".
Maybe I've misread the requirements I've thought of them as follows :
by prefix I thought of all the strings with length < than the original one, for example in my opinion the prefixes for "cat" are "c" and "ca" but not "cat";
- "the difference between the number of 0's and the number of 1's is minor(<) than 2" by this i thought that we should have (number of 0 - number of 1) < 2, but now I'm realazing that even (number of 1 - number of 0) < 2 should be fine.
One user suggested to do this :
"Note that you can build a simple DFA which checks if the difference between the number of ones and the number of zeroes never exeeds 2 for any prefix of the input string: Add accepting states qk for −2≤k≤2 (where q0 is the initial state) and a rejecting sink state qs with transitions qk→qk+1 via 1 and qk→qk−1 via 0 for appropriate values of k and qk→qs for the other values."
but I don't understand quite well what it means, I've tried some solutions on my own and they don't work properly :
Any possible solutions? EDIT The DFA should be impossible as a matter of fact : here is the explanation