结合确定性有限状态自动机

Question

我很陌生这些东西，所以在这里请原谅我的新手操作。

构建一个识别以下语言的确定有限自动机：Deterministic Finite Automaton DFA。

L= { w : w has at least two a's and an odd number of b's}. 

每个部分的自动化（至少有2个a，奇数数量的b）都很容易单独制作......有人能否解释一种将它们组合成一个的系统方法？谢谢。

- Haskell

Answer 1

您可以使用以下简单步骤构建组合DFA。

设 Σ = {a₁ , a₂ , ...,a_k }。
第1步: 为两种语言设计DFA，并将它们的状态命名为Q₀, Q₁, ...

第2步: 为两个DFA中的每个状态重新命名，即将DFA中的所有状态重命名为Q₀, Q₁, Q₂, Q₃等，假设您从下标0开始；这意味着没有任何一个状态会有相同的名称。

第3步: 使用以下步骤构建转换表(δ)

   3a. 合并DFA的起始状态：
      取两个DFA(DFA1 和 DFA2) 的起始状态，并将它们命名为Q_{[ i , j ]}，其中i和j是DFA1和DFA2的起始状态下标，即Q_i是第一个DFA的起始状态，Q_j是第二个DFA的起始状态，并将Q_{[i, j]}标记为合并DFA的起始状态。

   3b. 映射两个DFA的状态为：
           如果δ(Q_i,a_k) = Q_p1，且δ(Q_j,a_k) = Q_p2，其中Q_p1属于DFA1，Q_p2属于DFA2，则δ(Q_{[ i , j ]} , a_k) = Q_[p1,p2]

   3c. 在转换表中填充整个表格，直到没有Q_[i,j]剩余。

   3d. 合并DFA的最终状态：
      对于AND情况，最终状态将是所有Q_{[i , j]}，其中Q_i和Q_j分别是DFA1和DFA2的最终状态。
      对于OR情况，最终状态将是所有Q_{[i , j]}，其中Q_i或Q_j是DFA1和DFA2的最终状态之一。

第4步： 重新命名所有Q_{[i, j]}（唯一）并绘制DFA，这将是您的结果。

示例：

L= {w: w has at least two a's and an odd number of b's}.

步骤1：
奇数个b的DFA。

至少有2个a的DFA。

步骤2：
重命名DFA1的状态。

步骤3（a,b,c）：
构建的转移表如下。

步骤3d：
由于我们需要对两个DFA进行AND操作，因此最终状态将是Q_[2,4]，因为它包含了两个DFA的终止状态。
如果我们需要对两个DFA进行OR操作，则最终状态将是Q_[0,4]，Q_[2,3],Q_[1,4],Q_[2,4]。
添加终态后的转移表如下。

步骤4：
将所有状态Q_[i,j]重命名。
Q_[0,3] 重命名为 Q₀
Q_[1,3] 重命名为 Q₂
Q_[0,4] 重命名为 Q₁
Q_[2,3] 重命名为 Q₄
Q_[1,4] 重命名为 Q₃
Q_[2,4] 重命名为 Q₅
因此，最终的DFA如下所示。

- sonus21

---

你能解释一下这背后的科学原理吗？正则表达式是什么？ - HessamSH

Answer 2

当 a 至少有两个且 b 为奇数时，语言 L 是一种正则语言。它的 DFA 如下所示：

在这个 DFA 中，我在概念上结合了两个 DFS！

DFA-1 = for odd number of `b`'s (placed vertically three times in diagram)
DFA-2 = for >=  two a           (placed Horizontally two times in diagram)

_{这个DFA太症结和简单了，所以我认为没有必要在意如何将两个DFA组合起来。}

为了绘制这个DFA，您始终需要跟踪已经出现的b的数量是偶数还是奇数。状态0、2和4表示已经出现了偶数个b。因此，您可以在垂直方向上将此DFA分成两部分，其中底部状态为偶数个b，而上部状态为奇数个b。

同时，如果b的数量为奇数，则接受字符串，因此最终状态应该位于上部的某个状态中。

不仅b的数量是条件，而且a应该至少为2。因此，您可以将此DFA水平分成三个部分，其中a的数量在state-0和1处为0，在state-2和3处为1，在state-4和5处为2。在前两个a之后，字符串中允许任意数量的a，因此状态q4和q5上有自环。

_{所需状态的数量为6，因为奇偶数b需要2个状态，而且a至少为2，因此a=0、a=1、a=2需要3个状态，因此2*3 = 6}

- Grijesh Chauhan

Answer 3

这是使用两个自动机的产品完成的。

- Dan

---

我还卡住了。可以有人用言语来解释一下吗？ - Haskell

我在Jflap中构建了两个自动机... 我该如何将它们合并成一个？ - Haskell