Complexity lower bound for regular languages

Question

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

Answer 1

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

Answer 2

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:

1. $L$ is regular.

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

Answer 3

I am not 100% sure if this satisfies your condition for non-trivial, but here is a partial counter-example.

Take a decision problem $P$ which has a uniform circuit-complexity that is $O(n^{1 - \epsilon})$. For each $n$ consider the $L'_n$ that accepts only those strings that are in $P$ and have length $n$. This $L'_n$ probably has exponential size (if you pick $P$ carefully), however this is a language that accepts based on finite prefix; thus needs to be modified to achieve condition (c). Define $L_n = (L'_n)^*$ (i.e map the initial state an accepting one, and map each accepting state to the initial state).

Given an input $(n,x)$ build the circuit $C_n$ run it on $n$-bit chunks of $x$.