众所周知,“有限状态自动机”的定义是:
然后我们将这个有限状态自动机描述为:
那么我们就有结论了:
问题是:如果自动机首先读取的字符串是“2”,而不是接受空字符串,而该字符串不属于该自动机的字母表(0,1),该怎么办?这个自动机还会进入接受状态吗?
图片引自书本<计算理论导论>
定义一台机器时,其中一项是字母表(定义中的第二项)。我们不允许在字母表范围之外测试我们的机器。因此,所有 L(接受的字符串)和 L-bar(拒绝的字符串)字符串都应该来自 Sigma-star。