'a' s 和 'b' s 串联的单词的正则表达式。 a 在一个单词中恰好出现 n*2 次，而 'b' 正好出现 n*3 次

Question

我需要为这种语言创建一个 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。 ，因为我可以轻松地在正则表达式测试站点上对其进行测试。但这也没有用。我最终得到了太多似乎没有尽头的组合。

我不知道如何在不使用某种计数机制的情况下为此创建正则表达式。有人可以给我提示吗？

Answer 1

您可以将自动机建模为六个不同的状态，每个状态描述 (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