幂集构造
維基百科,自由的 encyclopedia
在计算理论中,幂集构造是转换非确定有限状态自动机(NFA)到识别同样语言的确定有限状态自动机(DFA)的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性,它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态,结果的DFA可能有最多2n个状态,这种指数增长有时使这种构造对于大NFA而言是不实际的。
在计算理论中,幂集构造是转换非确定有限状态自动机(NFA)到识别同样语言的确定有限状态自动机(DFA)的标准方法。它在理论上的重要性源于它确立了NFA尽管有额外的灵活性,它不能识别不能被任何DFA识别的任何语言。在实践中的重要性源于它把易于构造的NFA转换成了更有效执行的DFA。但是如果NFA有n个状态,结果的DFA可能有最多2n个状态,这种指数增长有时使这种构造对于大NFA而言是不实际的。