8
$\begingroup$

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?

$\endgroup$
15
$\begingroup$

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$.

$\endgroup$
7
$\begingroup$

Yes, this is true. For every such problem there is a DFA that decides the language, and checking if a word is accepted by a DFA can easily be done in time linear in the length of the word.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.