Why running DFA takes linear time?

Question

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?

Answer 1

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 ;)

Answer 2

Try thinking about it this way:

1. How many times is each character in the input string read by the DFA?
2. How much work does the DFA do when processing a single character from the input?

Hope this helps!