字符串的重複交錯副本的正則表達式？

Question

查找這種語言正則表達式：

L = {＆拉姆達;, AB，ABAC，abacab，abacabac，abacabacab，...}

好了，所以我一直在工作的這問題現在有一段時間了。到目前爲止，我知道'ab'重複其自身（ab）。但我難住'ac'....它不能是（ab）（ac）* ... 任何指針，將不勝感激。

我看過我的書，沒有例子可以告訴我如何解決這個問題。

Answer 1

讓我們先簡化一下。讓我們讓B代表ab，C代表ac。然後，您要生成的字符串

＆拉姆達，B，BC，BCB，BCBC，BCBCB，...

在這種情況下，你可能想正則表達式分成兩例：產生

01一個產生

＆拉姆達;, BC，BCBC，BCBCBC，BCBCBCBC，...

和一個

B，BCB，BCBCB，BCBCBCB，...

前者由正則表達式(BC)*給出，而後者是由正則表達式(BC)*B給出。如果將這些結合在一起，就會得到(BC)* | (BC)*B，可以將其重寫爲(BC)*(B | λ)。所有剩下要做的就是通過更換B和C with AB and ac`，這使所產生的正則表達式

(abac)*(ab | λ) 

這一觀察也應該讓你設計一個DFA或NFA的語言擴展了這一點，但我我會留下這個練習。 :-)

希望這有助於！