我需要为这种语言创建一个 NFA（或 DFA，还不知道会是哪个）：
L(A) = { w ∈ {a,b}* | count(w, a) = 2i, count(w, b) = 3j, i, j ∈ ℕ }
count(w, z) 定义字母 z 在单词 w 中出现的频率。在这种情况下，'a' 是 2 的倍数，'b' 是 3 的倍数。
有效单词示例：babab、aabbb、bbaab、bbbabbba
我努力为此创建一个自动机，所以我想我会先尝试为它创建一个正则表达式，然后使用这种方法将其转换为 NFA ，因为我可以在正则表达式测试站点上轻松地对其进行测试。但这也没有用。我最终得到了太多看似没有尽头的组合。
如果不使用某种计数机制，我不知道如何为此创建正则表达式。有人可以给我一个提示吗？
您可以将您的自动机建模为六种不同的状态，每一种都描述了 (count(w, a) mod 2, count(w, b) mod 3) 的状态。有六种不同的可能状态：
(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2)
每次读取“a”时，都会从当前状态（例如 (0, 1)）进入下一个对应 a 的状态（-> (1, 1)）。如果您读取另一个“a”，您将再次回到相同的状态 (-> (0, 1))。与 "b" 相同，但改变 b 值（例如 (0, 1) -> (0, 2) -> (0, 0) -> (0, 1)）。
唯一允许的接受状态是 (0, 0)。
使用视觉符号：
http://cdn.imghack.se/images/ccea2c62451d81e477f73ac6fabc5134.png
验证输入的最简单方法是使用正则表达式来满足您的要求：
^(?=((b*a){2})*b*$)(?=((a*b){3})*a*$)[ab]*$
这使用前瞻来断言“a”的数量是 2 的倍数（包括零），同样对于“b”，如果 3，则带来 s 的倍数。
请参阅live demo使用您的示例和一些无效示例的此正则表达式。
让我们看看，你需要偶数个 a，这给你两个状态
a-even
a-odd
对于 b，您需要三的倍数：
b-ok
b-one
b-two
结合这些状态，我们可以构建以下语法：
S(*) -> a A | b B1
A -> a S | b B1A
B1 -> b B2 | a B1A
B1A -> a B1 | b B2A
B2 -> b S | a B2A
B2A -> a B2 | b A
所以，这是一个正则文法，所有规则都有一个终端符号和最多一个非终端的右递归，希望语法有所帮助。