Search code examples
sequencedfa

DFA for odd sequences of 1 and 0

I want to create a DFA for language {1,0} which accepts only words build from sequences of odd 1 and 0. I've found many examples for DFA with even/odd numbers of 0 and 1 in a string but not in each sequence of that string. I cannot grasp how to create said graph. Should it be build with 4 states or maybe 3?

Just thought about something, is this one correct or am I mistaken here? enter image description here

Ok, so this one was wrong, but maybe this one? enter image description here With this one, however, I fell like you always have to start with either one 1 or one 0 and won't get more in the first sequence so it's not relly perfect...

Kind regards,

Solution

  • Give a deterministic finite automaton accepting those words over the alphabet {0, 1}, where each series of zeros and each series of 1s is of odd length.

    Is not 100% unambiguous. I personally understand, that the empty word, and a word consisting solely of 0s or solely of 1s is also part of the language (if it is of odd length). Then something like the following should do the trick.

    State 1 is the starting state. The "upper" branch (ie states 2, 3) is for accepting any odd number of 0, the "lower" branch (ie states 4,5) accepts any odd number of 1. You can "enter" the respective branch only by reading a single instance of the respective symbol, either starting from the empty word, or after reading an odd number of the respective other symbol.

    enter image description here

    For instance the word 1000111110001. After reading a single 1 you are in state 4. By reading a single 0, you switch to the "upper branch" and now can read any even (in this case 2) number of 0, which will always bring you back to the accepting state 2. Reading a 1 in state 3 is not possible (because the word would be invalid). Reading a single 1 in state 2 brings you back to state 4. And from here similar to the above, you can read any even number (in this case 4) of 1 which will always bring you back to the accepting state 4. And so on and so forth. If the symbol changes (or the word ends) after an even number of equal symbols, you are either in state 3 or 5, which are both not accepting, thus the word won't be accepted.