1
$\begingroup$

A language I'm investigating is not regular since the minimal DFA for the language grows depending on input string size. However, while the number of non-final states increases, the final states are the same small strictly finite core which include the initial state.

Another question looks superficially similar, hinting that what I'm looking for might be an interpretation of this language as a generalization of a prefix-code in order to ignore the infinite non-final states.

Are there methods to treat this 'pseudo-regular' language as regular (or any other language class with efficient algorithms) for purposes of intersection and path finding from the small final state set back to the inital state, thus sidestepping the issue that the complete DFA is not finite in size?

Improve this question
$\endgroup$
2
  • $\begingroup$ What do you mean by "path finding from the small final state set back to the initial state"? $\endgroup$
    – Yuval Filmus
    Aug 8, 2017 at 16:12
  • $\begingroup$ I don't quite see the connection, but perhaps it's better if you formulated a concrete question, formally defining the class of languages you're interested in, formally defining an algorithmic task, and asking whether this task can be accomplished efficiently on your class of languages. $\endgroup$
    – Yuval Filmus
    Aug 8, 2017 at 16:21

1 Answer 1

Reset to default
1
$\begingroup$

Your question is missing quite a few definition, but here is my interpretation.

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.

Note that if the minimal DFA for a language has $m$ accepting states, then every DFA for the language has at least $m$ accepting states (this follows from Myhill–Nerode theory). Therefore we obtain an equivalent definition if we replace "some DFA" with "the minimal DFA".

Using the product construction, you can easily show that the class of finite-regular languages is closed under union and intersection, and more generally under monotone set operations.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I made up this term for the sake of the answer. There might be a standard term, but I doubt it. $\endgroup$
    – Yuval Filmus
    Aug 8, 2017 at 16:34

Your Answer

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