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

• Exactly what is your input, and what is your model of computation? Aug 24, 2011 at 7:49
• The input is a string (sequence of letters), and model of computation is a RAM machine. Of course, in degenerate cases (such as when membership in $L$ is determined by the 1st letter), we don't need to read the whole string -- but in general, we obviously do. I'll edit the question to make it more formal. Aug 24, 2011 at 8:12
• I think you are not expressing what you have in mind correctly, take $A_i$s to be one state machine that accepts everything, membership in $L(A_i)$ is decidable in constant time. You want a sequence of atuomata which is hard not easy so you should say it is not decidable in $O(|x|\log |A_i|)$. Also you need to use uniform version (i.e. the automaton should be part of the input), otherwise you will ran into problems with non-uniformity (let $A_i$ accepts 0 iff $i\in K$). Aug 24, 2011 at 8:42
• Let $A_i$ only accept $0^{i}$. The minimal DFA has size $i$, the problem can be solved in $O(\min\{|x|,\log i\})$. (ps: I personally don't see what you are trying to do, may be you should explain it a little bit more in the question.) Aug 24, 2011 at 9:28
• The point is that I have a specific family of DFAs in mind and would like to argue a lower bound on the decision problem! Aug 24, 2011 at 9:33

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

• Yep. The classical (counter)example to show that going from NFA to DFA cannot always be efficient. But, to use your words, I would say that running this Turing machine is indeed the same as running the DFA implicitly, but not the same as running the DFA. Aug 24, 2011 at 14:48
• @Aryeh I didn't quite get your answer. Please could you elaborate? I thought you mentioned in the question that "Suppose I know that the minimal DFA for L has N states.", hence I am assuming that small n (n) and capital n (N) are distinct. Nov 1, 2013 at 3:35

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.

• Thanks for the pointer, I'll read the book. But I still have a feeling we're arguing more about definitions than about essence. I've added edit2 to try to capture this "essence". Aug 24, 2011 at 10:28
• Eh, I was about to delete this answer. I shouldn't post when I am just waking up. I will leave it up since you seemed to appreciate the pointer. I don't like my answer because it deals with program length, not runtime. Aug 24, 2011 at 10:56

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

• whoops, I see another answer came in while I was writing this. I have to run right now, but will remove my answer when I get back if it is redundant. Aug 24, 2011 at 14:43