正則表達式0 * 1 * 1 + 11 * 0 * 1 DFA

Question

表達式「0 * 1 * 1 + 11 * 0 * 1」是否被以下自動機接受？

由於表達產生字符串「1」結束，我相信會自動接受它。

但是，我在其中一個參考文獻中找到了答案。有人可以請澄清與解釋？

注意：+表示OR操作。

Answer 1

號你DFA相當於表達(0*1+)+

您所指定的表達至少需要三個1被接受。它分解成部分

0* 
1* 
1+ <-- Required at least once 
1 <-- Required 
1* 
0* 
1 <-- Required 

一個DFA你的表達需要表示這等同看起來是這樣的：與Regex visualizer創建

圖片，讓你產生這些圖來自正則表達式。

更新：如果+意味着或，這改變了事情。您的原始DFA仍然不相同。你錯過了，如果接受的字符串以1開頭，則需要至少再接受一個1才能被接受。的DFA的表達看起來像這樣：作爲通過輸入0*1*1|11*0*1於觀察生成

。