regular-language - 结合确定性有限自动机

Question

我对这些东西真的很陌生，所以我为这里的noobishness道歉。

构造一个Deterministic Finite Automaton识别以下语言的 DFA：

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

每个部分的自动化(at least 2 a's, odd # of b's)很容易单独制作......谁能解释一种将它们组合成一个系统的方法？谢谢。

Answer 1

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

令Σ = {a ₁ , a ₂ , ...,a _k }。
第一步：为两种语言设计 DFA 并将它们的状态命名为 Q ₀ , Q ₁ , ...

第二步：唯一地重命名两个 DFA 中的每个状态，即将 DFA 中的所有状态重命名为 Q ₀， Q ₁， Q ₂， Q ₃，...假设您从下标 0 开始；这意味着没有一个州有相同的名字。

第三步：使用以下步骤构建转移表（δ）

   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 , _ak ) = Q _p1和 δ(Q _j , _ak ) = 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}.

Step1：
奇数个b的DFA。

DFA 至少 2 个。

Step2：
重命名 DFA1 的状态

Step3(a,b,c)：
构造的转换表如下。

Step3d：
由于我们必须对两个 DFA 进行 AND，所以最终状态将是 Q _[2,4] ，因为它包含两个 DFA 的最终状态。
如果我们必须对两个 DFA 进行 OR 运算，最终状态将是 Q _[0,4] ,Q _[2,3] ,Q _[1,4] ,Q _[2,4]。
添加最终状态后的转换表会像这样。

Step4：
重命名所有状态 Q _[i,j]
Q _[0,3] to Q ₀
Q _[1,3] to Q ₂
Q _[0,4] to Q ₁
Q _[2,3] to Q ₄
Q _{[1 ,4]}到 Q ₃
Q _[2,4]到 Q ₅
所以最终的 DFA 将如下所示。

Answer 2

它是使用两个自动机的乘积完成的。

Answer 3

至少两个且为奇数的语言L是常规语言。其DFA如下：ab

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

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有多少 s 是偶数或奇数。States 0, 2 and 4表示偶数b已经来了。因此，您可以将此 DFA 垂直分为两部分，其中底部状态为偶数b，上部状态为奇数。

如果奇数也接受字符串，b因此最终状态应处于上部状态之一。

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

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