非确定性有限自动机的例子 NFA例子|自动机教程

范例1：
为过渡表设计NFA，如下所示：

解：
可以通过使用表中给出的映射函数来绘制过渡图。

文章图片
这里，

δ(q0, 0) = {q0, q1} δ(q0, 1) = {q0, q2} Then, δ(q1, 0) = {q3} Then, δ(q2, 0) = {q2, q3} δ(q2, 1) = {q3} Then, δ(q3, 0) = {q3} δ(q3, 1) = {q3}

范例2：
设计一个∑ = {0，1}的NFA可以接受所有以01结尾的字符串。
解：

文章图片
因此，NFA将是：

文章图片
范例3：
设计一个∑ = {0，1}的NFA，其中双“ 1”后跟双“ 0”。
解：
带有双1的FA如下：

文章图片
应该立即跟在双精度0之后。
然后，

文章图片
现在在double 1之前可以有0和1的任何字符串。类似地，在double 0之后，可以有0和1的任何字符串。
因此，NFA变为：

文章图片
现在考虑字符串01100011

q0 → q1 → q2→ q3 → q4 → q4 → q4 → q4

范例4：
设计一个NFA，其中所有字符串都包含一个子字符串1110。
解：
该语言由包含子字符串1010的所有字符串组成。部分转换图可以是：

文章图片
现在1010可能是子字符串。因此，我们将添加输入0和1，以便可以维护语言的子字符串1010。因此，NFA变为：

文章图片
【非确定性有限自动机的例子】上面的过渡图的过渡表如下：

考虑字符串111010，

δ(q1, 111010) = δ(q1, 1100) = δ(q1, 100) = δ(q2, 00)

卡着了！因为从q2到输入符号0都没有路径。我们可以用另一种方式处理字符串111010。

δ(q1, 111010) = δ(q2, 1100) = δ(q3, 100) = δ(q4, 00) = δ(q5, 0) = δ(q5, ε)

由于状态q5是接受状态。我们得到了完整的扫描，并达到了最终状态。
范例5：
设计一个∑ = {0，1}的NFA，可以接受所有从右端起第三个符号始终为0的字符串。
解：

文章图片
因此，我们从右端得到的第三个符号始终为“ 0”。 NFA可以是：

文章图片
上面的图片是NFA，因为在状态q0和输入0下，我们可以进入状态q0或q1。

非确定性有限自动机的例子