Search code examples
automatadfadeterministicnfaautomata-theory

DFA- Set of all strings whose 10th symbol from the right end is 1

Problem is "Constructing a Dfa accepting set of all strings whose 10th symbol from the right end is 1 over {0,1}"

The NFA is easy

(0+1)*1(0+1)^9

, but DFA has to have minimum 2^10 states. I've tried to see the pattern by constructing 2nd and 3rd symbol from the right.

I mean, when it is the 2nd from the right we need 4 states checking the remainders, and it has 2 final states; when it is 3, we check for the remainders of 8 and it has 4 final states.

Therefore, we can observe that 10th symbol one will have 2^10 states checking the remainders of 2^10 and it will have 2^9 final states. Besides that, I cannot see a way to visualize it graphically as it is asked in the question. Anyone brighter?

Solution

  • It would be hard to draw the DFA or list its states and transitions explicitly, but we can describe the construction in a pretty compact form:

    1. the DFA will have 2^10 states called qK for 0 <= K < 1024 (in these states, the binary digits d1, d2, ..., d10 encode whether the DFA will accept after 0, 1, ..., 9 additional symbols of input).

    2. the initial state is q0 and corresponds to not being able to accept after seeing any number of additional symbols (until we see the obligatory 1)

    3. the accepting states are q512 - q1023, inclusive, since in these states, we saw a 1 ten symbols earlier

    4. in state qK where K = d1.d2.d3.d4.d5.d6.d7.d8.d9.d10, we will transition to qK' where K' = d2.d3.d4.d5.d6.d7.d8.d9.d10.x on input symbol x

    5. alphabet is {0, 1}

    This doesn't give the DFA in extensive form, but it correctly and unambiguously defines the minimal DFA for this language.

    EDIT: Elaboration on step #4

    Step #4 defines the transition function for the DFA by specifying a rule according to which inputs to the DFA cause it to change state. The idea is this: each of the 1024 states corresponds to a 10-bit integer between 0 and 1023, inclusive. the binary representations of these numbers are 0000000000, 0000000001, ..., 1111111111. We may interpret each of these digits to encode whether the DFA should be in an accepting state after a number of additional input symbols corresponding to the digit's position in the array.

    So, if we call the digits (from high-order to low-order) d1, d2, ..., d10, then if d1 = 1, that means we can halt after zero additional input symbols (i.e., the current state is accepting). If d2 = 1, we can also halt if we see one additional input symbol. And so on. Another equivalent way to think about it is this: d(n) = 1 if and only if the symbol we saw (11 - n) symbols ago was 1. So, this keeps track of the most recent 10 symbols we've seen (that is why each transition goes to the state that shifts them all up by a factor of two) and by remembering that, we can always accept when necessary.