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} 上的单词列表分为三种情况：

• 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} 上得到一个正则表达式。