提问人：TheCaeserSalad 提问时间：10/3/2021 最后编辑：TheCaeserSalad 更新时间：10/3/2021 访问量：221
查找具有 2 个条件的 NFA
Finding an NFA with 2 conditions
问：
我正在尝试弄清楚如何编写一个 NFA，它只能接受以下语言，只有 6 个必要的状态：
{w： a 的数量在字母表上是偶数 OR 正好是 2 个 b} ∑={a， b} .
这是我有一个NFA的想法（https://prnt.sc/1ujhoiy）（图片作为链接提供，因为我没有发布图片的代表）。
这个 NFA 有 6 个必需的状态并具有所需的条件，但我不知道如何将 2 个条件放在一起。前面提到的机器适用于简单的组合，例如 、 、 ，但我无法弄清楚如何将两者连接起来，以便输入 、 、 、 成为真。aaaaaabbbaabaaabbbaabbabaaabetc...
先谢谢你。
答：
0赞
Jason Gerard
10/3/2021
#1
您可以先将其解为 2 个单独的 NFA，每个条件 1 个。将它们从初始状态 q0 连接在一起，并对每个状态进行 lambda 转换。
请记住，默认情况下，在计算机科学中，我们使用的 OR 是包容性的，而在英语中，默认情况下 OR 通常是排他性的 OR。这可能有助于在求解时清除一些边缘情况。
评论
0赞
TheCaeserSalad
10/3/2021
是的，这就是我在这里所做的（忽略 q3 是最终状态，这是来自之前的测试）。但是这样做会导致它不接受除了 、 、 等的简单组合之外的字符串......aaaaaabb
0赞
Jason Gerard
10/3/2021
您显示的 NFA 不符合语言要求。仅以第一部分 {w： number of a's is even} 为例，只要有偶数个 a，这个字符串也应该接受字符串中的任何位置的字符 b，但在您的 NFA 中，q1 和 q2 不接受字符 b。尝试使用 b 的过渡更新 NFA 的顶部，使其接受 aab、baab、baabbbb 等
0赞
TheCaeserSalad
10/3/2021
我在尝试查看如何做到这一点时遇到了问题？由于我们（我们的初始状态）也是最终状态，因此我无法从它过渡到（最终状态），否则，字符串将被直接接受。这是我更新的 NFA 这里aabq0q5b
0赞
Jason Gerard
10/3/2021
我认为 a 和 q3 上的 q4->q3 应该是接受状态而不是 q0，看起来它会起作用。
1赞
TheCaeserSalad
10/3/2021
谢谢！我想我在这里的底部想通了。我认为问题在于我想得太难了，并试图让顶部和底部一起工作，而不仅仅是分别做 2 个 NFA。感谢您的帮助！
评论