s********e
发帖数: 11 | 1 PLEASE, HOMEWORK DURE TOMORROW
1.Give an NFA over a single letter alphabet that rejects some string, but the
length of the shortest rejected string is strictly more than the number of
states.
2. explain clearnly why the following proof is not valid:
claim for every n in the positive integer, there is an n-state NFA that is
not equivelent to any n-state DFA.
proof. Let n be any positive integer, since there are more n-state NFAs than
n-state DFAs, so there must be some n-state NFA that is not si | c*****t
发帖数: 1879 | 2
Impossible :)
Hint: give a counter example by having two different n-states NFAs sharing
the same n-state DFA :).
【在 s********e 的大作中提到】
: PLEASE, HOMEWORK DURE TOMORROW
: 1.Give an NFA over a single letter alphabet that rejects some string, but the
: length of the shortest rejected string is strictly more than the number of
: states.
: 2. explain clearnly why the following proof is not valid:
: claim for every n in the positive integer, there is an n-state NFA that is
: not equivelent to any n-state DFA.
: proof. Let n be any positive integer, since there are more n-state NFAs than
: n-state DFAs, so there must be some n-state NFA that is not si
|
|
