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.


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

  • $\begingroup$ I understand that from subset construction, it'll have 2$^n$ states, how to prove it taking string w, |w| > n. $\endgroup$ – greendragons Apr 13 '13 at 17:29
  • $\begingroup$ Sorry, I don't understand your question (if it is a question). $\endgroup$ – Tara B Apr 13 '13 at 18:43
  • $\begingroup$ 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. $\endgroup$ – greendragons Apr 13 '13 at 18:54
  • $\begingroup$ Do you understand it intuitively, for a start? (In your original question, you didn't seem to believe it was true, so I guess at least at that point you hadn't understood it intuitively.) $\endgroup$ – Tara B Apr 13 '13 at 19:21
  • $\begingroup$ your answer was useful so did i mark it. It gave me insight to case length greater than n. $\endgroup$ – greendragons Apr 13 '13 at 19:39

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.