state-machine - 构造一个接受语言 L = {w | 的 DFA w ∈ {a,b}* 和 Na(w) mod 3 > Nb (w) mod 3}

Question

我不能解决这个问题，如果有人能解决这个问题。

构造一个接受语言 L = {w | 的 DFA w ∈ {a,b}* 和 Na(w) mod 3 > Nb (w) mod 3}

标签： state-machineautomatadfa

Answer 1

制作一个具有九个状态的 DFA，分别命名为 q00、q01、q02、q10、q11、q12、q20、q21 和 q22。每个状态 qxy 将对应一对 (x, y) = (Na(w) mod 3, Nb(w) mod 3)。然后，只需将接受状态设为 Na(w) mod 3 > Nb(w) mod 3 为真的状态：q10、q20 和 q21。您可以将这些状态布置在 3×3 网格中，让 Na(w) 分量沿行水平移动，而 Nb(w) 分量沿列垂直向下移动。这些将需要在列和行中进行环绕。