Make DFA of the set of all strings from {0,1} whose tenth symbol from the right end is a 1

Question

What will be the transition diagram of the set of all strings from {0,1} whose tenth symbol from the right end is a 1 ? I know the regular expression is (0+1)*1(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1)(0+1) But I couldn't turn it into DFA.

Answer 1

I encountered this question in Introduction to Automata Theory, Languages, and Computations by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman.

First, we need to get hold of the NFA here. This would have 11 states in linear formation with the start having a self loop with 0,1 and a transition to the next state with 1 (not 0). All the other 9 transitions from q_i -> q_i+1 would have transition for 0,1 both. The last state, q₁₀ will be our accept state.

That was fairly a straightforward approach for the NFA. Now if we convert this NFA to a DFA considering all 2¹¹ subsets of set of states of the NFA, we would get the solution.

I will add the NFA Diagram when I get some time. And try to figure out an easy trick to solve the DFA without considering all the possibilities.

You can look at Example 1.30 from Introduction to the Theory of Computation - M. Sipser - 3rd Edition at page 51. There they showed an NFA for strings having 1 at the third position from the end would have 4 states but that corresponding DFA would have 8 states. Not posting the screenshots for copyright issues.