與此DFA對應的正則表達式是什麼？

Question

這是來自研究項目的DFA。我們手動創建了DFA。我們感興趣的是與DFA對應的正則表達式。當然，可能有多個 正則表達式對應於它;我們更喜歡更簡單的一個。

Answer 1

傑克，基本上可以有兩個正則表達式這個DFA。 第一個可以是AB * CD * A， 第二可AE * F *

Answer 2

10*110*是用於從ABCD轉變而不在Cb上的環

1(0*(10)*)*110*我認爲也包括C和B

之間的環

0+10*1是來自AEF的循環。所以，你可以把它前面以兩個表達式

你得到(0+10*1)*10*110*不循環，(0+10*1)*1(0*(10)*)*110*它

最終的表達是這樣

(0+10*1)*1(0*(10)*)*110* 

從一個過渡到d

最後在達到D狀態時，您可以獲得1，達到A，並重復整個過程

((0+10*1)*1(0*(10)*)*110*)(1((0+10*1)*1(0*(10)*)*110*))* 

See it in action爲這個DFA

澄清一些有效和無效的字符串 - 這正則表達式是基於正則表達式由PCRE所接受。所以+意味着串1點或多個正好和*指0或多個正好，而|意味着OR

編輯的(0*(10)*)*可以爲(0|(10))*（感謝編寫更好@ grijesh，肖漢爲指向我在這個方向）。因此，RE（基於PCRE）將是

((0+10*1)*1(0|(10))*110*)(1((0+10*1)*1(0|(10))*110*))* 

Answer 3

您需要使用的算法描述爲here。如果您對該主題更感興趣，我強烈建議您閱讀Michael Sipser的Introduction to the Theory of Computation。

爲您的特定DFA，該算法以下你得到這個表達式：

[(010*1)*1(10*)110*1]*(010*1)*1(10)*110* 

Answer 4

你必須在B和E.錯過了標籤在你DFA自我循環，但因爲你說對於給定的DFA然後兩個迴路上的標籤的唯一選擇是0。

正確的正則表達式的DFA是：

(00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 

的簡要說明：

1. 你只有一個那就是D最終狀態。所以如果字符串在D結束，字符串可以被接受。 您注意到D上的傳入邊緣被標記爲1而D具有標記爲0的自我循環。

2. 起始狀態爲A所以字符串可以用0或1開頭。實際上在A上有兩個循環。一個以0開頭，並穿過上面的圖表。
   RE爲上部循環爲：00* 10*1

   爲了理解這一點：

   0  0*   1  0*   1 
   
   A-E loop on E  E-F loop on F  F-A 
   

3. 從A去D在下方的曲線圖。 RE是1 (0 + 10)* 1 1
   要理解這一點：

   1  (0 + 10)* 1  1 
   A - B loop on B B-C C-D  
   

4. 的DFA完整的RE是：（答案）

   (00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 
   

   要理解這一點：

   (00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 
   
   ^   ^            ^ 
   upper loop A to D   loop on D    * for loop on D  
   
   
            (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1 )* 
            ^ D-A A-A  A-B loop on B, B-c c-D  
           self loop on D         
   

編輯作爲@RedBaron評論執行此正則表達式生成的字符串01110100110：

以及拳頭檢查它由DFA或不接受：

A - 0 - >電子 - 1 --- > F - 1 ---> A --- 1 ---> B - 0 ---> B --- 1 ---> C --- 0 --- - > B --- 0 ---> B -1 - > C --- 1 ---> D --- 0 ---> D

是字符串被DFA接受。

如何從RE生成我給出了答案，下面我已經對齊RE和字符串。

(00* 10*1)* (1(0 + 10)* 1 1) (0 + 1 (00* 10*1)* 1 (0 + 10)* 1 1)* 

0^ 1^ 1  1 0100  1 1 0 

只有你可能有難度的理解：如何(0 + 10)*產生0100？下面這個檢查：

(0 + 10)*被重複了三次：

(0 + 10)(0 + 10)(0 + 10) 
0   10 0