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?