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.
Infinite intersection of regular languages 2026-10-31
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 putThe 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 . ConsequentlyThe 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.