Designing a DFA that accepts strings such that nth character from last satisfies condition

Question Detail: 

This is a homework question, so I am only looking for hints.

I got a question in an assignment which states :

Design a DFA that accepts strings having 1 as the 4th character from the end, on the alphabet {0,1}

I have been at this for a few hours now, and I think that designing such a DFA is not possible. However, I am not sure how to move forward in this direction to write up a somewhat formal proof.

So, what should I try to do to prove or disprove my hypothesis?

Asked By : AsheeshR

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14008

Answered By : AsheeshR

I first made the NFA and then converted it to a DFA. I ended up with a total of 16 states. I thought that I had probably done something wrong as I ended up with a very large number of states, so I then followed what J.-E. Pin suggested.

I first created a NFA that checks for the last character satisfying a condition and converted it to a DFA. I then repeated this for the second last and third last characters.

What I noticed was that, the number of states in the resulting DFA was $2^n$, where $n$ is the number of states in the equivalent NFA (excluding the initial state) or the position of the character to be checked from the end.

So, if I understand this correctly, the DFA is checking all the possible strings on the input alphabet for the last $n$ characters.

---

So, to answer my own questions :

I have been at this for a few hours now, and I think that designing such a DFA is not possible.

It is.

So, what should I try to do to prove or disprove my hypothesis?

Make a NFA and convert it to a DFA.