"（ 'a' * N - 'b' * M）％3 = 0"の条件を満たす正規表現を受け入れる文字列

Question

件名をさらに読む正規表現を書いています： "のアルファベット{a、b}は 'a'発生時から 'b'発生時を3で割ることができる場合にのみ文字列を受け取ります。 誰かが私にこれを手伝ってもらえますか？私はこの問題を解決するために私自身の入力を与えるべきであることを知っていますが、私は何の手がかりも持っていません。

多分、（aaa）をベースにして、次に「aとb」の次の「ペア」を展開する必要があるかもしれませんが、「aaa」aaabbbのように展開する方法はわかりません。 "（aaa）ababab"のようにはなりません。

Answer 1

カウントベースの正規表現の問題は、有限状態オートマトンを使って表現するのが最も簡単で、単一のパターンに減らすことができます。

3つのノードで、各モジュール値に1つ。 aまたはbが処理されたときのモジュラ値の変化を定義します。

単一遷移によってノードを介して各パスを置換することにより、一つのノードを折りたたみます。

• 0->2->0 → 0->0（ba）
• 0->2->1 → 0->1（bb）
• 1->2->0 → 1->0（aa）
• 1->2->1 → 1->1（ab）

別のノードに対して繰り返します。

• 0->1(->1)*->0 → 0->0（(a|bb)(ab)*(b|aa)）

最終パターンがある：(ba|(a|bb)(ab)*(b|aa))*