找到语言 L={0,1,2} | 的有限自动机需要包括 1002 1,2 是奇数，0 是偶数

Question

找到语言 L={0,1,2} 的有限自动机

符合以下标准：

• 单词必须包含“1002”。
• 1 出现的次数必须是奇数
• 2 出现的次数必须是奇数
• 0出现的次数必须是偶数

我能够证明规律性，但当我把它画在纸上时，我尝试了多种方法，但找不到方法

Answer 1

我认为我们应该使用 4 位来描述 4 个条件，因此，我们将有 2^4=16 个状态。然后你可以构造在状态之间移动的条件：

• 最左第 1 位：包含 1002
• 最左边第二位：奇数 1
• 最左第 3 位：奇数 2
• 最左第四位：偶数 0

例如，我们的初始状态是0001（q1），当我们遇到0时，它会转到0000（q0）。

这是一个示例流程：

q1 -> 0 -> q0

q1 -> 1 -> q9 (1001)

q1 -> 2 -> q3 (0011)

按照这个想法，接受状态将是 (1111) = q15