2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – D.W. Aug 8 '17 at 20:27
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – user2357112 Aug 8 '17 at 23:31
  • $\begingroup$ @user2357112 No. Consider any language $L\subseteq\{a\}^*$. We have $|L\cap\{a\}^n|\leq 1$ but $L$ can be infinite. $\endgroup$ – David Richerby Aug 8 '17 at 23:40
  • $\begingroup$ Oh - I was thinking of strings up to length $n$, not exactly length $n$. $\endgroup$ – user2357112 Aug 8 '17 at 23:44

Your Answer

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