建設有限自動機

你會同意，在正則表達式：建設有限自動機

((a|b)*(e|c)*)*

是A，B的任意組合，和c的？或者你會說c總是在a和b之後出現。

我會說沒有。你也可以引入'e'。此外，'c'可以跟隨'a'或'b'，但'e'也可以。或者你什麼也沒有。 – Makoto

@Makoto你會說字符串cba可以適合這個正則表達式嗎？ – user3339242

是的。這些可能發生的順序並不是確定性的，因爲你可以沒有a或b，但是全部是c，然後用a或b來跟蹤它。 – Makoto

通過我總是傾向於在語義上描述正則表達式RE。但也有一個規則，一個 - 「分佈式法」，這是非常有幫助的編寫清理和優化RE：

(P | Q)* == (P*Q*)* == (P* | Q*)*

注：|是工會的運作和P | Q是一樣P | Q。這裏P，Q是正則表達式。

所以你表達：

 ((a|b)*(e|c)*)*  # P = (a|b)* and Q = (e|c)* 
=> ((a|b) | (e|c))*  # (P* | Q*)* = (P | Q)*

正如我在工會爲了說並不重要，所以這裏()是多餘的。和

 ((a|b) | (e|c))*  
=> (a | b | c | e)*

*現在*表示重複應用了某種模式的任意次數。在上面的表達式*中應用了a | b | c | e，並且在每次迭代中您可以選擇任意一個符號。這意味着任何符號都會出現在正則表達式中的任何其他符號之後 - 這意味着「a」，「b」，「 c'，'e'是可能的。

而且它的FA非常簡單：由單狀態Q 組成，帶有標記所有四個符號的自循環。如下：

 
    __ 
    || a, b, c, e 
    ▼| 
––►((Q₀)) 

_{Q₀ is both initial and final state}

2014-04-05 19:23:05

回答