GATE | GATE CS 2018 |问题26

让N成为一个有N个州的NFA。设k是一个等价于N的最小DFA的状态数。下列哪一项必然成立？

（A） K≥ 2. ^N （B） K≥ N （C） K≤ N ^2. （D） K≤ 2. ^N 答复: （D） 说明： 当我们只有起始状态时，DFA中的最小状态数将为1，而所有其他状态都无法从stating state到达。 DFA中的最大状态数为2 ^N 作为最坏情况下具有n个元素的集合的子集数。

因此，k≤ 2. ^N 选项（D）是正确的。

相关问题—— 大门| 2008年大门|问题6 这个问题的小测验