我刚开始学自动机考虑到DFA，似乎很容易理解，设计DFA也不太困难。但我觉得很难证明…
有人能为这个问题提供一个非正式的证据或一些暗示吗谢谢！
PS：对不起，我没说清楚“丹”说的正是我的意思：
为什么决定问题“给定一个字符串w。自动机是否接受
或者拒绝W？”能在线性时间内完成吗？
最佳答案
我想你想知道为什么决定“给定一个字符串w，自动机接受还是拒绝w？”能在线性时间内完成吗？
假设w=aU 1…aU n。从初始状态q_0开始，应用转换增量（q_0，aU 1）=q_1，这就引出了q_1现在，重复这n次直到你处理完最后一封信这是线性时间算法；）