2

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!

greendragons
  • 129

1 Answers1

1

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.

Tara B
  • 5,341
  • 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
  • Sorry, I don't understand your question (if it is a question). – Tara B Apr 13 '13 at 18:43
  • 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
  • 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.) – Tara B Apr 13 '13 at 19:21
  • your answer was useful so did i mark it. It gave me insight to case length greater than n. – greendragons Apr 13 '13 at 19:39
  • I added what may be a hint or may have already been clear to you. I don't have time to write any more now, probably for the rest of today (UK time). – Tara B Apr 13 '13 at 19:57
  • I'll work it out later... , by the way sorry for extended conversation, i did not see you edited the answer and added hint there. thanx! – greendragons Apr 13 '13 at 20:01