什么是非确定性有限自动机(NFA)？
非确定性意味着在同一输入符号上从某个状态可能有多个可能的转换。对于给定的输入，输出是不确定的。NFA 可以表示为一个不确定的有限状态机。
NFA可以用5个元组表示（Q,$\sum$,$\delta$,q 0 ,F）
Q 是有限的非空状态集。
$\sum$是一组有限的输入符号。
$\delta$是从当前状态移动到下一个状态的转换函数。
∴ $\delta$:Q x $\sum$→ 2 Q
q 0 ∈ Q 是初始状态。
F \subseteq Q 是最终状态的集合。
Example1 - 为正则表达式 a(a+b)*ab 绘制 NFA
解决方案
Example2 - 为 a + b + ab 绘制 NFA
解决方案
示例3 - 令 M=(Q,∑,$\delta$,q 0 ,F) 为 NFA。证明对于任何 qϵQ 和 ϵ Σ，$\delta$′(q,a)= $\delta$(q,a)
解决方案
令M=(Q,∑,$\delta$,q 0 ,F)为识别语言L的NFA。那么DFA，M′=(Q 1 ,∑,$\delta$′,q′ 0 ,F ') 满足下列条件则认出 L:Q 1 =2 Q，即 Q 的所有子集的集合。
q′ 0 ={q 0 }
$\delta$(q,a)=∪ pϵq $\delta$(p,a) 对于 Q 1中的每个状态 q和 Σand 中的每个符号 a
F={qϵQ 1 |q∩F 2 ≠ф}
为了获得接受相同语言的 DFA M′=(Q 1 ,Σ,$\delta$′,q′0,F′)，如给定的 NFA，M=(Q,∑,$\delta$,q 0， F) 确实如此。它可以进行如下 -
Step1 - 最初 Q 1 =ф
Step2 - 将 {q 0 } 放入 Q 1中。{q 0 } 是 DFA M' 的初始状态。
Step3 - 然后对 Q 1中的每个状态 q执行以下操作：添加这个新状态，添加 δ(q,a)=∪ pϵq δ(p,a) 到 δ，其中右侧的 δ 是 NFA 的米'。
Step4 - 重复 step3 直到在 Q 1 中添加新状态，如果在 Q 1中添加新状态，则该过程消除。
Example4 - 证明如果 L 被具有 ∈-transitions 的 NFA 接受，则 L 被没有 ∈-transitions 的 NFA 接受。
解决方案
假设对于一些没有 ∈-transitions 的 DFA 或 NFA L = L (D)。它可以通过为 D 的所有状态 q 添加转换 δ(q,∈)=ф 将 D 转换为 ∈-DFA (E)。它还可以将 D 在输入符号上的转换，例如，δ D(q,a)=D 转换为NFA 转换到包含唯一 P 的集合，即 δ E (q,a)={P}。因此，E 和 D 的转移是相等的，但 E 明确指出没有转移出 E 的任何状态。
令 E=(Q E ,Σ,δ E ,q 0 ,F E ) 为 ∈-NFA。它可以使用上面表示的修改后的子集构造来制作 DFA。
D=(Q E ,∑,δ E ,q D ,F D )
L(D)= L(E)，因为 E 和 D 的扩展转移函数相等。扩展转换函数是接受状态 q 和字符串 w 并返回状态 P 的函数，状态 P 是自动化在从状态 q 开始并处理输入序列 w 时达到的状态。
δ E (q 0 ,w)=δ D (q D ,w) 由w的长度归纳得出。
以上是 什么是非确定性有限自动机(NFA)？ 的全部内容， 来源链接： utcz.com/z/363285.html
