# Complexity of membership testing for finite-regular languages

A language $$L \subseteq \Sigma^*$$ is finite-regular if there exists $$C$$ such that for all $$n$$, $$L \cap \Sigma^n$$ is accepted by some DFA with at most $$C$$ final states.

Given a finite-regular language $$A_L$$, am I guaranteed that there exists a polynomial-time algorithm $$A_L$$ that recognizes $$L$$? In other words, I want an algorithm such that on input $$x$$ it returns true or false according to whether $$x \in L$$ or not, and the running time is polynomial in the length of $$x$$. Is this guaranteed?

Note that the number of states of the complete DFA accepting such $$L$$ may be $$O(|\Sigma|^n)$$ so any trivial algorithm actually constructing the full DFA would not be polynomial time. However the number of accepting final states is $$O(1)$$, which leads me to believe there is some shortcut available here.

Thanks to Yuval Filmus for formalizing this language class, and explaining its closure properties.

• Let me know whether my edit accurately captures your intent. Am I right that you allow the algorithm to depend on the language $L$? Or do you want a single universal algorithm that on input $x$ and a specification of the language $L$, tests whether $x \in L$? If the latter, how are you planning to specify $L$?
– D.W.
Aug 8 '17 at 20:27

Finite-regular languages need not even be decidable. Indeed, if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\{ 1^n : \text{ the$n$th Turing machine halts on the empty input} \}$ is finite-regular but not decidable.
• "if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$" - I must be missing something. Wouldn't such a language be finite? Aug 8 '17 at 23:31
• @user2357112 No. Consider any language $L\subseteq\{a\}^*$. We have $|L\cap\{a\}^n|\leq 1$ but $L$ can be infinite. Aug 8 '17 at 23:40
• Oh - I was thinking of strings up to length $n$, not exactly length $n$. Aug 8 '17 at 23:44