# DFA worst case states

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_1a_2a_3.....a_n and b_1b_2b_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 language of words that have a $1$ in the $n$-th position can be recognized by a DFA with $n+2$ states. – Brian M. Scott Apr 12 '13 at 18:28
• @BrianM.Scott It's n-th from last, so for equivalent DFA it must have 2$^n$ states. – greendragons Apr 12 '13 at 18:36
• Ah, okay, but then you need to change the description: ‘last $n$-th’ does not mean ‘$n$-th from last’. – Brian M. Scott Apr 12 '13 at 18:42
• @BrianM.Scott Sorry mistake is mine. – greendragons Apr 12 '13 at 18:46
• No problem! ${}{}{}{}$ – Brian M. Scott Apr 12 '13 at 18:48

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.
• I understand that from subset construction, it'll have 2$^n$ states, how to prove it taking string w, |w| > n. – greendragons Apr 13 '13 at 17:29
• I am asking how to prove(formally not intuitively) it that for string greater than n, requires 2$^n$ states if n-th from last symbol is 1. – greendragons Apr 13 '13 at 18:54