Which of the following statements about regular languages is NOT true?

Concept

A regular language is one recognized by a finite automaton. Regular languages are closed under certain language operations, but regularity is not automatically inherited by every arbitrary subset.

Application

1. For any language L over an alphabet Σ, L is contained in Σ*. A finite automaton recognizes Σ*, so every language has a regular superset.

2. The empty language ∅ is a subset of every language. A finite automaton can reject every input, so ∅ is regular and every language has a regular subset.

3. Take the regular language Σ* over Σ = {a, b}. It contains {anbn | n ≥ 0}, which is not regular by the pumping lemma; therefore an arbitrary subset of a regular language need not be regular.

4. Every subset of a finite language is finite. Each finite language is regular because a finite automaton can recognize its finitely many strings.

Cross-check and contrast

• The superset claim follows from the universal regular language Σ*.

• The subset claim follows from the regular empty language ∅.

• The finite-language claim follows because subsets preserve finiteness.

Hence, the statement that is NOT true is: Every subset of a regular language is regular.