确定性有限自动机可分性问题
Deterministic Finite Automata divisibility problem
设计一个 DFA，它接受 L = { w 的 'a' 数可被 3 整除，'b' 数可被字母表中的 2 整除 {a,b}}
意识到我们应该在 DFA 中有 3 * 2 = 6 个状态。为什么？因为 a 的数量有 3 个选择（0 或 1 或 2）[考虑 余数] 和 b 数量的 2 个选择（0 或 1 类似）。
让我们将状态命名为 axby 这意味着我找到了 x 个 a 和 y 到目前为止的 b 数。例如，如果我们在 a2b0 中遇到 a，那么我们会转到 a0b0（希望你明白为什么？）。同样 a1b1 ---b---> a1b0 和 a1b1 ---a- --> a2b1。
不用说a0b0就是接受状态。
现在，您所要做的就是绘制各州并继续加入它们。我在这里把它们画在纸上。
设计一个 DFA，它接受 L = { w 的 'a' 数可被 3 整除，'b' 数可被字母表中的 2 整除 {a,b}}
意识到我们应该在 DFA 中有 3 * 2 = 6 个状态。为什么？因为 a 的数量有 3 个选择（0 或 1 或 2）[考虑 余数] 和 b 数量的 2 个选择（0 或 1 类似）。
让我们将状态命名为 axby 这意味着我找到了 x 个 a 和 y 到目前为止的 b 数。例如，如果我们在 a2b0 中遇到 a，那么我们会转到 a0b0（希望你明白为什么？）。同样 a1b1 ---b---> a1b0 和 a1b1 ---a- --> a2b1。
不用说a0b0就是接受状态。
现在，您所要做的就是绘制各州并继续加入它们。我在这里把它们画在纸上。