我试图解决DFA

Question

我要做的L1 L2ü路口和L1 L2ň

Answer 1

您可以通过正规笛卡尔积机建设运行算法得出的自动机用于L1和L2的交点和联合。但是，由于这些语言非常简单，因此可以更简单地给出语言并为每个语言记下DFA。

L1是至少有一个a的as和bs的所有字符串的语言。 L2是至少有两个b的as和bs的所有字符串的语言。

要接受L1和L2的交集，我们需要看到至少一个和两个bs。下面，我们有六个州：

1. Q0，初始状态下，我们需要一个和两个BS
2. 第一季度，我们仍然需要两个BS
3. Q2，在这里我们还需要一架B
4. Q3，在这里我们不需要更多的（接受状态）
5. Q4，其中我们仍然需要一个一个和一个b

6. Q5，在那里我们仍然需要一个一个

   ---> Q0-A-> Q1-B-> Q2-B-> Q3 -B-> Q4-A-> Q2 Q3 -B-> Q5-A-> Q3

（其中转换丢失，它们是自循环）

请注意，有六个状态：这与我们分别在两个和三个状态的原始DFA上完成笛卡尔乘积机构造的情况相同。

对于联合，我们可以使用完全相同的DFA，并将接受状态的集合更改为q1，q3，q5。这表明我们现在接受这一事实，即任何一个条件都是真实的（并且状态q1和q5是一个状态，但不是两个状态（如q3状态）都满足）。