patternModerate
Does the smallest DFA equivalent to this NFA requires at least $O(2^n)$ state?
Viewed 0 times
thissmallestdfatheequivalentnfarequiresstatedoesleast
Problem
The wikipedia page Powerset construction says that the DFA equivalent to this $(n + 1)$-state NFA (with $n=4$ here) "requires $2^n$ states, one for each $n$-character suffix of the input".
I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.
But I can find a very much smaller DFA equivalent to this NFA just below:
Is Wikipedia wrong? Or am I? (which is much more likely)
I understand that the author wants to say that the smallest DFA equivalent to this NFA needs at least $2^n$ states.
But I can find a very much smaller DFA equivalent to this NFA just below:
Is Wikipedia wrong? Or am I? (which is much more likely)
Solution
The NFA accepts strings where the fourth letter from the end is 1. Your DFA doesn't accept 11000.
A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.
A DFA doesn't know how much input is left, so the property "the fourth character from the end" is difficult. You need to remember the last four characters to know whether it was a 1 or a 0 once you reach the end of the string. To do so you need a state for each possible combination of the last four characters, so 2^4 states. If you look hard at the DFA the Wikipedia gives you should be able to figure out which of the states stores which combination of characters.
Context
StackExchange Computer Science Q#68794, answer score: 10
Revisions (0)
No revisions yet.