Q:

Complexity lower bound for regular languages

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

A:

I'll answer my own question -- the conjectured lower bound is false. Consider 
$L_n=\Sigma^* 0 \Sigma^n$ (that is, the collection of all strings with a $0$ in the $n$th location from the end). It's easy to see that there is an $O(n)$ size NFA for $L_n$, but the minimal DFA for $L_n$ is exponential. Here is a TM that decides membership in $L_n$ in time $O(|x|+n)$: scan $x$ to the end (time $|x|$) and read $n$ steps back to see if that letter is $0$.

A:

Edited to add: I don't think this answer is on point, but I will leave it up.  Now community wiki so I don't get any more reputation for this.
The lower bound is not correct. Intuitively, this is because, to decide membership in $L$, I need to know the description of the DFA, but I may not need to run the DFA on the input if I am a Turing machine.
More formally, there is a Kolmogorov Complexity Characterization Theorem for Regular Languages. It states in part that the following are equivalent:

$L$ is regular.
$C(\chi_1 \ldots \chi_n) \leq \log n + c_L$.

Here, C is "simple" Kolmogorov Complexity, $\chi$ is the characteristic sequence of $L$, and $c_L$ is a constant depending only on $L$. Intuitively, this constant is the number of bits required to describe the minimal DFA for $L$, plus some overhead.
Finding such a minimum Turing program for $L$ might be hard.......
This is discussed in detail in Section 6.8 of Li and Vitanyi's book on Kolmogorov Complexity.

