Suppose I have a regular language $L$, and I would like to lower-bound the complexity of deciding membership in $L$. Suppose I know that the minimal DFA for $L$ has $N$ states.
I would like to claim that determining the membership of a string of length $n$ in $L$ requires time $\Omega(n\log N)$. The dependence on $n$ is obvious -- I have to read the whole string, in general, to know if it belongs to a language. The $\log N$ factor is because to know what state I am in I need to write it down, and this takes time $\log N$.
This requires arguing that there is no faster way to determine membership in $L$ than to run its minimal DFA (implicitly or explicitly). I think such an argument can be formalized (via equivalence classes, for example), but perhaps I am being naive.
Question: Is the $\Omega(n\log N)$ lower bound correct?
Edit: let me make this more formal. Is there an infinite family of distinct minimal DFAs $A_1, A_2,..$ such that some algorithm simulating the $\{A_i\}$ on a deterministic RAM machine can determine membership of $x$ in $L(A_i)$ in time $o(|x|\log|A_i|)$, where $|x|$ is string length and $|A_i|$ is the number of states?
Edit2: Kaveh's and Aaron's answers seem to indicate that my lower bound is false. But I would love to see a non-trivial counter example. Suppose: (a) I have a family of regular languages $\{L_n\}$ (b) each $L_n$ has a compact description (say, as an NFA) of size $poly(n)$, but the minimal DFA for $L_n$ has size $2^n$ (c) for each $n$, there is no fixed-length prefix that determines membership in $L_n$ (this rules out Kaveh's examples -- you really do need to read the whole string)
Can somebody give an example of a family $L_n$ satisfying (a,b,c) for which there is a TM taking $n$ and $x\in\Sigma^*$ as inputs and deciding $x\in?L_n$ in time $o(n|x|)$? [Note that we've switched from RAM to TM as the computational model; $n$ is given in binary.]