# Simulating DFA operations on non-regular languages with finite final state set

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?

• What do you mean by "path finding from the small final state set back to the initial state"? Aug 8 '17 at 16:12
• 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. Aug 8 '17 at 16:21

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