Suppose an NFA which accepts language of the form L(N) = {w| w has 1 in n$^t$$^h$ from last symbol.} Then the corresponding DFA would have 2$^n$ states(worst case of subset construction). If we are to prove that equivalent DFA has 2$^n$ states, then we take 2 string as a$_1$a$_2$a$_3$.....a$_n$ and b$_1$b$_2$b$_3$....b$_n$ and consider two cases:
1) a$_i$ $\neq$ b$_1$, i=1. this case is clear to me....
2) a$_i$ $\neq$ b$_i$ , i>1. I am having trouble in understanding this case. If both a$_i$ and b$_i$ has same value for n$^t$$^h$ symbol from last, then automaton would be in accepted state after reading a$_n$ and b$_n$. So why do we need to remember every possible string sequence for this case.
Thanx!
The difficulty is that you don't know until you get to the end which symbol is the $n$-th from last. To understand what is going on, you need to think about how the automaton should process strings of more than $n$ symbols, rather than of exactly $n$ symbols as you seem to be doing.
As a hint to hopefully help you come up with a formal proof: Think about what information you need to remember as you are processing a string. You need to remember every $1$ you see, and how far 'back' in the string you saw it, in case it turns out to have been in the $n$th-from-last position. Except you can forget any information from before the most recent $n$ characters of the string, since any $1$ read before then can't possibly be the $n$th-from-last symbol.