# Why are all regular languages in P?

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?

• If $k$ is a constant then $2^{k+1}$ is a constant, so the DFA has a constant number of states. Any problem where the input is guaranteed to be one among some finite set of inputs (and where the output is also finite) can be solved in constant time by simply having a lookup table (even if it has a gazillion entries, that is still a constant). Or by defining a (constant-sized) DFA as you do. Jun 9 at 21:20

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