# Set of infinite DFA's

$INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\}$

Here $(A)$ denotes the encoding of DFA

Is above language regular, CFL or recursive ?

I know that above language is recursive for sure. I am not able to decide whether it's regular or not.

For regular, we know that regular languages are not closed under infinite union. So maybe above language is not regular but I couldn't think of an example where Union of infinite regular languages is not regular.

Can someone help me?

• Your approach doesn't seem to work: infinite union is a union of infinitely many languages, not a union of (finitely many) infinite languages. Regular language are closed under the latter. Jan 25, 2018 at 15:23
• Nothing in the question has anything to do with unions of languages. The language $INFINITE_{DFA}$ is a set of strings, each of which in some way represents a language. It is not the union of the languages represented. (If it were, it would include the (regular) language consisting of all possible strings, which would therefore be the union. But that's a completely different question.)
– rici
Jan 25, 2018 at 17:23
• @Rajesh R: You need to ask a more specific question, to fit the format of this site. Jan 25, 2018 at 18:10
• Regular languages are really weak. Checking whether a DFA generates an infinite language boils down to directed reachability, an NL-complete problem which is beyond the power of regular languages. Jan 26, 2018 at 4:31
• @RajeshR We can, but this requires more than $O(1)$ space, so we can't implement it using a DFA. Jan 26, 2018 at 19:17