I'm stuck trying to implement a DFA to do this. Everything I've tried so far seems to have to be able check the next nine elements to determine if the string terminates. Any tips?

  • $\begingroup$ Indeed, you need an exponential number of states. $\endgroup$ – rici Feb 6 '17 at 17:20
  • $\begingroup$ So is it even possible to define a DFA for this? $\endgroup$ – Andrew Walker Feb 6 '17 at 17:27
  • $\begingroup$ Of course. Start with the dfa for "the second last is 1", $(0+1)^*1(0+1)$ and work up from there until you see the pattern. $\endgroup$ – rici Feb 6 '17 at 17:32

Your idea is correct.

Using the Myhill-Nerode theorem, it can be proven that the DFA for this language with the minimum number of states has $2^{10}=1024$ states.

Firstly, it is easy to see that the language is regular using an NFA of $11$ states. In the start state, have transitions for $0,1$ to itself, and a transition for $1$ to another state. From there, have a single common transition for $0,1$ from a given state to a new state each time. The last state is the final state. Thus, the string is accepted if $10$ characters earlier, the symbol was a $1$, which enabled the strings symbols to enter this "chain".

Your equivalent DFA will need to remember the each of the last $10$ symbols, which give $2^{10}$ combinations. It can be shown that every string using the given alphabet can be divided into $2^{10}$ equivalence classes over this language, one for each combination.

For any two strings over this alphabet, if they have the last $10$ symbols the same, then every string appended will result in either both being accepted by the language or both rejected by the language. They will be accepted if the first symbol is a $1$, and rejected otherwise. So, they are equivalent.

For any two strings whose last $10$ symbols are not the same, there must exist some position where they differ. By simply appending any string such that the resultant string has the symbols from this position at $10$ places from the end, one must be accepted and the other must be rejected. So, they cannot be equivalent.

If the number of symbols are less than $10$, prepend with leading zeroes, and the argument still holds.

Thus, we have $2^{10}$ equivalence classes, and by the Myhill-Nerode theorem, any DFA for this language must have at least $2^{10}$ states.


You can create an NFA easily for such languages whose $n^{th}$ symbol from rigth is specific. You can create a DFA for second and third last symbol 1 from the NFAs. Then I know there is some pattern in $\delta$ and $A$ that can be found easily and you can implement an automaton with 1024 states on a machine.

Take $$Q = \{q_0,q_1,... q_{1023}\}$$
$$\delta(q_i,a) = q_j ,j=(i\%512)*2+a$$
$$A = \{q_0,q_1,...q_{511}\}$$
It looks unconventional but take $q_{1023}$ as initial state.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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