A DFA that depends on a natural number

Question

Given a natural number $m$, I'm asked to find a DFA that accepts the language of words over Σ = {0, 1} such that the $m$th character from the end is 1. (The answer has to depend on $m$) This is a question I was given in one of my homework assignments, therefore I'd really like some hints on this one. Thank you very much!

Answer 1

A DFA that accepts a word in $\{\,0,1\,\}^*$ if the $m$-th input character from the end is $1$ must remember the last $m$ characters that it read. That is, there must be a state for each of the $2^m$ possible words in $\{\,0,1\,\}^*$ of length $m$. While looking at the state graphs of the DFAs for small values of $m$ may not immediately suggest a rule, these automata have a simple, regular structure.

First of all, they can be implemented as shift registers: registers that store the last $m$ input bits that were read. Every time a new bit of input is read, the current bits shift to the left and the new bit is stored in the rightmost position. The oldest (leftmost) bit is lost. The state of the DFA is given by the register's content. Whether the DFA is accepting depends on the oldest bit. The initial state is the one with $0$s in all positions.

Armed with this intuition, if we interpret the contents of the register as a number in base 2, we can then give a simple formula for the next-state function of the DFA. Let the set of states of the DFA be $Q = \{\,0,\ldots,2^{m-1}\,\}$. Let $b$ be the input bit, and let $\delta\colon Q \times \{\, 0,1\,\} \to Q$ be the next state function; then

$$ \delta(q,b) = (2q+b) \bmod 2^m\enspace. $$

You should be able to complete the formal description of the DFA without too much trouble from here.

You should also try to understand the claim I made at the beginning, that these DFAs do need $2^m$ states.