正則表達式涉及模運算

Question

我試圖創建DFA或正則表達式語言

L = {一^ň b^米 | n mod 3 = m mod 3}`

例如，L包含字符串aaabbb，aaabbbbbb和abbbb。

但是，我在這裏遇到了任何進展。我怎樣才能做到這一點？

Answer 1

只有三個可能的餘數模3。您可以通過列出處理這三種情況中的每一種的正則表達式，然後將它們聯合在一起來構建該語言的正則表達式。這裏有一個可能的答案：

(aaa)*(bbb)* | a(aaa)*b(bbb)* | aa(aaa)*bb(bbb)* 

希望這有助於！