3
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

I cannot see a way to visualize it graphically as it is asked in the question.

It is not necessary nor required of you to visualize or draw a wanted dfa. The exercise only asks you to "construct a DFA accepting ...". The meaning of constructing a DFA is specifying/describing/defining the 5-tuple, $(Q,\Sigma, \delta, q_0,F)$ in the definition of a DFA. Or whatever definition that is used in your course. If you can draw a graph of the DFA, that is great. However, you don't have to unless you are asked specifically to include a graph.

Let us describe a desired DFA as follows.

  • The states $Q=\{q_0, q_1, \cdots, q_{1023}\}$.
  • The alphabet $\Sigma=\{0, 1\}$.
  • The transition $\delta(q_i, \sigma)=q_{(i\%512<<1) + \sigma}$ for any state $q_i$ and any $\sigma\in\Sigma$. Or, what is equivalent, $$\delta(q_{(d_9d_8d_7d_6d_5d_4d_3d_2d_1d_0)_2},\sigma)=q_{(d_8d_7d_6d_5d_4d_3d_2d_1d_0\sigma)_2}$$ where $(d_9d_8d_7d_6d_5d_4d_3d_2d_1d_0)_2$ is the binary representation of the subscript, with some leading $0$s possibly.
  • The initial state is $q_0$.
  • The accept states are $q_{512}, q_{513}, \cdots, q_{1023}$. Put it in another way, a state $q_i$ is an accept state iff the binary representation of $i$ has $10$ digits, with the most significant digit being $1$.

It is straightforward to check the DFA constructed above accepts all strings whose 10th symbol from the right end is $1$ and no other strings.

By the way, the DFA above that has $2^{10}$ states is the minimum DFA wanted, as you have noted. It is a nice example that indicates that the minimum DFA that is equivalent to an $n$-state NFA may require $2^n$ states.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ The answer above uses integers for the subscripts of the states. A more-straightforward way is using binary strings of length $10$ for the subscripts. The initial state will be $q_{0000000000}$. The transition function has been, in fact, described above. The accept states are the states whose subscripts are strings that starts with $1$. $\endgroup$
    – John L.
    Mar 13 at 21:59
8
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

Those state diagrams can be constructed inductively, so it seems. Their structure is (in another context) known as De Bruijn graph.

I sincerely hope you are not actually forced to draw some thousand states though.

Picture below is part of a diagram from the wikipedia page mentioned above (David Eppstein, public domain).

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.