我将从两个更简单的 DFA 的交集构造一个 DFA。第一个更简单的 DFA 识别所有至少包含三个 0 的字符串的语言，第二个更简单的 DFA 识别最多两个 1 的字符串的语言。字母表是 (0,1)。我不确定如何将两者结合起来构建更大的 DFA。谢谢！
问问题
13321 次
2 回答
7
这是一个总体思路：
最直接的方法是根据您看到的 1 的数量使用不同的路径来计算 0，以使它们彼此“平行”。每次看到 1 时从路径的一层移动到下一层，如果看到第三个 1，则从最后一层移动到陷阱状态。根据分配的确切性质，您可能能够浓缩这个，但是一旦你有了一个基本的布局，你就可以确定它。通常，您可以将第一个 DFA 中的状态与第二个 DFA 中的状态相结合，以产生较小的最终结果。
为相交操作构建自动机。
假设我们有两个 DFA M1 = (S1, q(1) 0 , T1, F1) 和 M2 = (S2, q(2) 0 , T2, F2)。这两个 DFA 识别语言 L1 = L(M1) 和 L2 = L(M2)。我们想要设计一个识别交点 L1 ∩L2 的 DFA M= (S, q0, T, F)。我们使用为语言联合构建 DFA 的想法。给定一个输入 w，我们在 w 上同时运行 M1 和 M2，正如我们对联合操作所解释的那样。一旦我们在 w 上完成 M1 和 M2 的运行，我们就会查看这两个运行的最终状态。如果两个最终状态都接受，那么我们接受 w，否则我们拒绝 w。
在构造新的转换函数时，最容易想到的方法是使用状态对。例如，考虑以下 DFA：
现在，我们可以通过同时遍历两个 DFA 来开始组合这些。例如，两者都从状态 1 开始。现在如果我们看到一个a作为输入会发生什么？那么，DFA1 将从 1->2 开始，而 DFA2 将从 1->3 开始。那么，当组合时，我们可以说交集将从状态“1,1”（两个 DFA 都处于状态 1）变为状态“2,3”。状态 2 是 DFA1 中的接受状态，状态 3 是 DFA2 中的接受状态，因此状态“2,3”是我们新的 DFA3 中的接受状态。我们可以对所有状态/转换重复此操作，并最终得到：
那有意义吗？
参考：康奈尔大学在此作业中找到的图像。
于 2010-10-26T14:40:55.790 回答
0
最简单的方法是使用2DFA模型：从第一个 DFA 的结束状态（测试至少 3 个零的那个）跳转到第二个的开始状态，然后反转到输入的开头。然后让第二个 DFA 测试字符串。
于 2010-10-26T15:06:00.243 回答