簡化正則表達式，自動機理論

我最近需要弄清楚語言的正則表達式 {w | | w |是奇怪的，並且w開始和以字母{a，b}上的符號b}結束。簡化正則表達式，自動機理論

我想出了一個解決方案是

b(ab+bb+aaab+aabb+abab+abbb+bbbb+bbab+babb+baab)*

的解決方案是很長，所以我希望有人能告訴我一個方法這可以簡化，

來源

2016-10-05 Sean McCarthy

你的「解決方案」是錯誤的。捕獲不屬於你的語言的'baa'。無論如何，如果你有更多的正則表達式可以找到，請隨時發表我的評論。我很樂意提供幫助。 – xenteros

謝謝，這實際上恰巧是一個錯字。這意味着要「bb」 –

無論如何，upvote正確的答案，只是爲了公平。 – xenteros

你可以嘗試b|(b(a|b)((a|b)(a|b))*b) 語言你描述可以產生b，並且由第一個分支捕獲，並且這是它可以產生的唯一大小爲1的字符串。然後它可以生產尺寸3,5,7，...琴絃。那些被第二個分支捕獲。開始和結束時的b是不言自明的。而那些帳戶爲2個字符。中間位是經過{a,b}的經典語言{w | |w| is odd}。

更強大的語法將允許類似b((a|b)((a|b)^2)*b)?的東西，它更緊湊，但等同。

來源

2016-10-05 07:30:22

謝謝，很好的解釋。 –

最簡單的一個：

(b(a|b)(aa|ab|ba|bb)*b)|b

來源

2016-10-05 07:33:18 xenteros

簡化正則表達式，自動機理論

回答

相關問題