automation - 有限自动机不接受字符串

Question

over(0,1) 的有限自动机如何不接受任何字符串？我只能想到

s->a->q->F

最终状态 F 为空集。请问这是真的吗？

Answer 1

答案很可能是肯定的。为什么是“最有可能”？出色地。

在数学上，FSA 是一个 5-tuple (Sigma, S, s0, delta, F)，其中

• Sigma是字母表，
• S是状态集，
• s0是初始状态，
• delta是状态转移函数，
• F是接受状态的集合。

由于您已修复Sigma，因此只有四个地方可能出错。如果您手动创建 FSA，您当然会创建一个

• 没有状态
• 没有初始状态
• 并非所有状态都可以访问
• 没有接受状态

如果我们假设一个格式良好的 FSA（意思S不是空的，并且所有状态都是可访问的），如果您从例如具有类似fomas0 in S库的正则表达式创建它就是这种情况，那么是的：FSA 的唯一方法不接受任何字符串就是没有接受状态。