Why are all regular languages in P?

Question

Just to be clear, I am aware that you can define an accepting DFA for every regular language. My problem is a bit deeper.

Let's say we have a language L which consists of a random half of all binary strings of length at most k. This language is finite, so it is regular. We can of course create a DFA for it, by representing every binary string of up to k length and marking the states corresponding to words in the language as accepting.

However, such a DFA has 2^(k+1) + 1 states - one for every input, one starting state (accepting if the empty word is in the language), and one garbage state for strings longer than k.

If I were to write a program to implement this DFA, it would require an exponential number of instructions (in regard to maximum input length k), since I need to at least allocate memory for every state and map transitions. So it looks like it shouldn't be in P.

Possibly, this DFA can be minimized to have fewer states. I am not aware of any theorem that it is always the case though and for a good reason - if you could minimize any DFA to say, polynomial number of states, then you could do it for all finite languages - like 3SAT over 100 boolean variables, with obvious consequences.

What am I missing here?

Answer 1

Such a DFA is a binary decision tree with depth k. While it does have O(2^k) nodes, in order to reach a leaf you need at most k steps, so deciding whether a word is in L takes O(k) steps. How big the program is is irrelevant for the runtime complexity.

Answer 2

There are two important things you should note:

1. the complexity (of a Turing Machine) is measured by running time, and not by the length of the "code", or the number of states.

2. Every DFA can be converted to a TM that just goes right on the tape.

Combine the two ideas, and you get that every DFA can be converted to a TM that accepts the same language and runs in exactly $n$ steps, where $n$ is the size of the input. Hence, every regular language is in $P$.