轉換DFA到RE

Question

我使用JFLAP轉換一個DFA到RE的語言

「即使a和奇b」，如圖

這最後一步是我不太清楚在圖怎麼得到這個最終RE

最終RE

((ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)*(a(bb)*ba+b))*(ab(bb)*ba+aa)*(ab(bb)*a+b)(a(bb)*a)* 

我的困惑是在學期a(bb)*ba+b（Q1到Q0），爲什麼在最後表達

Answer 1

我已經重新標記的NFA的轉換你的圖中這樣的解釋是簡單的具有明星。

但這樣做會使你的正則表達式：

(R1* R2 R3* R4)* R1* R2 R3* 

第一個括號部分實質上描述的是讓你從Q0回Q0的一系列步驟。正則表達式中，儘可能多地做到這一點，當你完成任務時，可以按照R1的次數跟隨你想要保持的狀態q0，當你真的做完了亂七八糟的時候，按照R2得到到最後的狀態，你可以循環使用R3。

這不是最好或最直觀的方式來將NFA轉換爲正則表達式，但我認爲這是正確的。希望解釋是有道理的。如果沒有，請在評論中提問！

作爲參考，我寫了我提出的正則表達式。注意我使用|而不是像你一樣。

(aa|ab(bb)*ba)* (ab(bb)*a|b) ((a(bb)*a)* ((a(bb)*ba|b)(aa|ab(bb)*ba)*(ab(bb)*a|b))*)*

編輯：

你希望你的正則表達式來捕獲所有可能的模式，最終將導致你最終狀態，從狀態Q0開始。現在想象你站在q0狀態。你會採取什麼行動？你可以把你的一套行動分解成那些讓你處於q0狀態的行動和那些能讓你進入q1的行動。

操作，將讓你在Q0：

• 按照R1
• 關注R2，做任何瞎搞你可以在Q1，然後按照R4回來Q0。讓我們稱之爲正則表達式R2_R4，其中該空白需要填充我們可以在q1中執行的所有可能的事情，除了通過R4返回。那麼我們能做的唯一事情就是跟隨R3一堆，所以我們用R2R3 * R4替換空白。

通過列舉你可以留在q0中的所有方法，你基本上擺脫了從q1到q0（R4）的轉換。換句話說，在我的正則表達式的這個部分之後，如果你到q1狀態，應該沒有辦法返回到q0（如果它有被正則表達式的第一部分捕獲的話）。所以，你的NFA現在那種看起來是這樣的：

所以，你最終的正則表達式將是，遵循停留在Q0過渡，然後通過R2去Q1，並留在Q2，只要你想通過跟隨R3。所以，你的正則表達式可能看起來像：

(R1 + R2R3*R4)* R1* R2 R3* 

這實際上等同於你有一個：

(R1* R2 R3* R4)* R1* R2 R3* 

因爲(R1+R2 R3* R4)*的或本質上等同於(R1* R2 R3* R4)*。我實際上認爲使用or（+）的版本更加清晰，但只要它有效，它並不重要。