patternMinor
DFA that accepts strings whose 10th symbol from the right end is 1
Viewed 0 times
dfaacceptsthewhosesymbolthatendfromstrings10th
Problem
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?
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 is easy to prove that you need at least $2^{10}$ states. Suppose you need fewer states. Then after feeding $2^{10}$ different sequences of length ten, there exist two sequences ending in the same state. But these two sequences differ at some point, so if you feed the same further symbols (possibly none) to the two sequences, the states will remain equal, but the symbols will differ when becoming the last tenth symbol. So it's wrong, and you need at least $2^{10}$ states. No one can be smarter. Pigeonhole principle.
Context
StackExchange Computer Science Q#159014, answer score: 8
Revisions (0)
No revisions yet.