NFA 转 DFA 的最坏情况是啥样，怎样构造
如果只是要求使用子集构造法的时候出现了所有
个结点的话是容易的，只需要让字符集大小为
，在每个状态，读入对应的字符转移到对应的状态集合就可以了。
如果是要让这个NFA不存在比
个状态更少的DFA的话……有一个经典的例子，但是只能让DFA的状态数达到
……我不知道有没有严格达到上界的例子，反正渐进意义下是一样的对吧（雾
考虑语言
，字符集
，其中
是一个常数。
容易构造它的NFA：从起始状态
开始，可以读入任意字符都转移到自身，也可以猜测这是倒数第
个字符，于是跳转到
。之后状态
无论读入0或1都转移到
。于是
就是接受状态。这个NFA有
个状态。
那么，把这个NFA转化为DFA，如果它的状态数小于
会怎么样呢？根据鸽巢原理，一定存在两个不同的长度为
的串，停在了同一个状态。假设他们在倒数第
位不同，那么只要让它们在接下来读入相同的
个字符，它们仍然停在同一个状态。但因为它们的倒数第
位不同，一定是一个被接受，另一个不被接受。这意味着DFA的这个状态必须既是终止态也是非终止态，于是矛盾。
■网友
假设在一个NFA中有n个state：S1 S2 ... Sn。
那么这些state所组成的集合的powerset就一共有2^n个元素（包括空集）。
那现在定义2^n - 1个symbol分别映射powerset里的非空元素，并把起始state的状态转移函数定义成这个映射。
最后随便选个起始和结束的state就可以了。
【NFA 转 DFA 的最坏情况是啥样，怎样构造】 如此构造的NFA没有任何现实意义，但它确实是最坏情况的一种构造。
推荐阅读
- 《算法导论》第六章 堆排序 维护堆的性质 为啥最坏情况发生在树的最底层恰好半满的时候
- ThinkPad E550 20DFA04ACD装SSD?
- The Hate U Gave Little Infants Fcks Everybody是啥意思
- 秋日林枫道|越南品牌VinFast，推出超豪SUV取名总统，限量发售
- Vinfast LUX|让人眼前一亮的B级轿车，50万外表仅卖17万！奥迪A8L都怕它
- 易车|目标建立知名越南品牌 越南 VinFast 计划将纯电动车出口至美国
- 怎样计算正则表达式之间的包含关系
- 5-10万|最新一批汽车安全碰撞测试出炉，大众奇瑞上榜，最好最坏很意外
- 用有限个栈实现一个队列，保证每个队列操作（在最坏情况下）都只需要常数次栈操作
- 你见过的最好的、最坏的说明书都有哪些都是啥品牌的啥产品呢