1
$\begingroup$

$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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – reinierpost Jan 25 '18 at 15:23
  • $\begingroup$ 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.) $\endgroup$ – rici Jan 25 '18 at 17:23
  • $\begingroup$ @Rajesh R: You need to ask a more specific question, to fit the format of this site. $\endgroup$ – reinierpost Jan 25 '18 at 18:10
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 26 '18 at 4:31
  • 1
    $\begingroup$ @RajeshR We can, but this requires more than $O(1)$ space, so we can't implement it using a DFA. $\endgroup$ – Yuval Filmus Jan 26 '18 at 19:17

Your Answer

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

Browse other questions tagged or ask your own question.