2.1

:material-circle-edit-outline: 约 182 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟

DFA与NFA的等价与转换

NFA与DFA等价

解决问题的能力方面

DFA都是NFA，因为函数就是一种关系

NFA 能表示更多的传递种类

DFA与NFA等价

什么意思？

NFA转化为DFA

我们先定义一个新集合

\(E(q)\) 表达的是一个状态不消耗任何字母能转移到的所有状态

即只消耗 \(e\) 就能到达的

由 NFA 构建等价 DFA

记 \(M^\prime=(K^\prime,\Sigma ,\delta,s^\prime,F^\prime)\) 为 DFA，\(M=(K,\Sigma ,\Delta,s,F)\) 为 NFA，他们是等价的

则：

• \(K^\prime=2^K\)
• \(s^\prime=E(s)\)
• \(F^\prime=\{Q|Q\subseteq K,Q\cap F\neq\empty\}\)
• 

证明

1. \(M^\prime\) 是确定的

？？？？？？

1. \(M^\prime\) 等价于 \(M\)

断言的证明，数学归纳法：