Which of the following is TRUE?

Answer: Every finite subset of a non-regular set is regular.

Key idea: any finite language is regular.

• Why the correct statement is true:

  A finite language can be described by a regular expression that is the union of its finitely many strings (for example, "w1|w2|...|wk"). Equivalently, build a DFA that recognizes exactly those finitely many strings by encoding a trie of the strings. Therefore every finite subset (being finite) is regular.

• Why the other statements are false (counterexamples):

  • Statement: Every subset of a regular set is regular. Counterexample: The set Σ* is regular, but the subset { a^n b^n | n ≥ 0 } is not regular. Hence a regular superset can contain non-regular subsets.

  • Statement: The union of two non-regular sets is not regular. Counterexample: Over alphabet {a}, let P = { a^n | n is prime } and C = { a^n | n ≥ 1 and n is composite }. Both P and C are non-regular in unary, but P ∪ C equals all non-empty strings a+, which is regular. Thus two non-regular sets can have a regular union.

  • Statement: Infinite union of finite sets is regular. Counterexample: For each n ≥ 0 let S_n = { a^n b^n } (each S_n is finite, therefore regular). The infinite union ⋃_{n≥0} S_n = { a^n b^n | n ≥ 0 } is not regular. So an infinite union of finite sets need not be regular.