为以下语言构造DFA:所有至少有三个0且最多两个1的字符串

Question

我将从两个更简单的DFA的交集构建DFA.第一个更简单的DFA识别至少有三个0的所有字符串的语言,第二个更简单的语言DFA识别最多两个1的字符串语言.字母表是(0,1).我不确定如何构建一个更大的DFA结合两者.谢谢!

Answer 1

这是一个大致的想法:

最直接的方法是使用不同的路径来计算0,这些路径基于您看到的1的数量,使它们彼此"平行".每次看到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接受状态.我们可以对所有状态/转换重复此操作,最后得到:

那有意义吗？

参考:康奈尔大学此作业中的图像.