RE：一的數量是整除6和b的數量是由8

Question

整除查找一個正則表達式表示由{a,b}，其中的a數目的是除盡6和b數串可以被8整除。

我試圖創建一個DFA，其接受這樣的字符串。我的想法是使用所有餘下的mod 6和mod 8，總共剩餘48個餘數。因此，在DFA每個狀態是一對(r, s)其中r從0變化至6和s從0變化至7開始狀態（以及接受狀態）(0, 0)和由我們可以很容易地通過注意給轉換到狀態，如果我們輸入"a"狀態(r, s)轉變到(r + 1, s)和輸入"b"它轉換到狀態(r, s + 1)。

但是實在是太難了與48個狀態的DFA工作，我不知道這是否可以通過手動使用DFA最小化算法最小化。

我真的不知道如何才能得到表示這樣的字符串的正則表達式。

Answer 1

如果你被允許使用向前看符號：

^(?=b*((ab*){6})+$)a*((ba*){8})+$ 

Debuggex Demo

匹配字符串的例子：bbaabbaabbaabb

的想法很簡單：我們知道如何搭配有串可以被6整除的a s - ^((b*ab*){6})+$，我們也知道如何匹配字符串，數字爲b s可被8整除 - ^((a*ba*){8})+$。所以我們只需要一個正則表達式，另一個用於匹配部分。

在情況下，如果你也需要匹配只由a S或只是b小號字符串，那麼下面的正則表達式會做：

^(?=b*((ab*){6})*$)a*((ba*){8})*$ 

匹配的字符串的

例子： aaaaaa，bbbbbbbb，bbaabbaabbaabb

Debuggex Demo