1

我刚开始学习自动机。给定 DFA 似乎很容易理解，设计一个也不是太难。但我觉得很难证明事情......

任何人都可以为这个问题或一些提示提供非正式的证据吗？非常感谢！

PS：对不起，我没有说得很清楚。@Dan 所说的正是我的意思：

为什么要决定“给定一个字符串 w。自动机接受还是拒绝 w？”这个问题。可以在线性时间内完成吗？

4

2 回答 2

4

试着这样想：

  1. DFA 读取输入字符串中的每个字符多少次？
  2. 在处理输入中的单个字符时，DFA 做了多少工作？

希望这可以帮助！

于 2013-01-20T19:58:01.343 回答
4

我猜你想知道为什么要决定“给定一个字符串 w。自动机接受还是拒绝 w？”这个问题。可以在线性时间内完成吗？

假设 w=a_1...a_n。从初始状态 q_0 开始并应用转换 \delta(q_0, a_1) = q_1，这会将您带到 q_1。现在，重复此操作 n 次，直到处理完最后一个字母。这是一个线性时间算法；）

于 2013-01-20T19:58:55.400 回答