我刚开始学习自动机。给定 DFA 似乎很容易理解，设计一个也不太难。但是我觉得证明事情很难...
谁能给出这个问题的非正式证明或一些提示？非常感谢!
PS:对不起，我没有说清楚。 @Dan 所说的正是我的意思:
why deciding the question "Given a string w. Does the automaton accept or reject w?" can be done in linear time?
最佳答案
我猜您想知道为什么要决定“给定一个字符串 w。自动机是接受还是拒绝 w？”这个问题。可以在线性时间内完成吗？
假设 w=a_1...a_n。从初始状态 q_0 开始并应用转换\delta(q_0, a_1) = q_1，这会将您带到 q_1。现在，重复 n 次，直到处理完最后一个字母。这是一个线性时间算法 ;)
关于algorithm - 为什么运行 DFA 需要线性时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14428588/