Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
众所周知,“有限状态自动机”的定义是:
然后我们将这个有限状态自动机描述为:
那么我们就有了结论:
问题是:如果自动机第一次读取的字符串是'2',而不是接受一个空字符串,那不属于这个自动机的字母(0,1)怎么办。这个自动机还会去接受状态吗?
图片引自《计算理论导论》一书
定义机器时,其中一项是字母表(定义中的第二项)。我们不允许在字母表范围之外测试我们的机器。因此,L(接受的字符串)和 L-bar(拒绝的字符串)的所有字符串都应该来自 Sigma-start。