支付b和偶數個字符串的正則表達式

Question

如何定義正則表達式以使用以下語言？

L = {w∈{a，b} * | W具有偶數B的}的

我試圖創建相關的自動機：

，並從我試圖運用算法來獲得DFA定期espression和我得到這個公式： a*ba*b。

這是正確的答案嗎？

Answer 1

您是接近，但你在pattern.You結束需要一個a*還需要錨^和$指定開始和你string.Then結束，你可以把你所有的正則表達式的捕獲組內和使用*匹配任何偶數如果b和a*的數量b零：

^((a*ba*ba*)*|a*)$ 

注：|是一個邏輯OR，讓您的正則表達式引擎匹配(a*ba*ba*)*或a*。

Debuggex Demo

您也可以使其更加優雅，但因爲你不熟悉非常符合正則表達式首先我建議前面的模式。

例如下面將工作：

^(((a*b){2})*)a*$ 

Answer 2

這裏是最好的解決辦法，因爲我遵循從DFA正則表達式轉換算法（由鋼筆完成）：

(a*|ba*b)* 

你可以測試它here，你可以通過觀看這個video瞭解這個算法。