NFA 示例

示例 1

为以下转换表设计一个 NFA

解决方案

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

此处，

示例 2

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

解决方案

因此，NFA 将会是

示例 3

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

解决方案

具有双 1 的 FA 如下

它应该紧跟着双 0。

然后，

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

因此，NFA 变为

现在考虑字符串 01100011

示例 4

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

解决方案

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

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

上面转换图的转换表如下

考虑字符串 111010,

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

由于状态 q5 是接受状态。 我们得到了完整的扫描，并且我们到达了最终状态。

示例 5

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

解决方案

因此，我们始终从右端获得第三个符号为“0”。 NFA 可以是

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