为以下语言构建 DFA：所有至少包含 3 个 0 和最多 2 个 1 的字符串
我将从两个更简单的 DFA 的交集构造一个 DFA。第一个较简单的 DFA 识别所有至少包含三个 0 的字符串的语言，第二个较简单的语言 DFA 识别最多包含两个 1 的字符串的语言。字母表是(0,1)。我不知道如何将两者结合起来构建一个更大的 DFA。谢谢！
I am to construct a DFA from the intersection of two simpler DFAs. The first simpler DFA recognizes languages of all strings that have at least three 0s, and the second simpler language DFA recognizes languages of strings of at most two 1s. The alphabet is (0,1). I'm not sure how to construct a larger DFA combining the two. Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
总体思路如下：
最直接的方法是根据您看到的 1 的数量使用不同的路径来计算 0，以便它们彼此“平行”。每当看到 1 时，就从路径的一层移动到下一层，然后如果看到第三个 1，则从最后一层移动到陷阱状态。根据分配的确切性质，您可能能够压缩此层，但是一旦有了基本布局，您就可以确定这一点。通常，您可以将第一个 DFA 中的状态与第二个 DFA 中的状态组合起来，以产生更小的最终结果。
这里有一个更数学的解释：
在构造新的转换函数时，最简单的思考方法是使用状态对。例如，考虑以下 DFA：
现在，我们可以通过同时遍历两个 DFA 来开始组合这些 DFA。例如，两者都从状态 1 开始。现在，如果我们看到
a作为输入，会发生什么？那么，DFA1 将从 1→2，DFA2 将从 1→3。那么，当组合时，我们可以说交集将从状态“1,1”（两个 DFA 都处于状态 1）变为状态“2,3”。状态 2 是 DFA1 中的接受状态，状态 3 是 DFA2 中的接受状态，因此状态“2,3”是新 DFA3 中的接受状态。我们可以对所有状态/转换重复此操作，并最终得到：这有意义吗？
参考：康奈尔大学的此作业中找到的图片。
Here's a general idea:
The most straightforward way to do this is to have different paths for counting your 0s that are based on the number of 1s you've seen, such that they are "parallel" to each other. Move from one layer of the path to the next any time you see a 1, and then move from the last layer to a trap state if you see a third 1. Depending on the exact nature of the assignment you might be able to condense this, but once you have a basic layout you can determine that. Typically you can combine states from the first DFA with states in the second DFA to produce a smaller end result.
Here's a more mathematical explanation:
When constructing the new transition function, the easy way to think of it is by using pairs of states. For example, consider the following DFAs:
Now, we can start combining these by traversing both DFAs at the same time. For example, both start at state 1. Now what happens if we see an
aas input? Well, DFA1 will go from 1->2, and DFA2 will go from 1->3. When combining, then, we can say that the intersection will go from state "1,1" (both DFAs are in state 1) to state "2,3". State 2 is an accept state in DFA1 and state 3 is an accept state in DFA2, so state "2,3" is an accept state in our new DFA3. We can repeat this for all states/transitions and end up with:Does that make sense?
Reference: Images found in this assignment from Cornell University.
最简单的方法是使用 2DFA 模型：从最终状态第一个 DFA（测试至少 3 个零的那个）跳转到第二个 DFA 的开始状态，并反转到输入的开头。然后让第二个 DFA 测试该字符串。
The simplest way would be using the 2DFA model: from the end state of the first DFA(the one testing for at least 3 zeros) jump to the start state of the second one, and reverse to the beginning of the input. Then let the second DFA test the string.