If we know that a language is regular, we can solve the set membership question for a given string by running it through the corresponding DFA for that language. But what about the other way? Means, if set membership question can be solved for a particular language does this imply that the language is regular?

  • $\begingroup$ If either of the answers addressed your question sufficiently, please select one of them. $\endgroup$ – G. Bach Oct 21 '15 at 11:56

Since any irregular, but decidable language answers the question with "no, there are irregular languages that are decidable", maybe some nuance for how this relates to the usual complexity classes.

For one thing, every regular language has at most linear time complexity (just use a DFA that recognizes the language and run the word on it and check whether you end up in an accepting state). Therefore, the deterministic time hierarchy theorem implies that there are languages that are decidable, but irregular, since it implies that the set of languages that, say, require at least quadratic but at most cubic time is nonempty; similarly for languages that require $\Theta(2^{2^{2^n}})$ time. On the other hand, there are irregular languages that have linear time complexity, as illustrated by the example $\{a^nb^n : n \in \mathbb{N}\}$ that David gave.

Another surprising thing I became aware of only recently is that SAT, the NP-complete problem of deciding whether a CNF formula is satisfiable, is context-sensitive. To see this, remember that the automata recognizing context-sensitive languages are the linear bounded automata, which are nondeterministic Turing machines that are only allowed to use the space used for the input (or alternatively, only use linearly much additional space - using a speedup theorem, those definitions should be equivalent); here are references on the matter.

And finally, a restricted version of the question ("does NP-completeness imply regularity?") can be answered by "no, there are irregular languages that are NP-complete". If P=NP, then all irregular languages that can be decided in polytime are NP-complete (since the reduction has all the power required for deciding any NP-problem, and so reductions always work), and if P$\neq$NP, then all NP-complete languages are irregular: if they weren't, then there would be a regular language that is NP-complete, but regular languages can be decided in linear time, contradicting P$\neq$NP.

So to sum up: decidability doesn't tell you much about where in the complexity zoo we are, and even knowing a language can be solved in linear time doesn't tell you anything about regularity. On the other hand, irregularity doesn't tell you much about time complexity either (maybe that implies that the language requires at least linear time - but I can't prove that off the cuff, not sure it's true!).

  • $\begingroup$ Maybe one last comment: constant time complexity does imply regularity, since the deciding TM can only produce constantly many different configurations in constant time, and so we can translate those to states and build a finite automaton that way. $\endgroup$ – G. Bach Oct 14 '15 at 20:04

No. The language is only regular if its set membership problem can be decided by a DFA. For example, the set membership problem of the language $\{a^nb^n\mid n\geq 0\}$ can be solved but this language is known not to be regular (e.g., by the pumping lemma).

Thanks to reinierpost for pointing out that this is way simpler than I was originally making it, and for persisting when it took me multiple hours to understand that.

  • 2
    $\begingroup$ Or to put it in more concrete terms: regular languages are those for which membership can be tested in an amount of memory that depends only on the problem, not on the particular input. $\endgroup$ – Gilles 'SO- stop being evil' Oct 13 '15 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.