computation-theory - 绘制一个简单的非确定性有限自动机 (NFA)

Question

我如何为这个问题绘制 NFA（自动机）？

首先它应该接受：

• 字母 = x,y,z

• L= { w | w 使得出现次数 x,y,z 之一是三的倍数。}

例如：{xxx, yyy, zzz, xyxyzzz, xyxyx, zyzyz...}

Answer 1

首先让我们从一个更简单的问题开始：
你如何为 L' = { ^an |绘制这个自动机？n % 3 == 0}？

您将绘制一个具有 3 种状态的自动机 - 每个可能的模数一个，并在它们之间迭代a. 接受状态将是表示为 的状态0。

现在，在确定之后 - 对于您的问题，您的自动机需要有 3 ³个状态 - 所有可能的元组(x,y,z)x,y,z 位于 {0,1,2} 中。

你现在的目标是了解你的 lamda 是什么？既然是你的作业，我不会给出完整的答案，只是提示：

如果你看到x并且你处于状态(a,b,c)- 你想前进到(a+1 %3 ,b,c)

还想一想-接受状态是什么？提示：简化的接受状态是L'什么？

附件：L'如上所述的自动机。