Search code examples
algorithmcomplexity-theorytheorydfa

Why running DFA takes linear time?

I just start learning automata. It seems easy to understand given DFA and not too difficult to design one. But I feel it's very hard to prove things...

Can anyone give a informal proof for this question or some hint? Thanks a lot!

PS: sorry I didn't phrase very clearly. What @Dan said is exactly what I mean:

why deciding the question "Given a string w. Does the automaton accept or reject w?" can be done in linear time?

Solution

  • I guess you want to know why deciding the question "Given a string w. Does the automaton accept or reject w?" can be done in linear time?

    Suppose w=a_1...a_n. Start in the initial state q_0 and apply the transition \delta(q_0, a_1) = q_1, which brings you to q_1. Now, repeat this n times untill you processed the last letter. That's a linear time algorithm ;)