我試圖解決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狀態）都滿足）。