计算理论 - DFA
Computation theory - DFA
我想设计一个字母表 {x,y,z} 的 DFA，它接受 3 的 'z' 倍数的单词（例如 "xzyyxzzyy"）
有人知道怎么做吗？或者接受它的语言是什么？
您将需要三个状态来跟踪看到的 z 的数量，modulo 三个；这些状态将在输入 z 上相互循环，#z(w) = 0 (mod 3) 的状态将是唯一接受状态。
为了允许任意的 x 和 y，每个状态都可以在这些输入上循环到自身。
您可以使用 q0、q1 和 q2 作为状态，使 q0 成为初始状态并且仅接受状态。然后，你有三个转换 f(qi, z) = wh 其中 j = i + 1 (mod 3)，三个转换 f(q, x) = q 和三个转换 f(q, y) = q总共九次转换。
我想设计一个字母表 {x,y,z} 的 DFA，它接受 3 的 'z' 倍数的单词（例如 "xzyyxzzyy"）
有人知道怎么做吗？或者接受它的语言是什么？
您将需要三个状态来跟踪看到的 z 的数量，modulo 三个；这些状态将在输入 z 上相互循环，#z(w) = 0 (mod 3) 的状态将是唯一接受状态。
为了允许任意的 x 和 y，每个状态都可以在这些输入上循环到自身。
您可以使用 q0、q1 和 q2 作为状态，使 q0 成为初始状态并且仅接受状态。然后，你有三个转换 f(qi, z) = wh 其中 j = i + 1 (mod 3)，三个转换 f(q, x) = q 和三个转换 f(q, y) = q总共九次转换。