簡化這個正則表達式

Question

我正在爲我的編譯器類做一些預試練習，並且需要簡化這個正則表達式。

(a U b)*(a U e)b* U (a U b)*(b U e)a* 

很明顯，e是空字符串，U代表聯合。

到目前爲止，我認爲其中一個（a U b）*可以被刪除，因爲U a = a的聯合。但是，我找不到任何其他的簡化，到目前爲止還沒有很好地解決其他問題。 :(

任何幫助表示讚賞，非常感謝！

Answer 1

對正則表達式有點生疏，但如果仍然*表示 「零個或多個ocurrences」 你可以替換：

(a U e)b* for (a U b)* 

離開第一部分有：

(a U b)*(a U b)* = (a U b)* 

在右邊，你有

(b U e)a* = (b U a)* 

現在，由於U形B = U A，你會得到：

(a U b)*(a U b)* 

在右手邊，這讓剛剛

(a U b)* U (a U b)* = (a U b)* 

我認爲這是它...

Answer 2

我認爲整件事是相當於(a U b)*（或大多數正則表達式語法，(a|b)*）

Answer 3

首先TRAN石板的語言的英語描述：

(a U b)*(a U e)b* U (a U b)*(b U e)a* 

轉換爲：

---

的a秒或b小號的任何序列，接着任選的a，隨後通過任何數量的b小號。

OR

任意數量的a S和b秒，然後通過一個可選的b，任意數量的a小號

---

follwed有很多重疊的位置 - 至少(a U b)*(a U e)是與(a U b)*完全相同，因爲「a s和b s的任何序列」必然以a或ε（以任意字符串可以與小量結束），因此這些基團可被消除，留下

(a U b)*b* U (a U b)*a* 

轉換爲：

---

的a秒或b小號的任何序列，隨後通過任何數量的b小號。

OR

任何數量的a S和b S，通過任何數量的follwed a小號

---

現在那些最外組的第一部分是相同的，所以允許塌陷那些成一個

(a U b)*(a* U b*) 

翻譯爲：

---

任何序列的a S或b秒，然後通過任何數目的a S或通過任何數量b秒。

---

現在等一等，「由於和B的任何序列」 一定用「的a小號任何序列或b小號任何序列」，結束這意味着什麼，其匹配的第一個部分可以匹配整個正則表達式（因爲第二部分可以有一個長度爲零），所以我們爲什麼不只是使它

(a U b)* 

ただ。簡單。

Answer 4

I'll給你我將如何解決這個問題的想法：（不是很正規，無擔保）

看主U的左側：

（U形B）* - 這是什麼意思？長度爲n的a和b的組合，其中n> = 0。

接下來是（U e）。我們有什麼在這裏？一個空的單詞。如果我們想要的話，我們可能已經在前一部分中獲得了它。如果我們想要e，那麼我們可以不管它。請注意，我們不需要一個a，因爲我們可以選擇e。所以我們可以跳過這整個部分。

接下來是什麼？ B *。那是什麼？儘可能多的b's我們想要的。我們也可以在第一部分中獲得這些！我們可以離開！

所以左邊唯一的東西是（一個U b）*。

讓有右側一看：

確定這是很容易，現在，我們可以用同樣的想法，這只是不同的字母。

我們也會以同樣的方式得到（a U b）*。所以最後我們有（a U b）* U（a U b）*，你知道它等於（a U b）*。