finite-automata - 为以下语言构建 DFA : all strings that have at least three 0s and at most two 1s

Question

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

Answer 1

这是一个总体思路:

最直接的方法是根据您看到的 1 的数量使用不同的路径来计算您的 0，这样它们彼此“平行”。每当你看到一个 1 时，从路径的一层移动到下一层，然后如果你看到第三个 1，则从最后一层移动到陷阱状态。根据分配的确切性质，你可以压缩这个，但是一旦有了基本布局，您就可以确定它。通常，您可以将第一个 DFA 中的状态与第二个 DFA 中的状态组合起来，以产生较小的最终结果。

Here's a more mathematical explanation :

Constructing automata for the intersection operation.
Assume we are given two DFA M1 = (S1, q(1) 0 , T1, F1) and M2 = (S2, q(2) 0 , T2, F2). These two DFA recognize languages L1 = L(M1) and L2 = L(M2). We want to design a DFA M= (S, q0, T, F) that recognizes the intersection L1 ∩L2. We use the idea of constructing the DFA for the union of languages. Given an input w, we run M1 and M2 on w simultaneously as we explained for the union operation. Once we finish the runs of M1 and of M2 on w, we look at the resulting end states of these two runs. If both end states are accepting then we accept w, otherwise we reject w.

---

构造新的转换函数时，最容易想到的方法是使用状态对。例如，考虑以下 DFA:

现在，我们可以通过同时遍历两个 DFA 来开始组合这些。例如，两者都从状态 1 开始。现在如果我们看到一个 a 作为输入会发生什么？那么，DFA1 将从 1->2，而 DFA2 将从 1->3。那么，在组合时，我们可以说交集将从状态“1,1”(两个 DFA 都处于状态 1)到状态“2,3”。状态 2 是 DFA1 中的接受状态， 状态 3 是 DFA2 中的接受状态，因此状态“2,3”是我们新的 DFA3 中的接受状态。我们可以对所有状态/转换重复此操作并结束:

这有意义吗？

引用:在 this assignment 中找到的图片来自康奈尔大学。