Finite language 2026-10-31
A formal language with finitely many words. Every finite language is a regular language: take a finite union of the regular expressions spelling its members, with the empty language represented separately when there are no members.
Regular languages are closed under finite intersection, but not countably infinite intersection. Indeed, for any formal language over a finite alphabet, let contain every word of length at least , together with the members of of length less than . Each is a regular language, since its exceptional short part is a finite language, and . Thus every formal language, including one that is not a regular language, can arise in this way.
No: regular languages are not closed under countably infinite intersection. Let and put
The first term in has regular expression , where the fixed power means copies. The second term is a finite language, a finite union of single words. Their union is therefore a regular language.
If , then for each either or belongs to the second term, so . If , choose . It belongs to neither term of . Consequently
The formal language is not a regular language. Indeed, for a proposed pumping length , the pumping lemma for regular languages applied to must pump a nonempty block consisting only of zeros. Repeating that block increases the number of zeros without increasing the number of ones, leaving . This contradiction proves the counterexample. Finite intersection closure does not extend to this infinite intersection of regular languages.