# Any problem solved by a finite automaton is in P

After my Theory of Computation class today this question popped in my mind: If a problem can be solved by a finite automaton, this problem belongs to P.

I think its true, since automata recognize very simple languages, therefore all these languages would have polynomial algorithms to solve them. Thus, is it true that any problem solved by a finite automaton is in P?

Yes, it is true. In terms of complexity classes, $$\text{REG} \subseteq \text{P},$$ where $\text{REG}$ is the class of regular languages (i.e., problems that can be solved by a finite automaton). More specifically, $$\text{REG} \subseteq \text{DTIME}(n), \tag{*}$$ and $\text{DTIME}(n)$ is a strict subset of $\text{P}$ by the time hierarchy theorem.
The proof of (*) is as follows: for any problem in $\text{REG}$, there is a DFA which solves it. Convert that DFA to a Turing machine with the same states and transition function, which always moves to the right until it sees a blank, and then accepts or rejects. This Turing machine always halts in time exactly $n$.
It's also worth mentioning that $$\text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$$ for any fixed constant $k$.