regex - E={a,b} で言語の正規表現を見つける

Question

L = w : (na(w) - nb(w)) mod 3 /= 0

この言語の正規表現を見つけるにはどうすればよいですか?

As の数から B の数を引いた値が 3 の倍数にならないということは理解しています。つまり、a - b は 3、6、9、12 などにはなりません

しかし、私はまだそれを正規表現に入れるのに苦労しています。最初にDFAかNFAにしてみましたが、それもできませんでした。

どんな助けでも大歓迎です！

Answer 1

{a,b} の単語のリストを 3 つのケースに分割することで、それを実現できます。

• L1 = w : (na(w) - nb(w)) mod 3 = 1
• L2 = w : (na(w) - nb(w)) mod 3 = 2
• L3 = w : (na(w) - nb(w)) mod 3 = 3

L はL1 U L2であり、L1、L2、および L3 に関連する式を作成できるはずです。その後、物事を排除して、{a,b} の正規表現になるはずです。