有限自动机不接受字符串

Question

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

s->a->q->F

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

Answer 1

答案很可能是肯定的。为什么 "most likely"？嗯。

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

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

自从您修复了 Sigma 之后，只有四个地方可能出错。如果您手动创建 FSA，您当然会创建一个

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

如果我们假设一个格式正确的 FSA（意思是 S 不为空并且 s0 in S，所有状态都是可访问的），如果您从例如带有像 foma 这样的库的正则表达式，然后是：FSA 不接受任何字符串的唯一方法是没有接受状态。