NFA的例子

示例1:

为转换表设计一个NFA，如下所示:

解决方案:

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

在这里,

示例2:

设计一个有∑={0,1}的NFA接受所有以01结尾的字符串。

解决方案:

因此，NFA将是:

示例3:

设计一个∑={0,1}的NFA，其中双'1'后面跟着双'0'。

解决方案:

带双1的FA如下:

它后面应该紧跟两个0。

然后,

在双1之前，可以有任何0和1的字符串。类似地，在双0之后，可以有任何0和1的字符串。

因此NFA就变成了:

现在考虑字符串01100011

示例4:

设计一个NFA，其中所有字符串都包含子字符串1110。

解决方案:

该语言由包含子字符串1010的所有字符串组成。部分转换图可以是:

1010可以是子字符串。因此，我们将添加输入0和1，这样就可以维护语言的子字符串1010。因此NFA就变成了:

以上转换图的转换表如下:

考虑一个字符串111010，

卡住了!因为输入符号0没有来自q2的路径。我们可以用另一种方式处理字符串111010。

因为状态q5是接受状态。我们得到了完整的扫描，我们达到了最终的状态。

例5:

设计一个NFA，∑={0,1}接受所有右端起第三个符号始终为0的字符串。

解决方案:

因此，我们从右端得到的第三个符号总是“0”。NFA可以是:

上面的图像是一个NFA，因为在输入0的状态q0下，我们可以进入状态q0或q1。