我将从两个更简单的 DFA 的交集构造一个 DFA。第一个更简单的 DFA 识别所有至少包含三个 0 的字符串的语言,第二个更简单的 DFA 识别最多两个 1 的字符串的语言。字母表是 (0,1)。我不确定如何将两者结合起来构建更大的 DFA。谢谢!
2 回答
这是一个总体思路:
最直接的方法是根据您看到的 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 中的接受状态。我们可以对所有状态/转换重复此操作,并最终得到:
那有意义吗?
参考:康奈尔大学在此作业中找到的图像。
最简单的方法是使用2DFA模型:从第一个 DFA 的结束状态(测试至少 3 个零的那个)跳转到第二个的开始状态,然后反转到输入的开头。然后让第二个 DFA 测试字符串。