-1

众所周知,“有限状态自动机”的定义是: 在此处输入图像描述

然后我们将这个有限状态自动机描述为: 在此处输入图像描述

那么我们就有了结论: 在此处输入图像描述

问题是:如果自动机第一次读取的字符串是'2',而不是接受一个空字符串,那不属于这个自动机的字母(0,1)怎么办。这个自动机还会去接受状态吗?

图片引自《计算理论导论》一书

4

1 回答 1

0

定义机器时,其中一项是字母表(定义中的第二项)。我们不允许在字母表范围之外测试我们的机器。因此,L(接受的字符串)和 L-bar(拒绝的字符串)的所有字符串都应该来自 Sigma-start。

于 2019-06-10T11:16:28.963 回答