1
$\begingroup$

I am aware of following two facts related to two concepts: regular languages and finite sets:

  • Regular languages are not closed under subset and proper subset operations.
  • It is decidable whether given regular language is finite or not.

However I feel these facts are quite insufficient to prove whether following statements are true or false:

  1. If all proper subsets of $L$ are regular, then $L$ is regular.
  2. If all finite subsets of $L$ are regular, then $L$ is regular.
  3. If a proper subset of $L$ is not regular, then $L$ is not regular.
  4. Subsets of finite sets are always regular.

I feel 3 is false, as regular languages are not closed under proper subset operation. Right?

But I am unsure of the other points. What facts I am missing to answer above statements true or false?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I see four questions here. Please ask only one question per post. If you have multiple questions you can ask them separately. $\endgroup$ – D.W.♦ Jul 9 '18 at 21:50
  • 1
    $\begingroup$ I understand, but from answer, we can see how these concepts are interlinked and discussing them together at one place definitely adds more to our understanding. We can also think of this as a "single question of how these concepts are interlinked", explored through multiple questions. $\endgroup$ – anir Jul 11 '18 at 19:53
4
$\begingroup$

One useful fact about regular languages is that a union of finitely many regular languages is regular. From this it follows that all finite languages are regular: the language that recognizes a single constant string is always regular, and a finite language is a union of finitely many constant strings.

(Proof: remember that regular languages are exactly those representable by regular expressions. A regular expression can be trivially written to recognize a single constant string. To recognize a finite union of regular languages, simply combine their regular expressions with the union operator. Now you have a (potentially enormous but) finitely-long regular expression recognizing the entire language.)

This means that 1 is true, because a finite set is equal to the union of all its proper subsets, and an infinite language always has a non-regular subset.

(Proof: if a language $L$ is finite, then it has finitely many subsets, and is equal to the union of these subsets. If $L$ is infinite, then it has uncountably many subsets. But there are only countably many regular languages over a given alphabet, because regular expressions are strings and thus can be enumerated. Thus by diagonalization there exists a non-regular subset.)

2, on the other hand, is false as long as there exists an infinite non-regular language. (And such a language does exist: $\{ 0^n 1^n | n \in \mathbb{N} \}$ is a classic example.) It's not regular, but all its finite subsets are finite, and thus regular.

Your intuition is correct: 3 is false. The non-regular language I just mentioned is a proper subset of $\{ 0^a 1^b | a, b \in \mathbb{N} \}$, which is regular.

4 is also true, since any subset of a finite set is always finite.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Can you please mention sources of these facts? I have went through the books by Ullman and Peter Linz but I did not came across these facts. $\endgroup$ – anir Jul 9 '18 at 19:47
  • $\begingroup$ I can provide a proof if you like, but I'm not sure it's worth shoehorning into this question. You're welcome to ask another question, and I'll give the proof there if you like? $\endgroup$ – Draconis Jul 9 '18 at 20:09
  • $\begingroup$ @Draconis, I feel (1) means the language is finite, and thus regular. Can you provide an infinite example? Or proof? $\endgroup$ – vonbrand Jul 11 '18 at 14:15
  • 1
    $\begingroup$ @vonbrand An infinite language always has a non-regular subset. Proof: there are uncountably many subsets of an infinite language, but only countably many regular languages over a given alphabet (because regular expressions are strings and can be enumerated). Thus by diagonalization there must be a subset that is not regular. $\endgroup$ – Draconis Jul 11 '18 at 15:34
  • 1
    $\begingroup$ @anir I added some proofs, because they're fairly short. Does this help? $\endgroup$ – Draconis Jul 11 '18 at 15:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.