我需要为这种语言创建一个 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
我努力为它创建一个自动机，所以我想我应该先尝试为它创建一个正则表达式，然后使用 this method 将其转换为 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
关于 'a' s 和 'b' s 串联的单词的正则表达式。 a 在一个单词中恰好出现 n*2 次，而 'b' 正好出现 n*3 次，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20036291/