结合确定性有限自动机

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; 这意味着没有一个州会有相同的名字.

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

   3A.组合DFA的
      起始状态:取两个DFA(DFA1和DFA2)的起始状态,并将它们命名为Q _[i,j],其中i和j分别是DFA1和DFA2的起始状态的下标; 即,Q _i是第1个DFA的开始状态,Q _j是第2个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:
DFA为奇数个b.

DFA至少为2个.

第2
步:重命名DFA1的stae

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].
在添加最终状态后,转换表会这样.

步骤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将如下所示.

Answer 2

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