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

Question

我真的是新手，所以我为这里的笨拙而道歉。

构造识别以下语言的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。
令Σ= {a1，a2，...，ak} 。
第一步:设计两种语言的DFA，并将其状态命名为Q0，Q1，...
第二步:唯一地重命名两个DFA中的每个状态，即，假设您已从下标0开始，则将DFA中的所有状态重命名为Q0，Q1，Q2，Q3...。这意味着该州都不会有相同的名称。
第三步:通过执行以下步骤来构造转换表(δ)
3a。 组合DFA的开始状态:
将两个DFA(DFA1和DFA2)的起始状态分别命名为Q [i，j]，其中i和j分别是DFA1和DFA2起始状态的下标；即Qi是第一个DFA的开始状态，而Qj是第二个DFA的开始状态，并将Q [i，j]标记为组合DFA的开始状态。
3b。 将两个DFA的状态映射为
如果δ(Qi，ak)= Qp1且δ(Qj，ak)= Qp2，其中Qp1属于DFA1而Qp2属于DFA2，则δ(Q [i，j]，ak)= Q [p1，p2]
3c 。填满整个表，而过渡表中还剩下Q [i，j]。
3d 。合并后的DFA的最终状态:
对于AND情况，最终状态将全部为Q [i，j]，其中Qi和Qj分别是DFA1和DFA2的最终状态。
对于OR情况，最终状态将全部为Q [i，j]，其中Qi或Qj是DFA1和DFA2的最终状态。
第四步:
重命名所有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的位置

步骤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]至Q0
Q [1,3]至Q2
Q [0,4]至Q1
Q [2,3]至Q4
Q [1,4]至Q3
Q [2,4]至Q5
因此最终的DFA将如下所示。