# Why is every finite language A ⊆ Σ* regular

So I've been doing regular languages a while and still need a better understanding of why all finite languages A ⊆ Σ* are regular? Is there a formal proof of it or is it just because a DFA can represent any finite language since the states would be finite as well?

• Possible duplicate of Are all irregular languages infinite? – xskxzr Feb 14 '19 at 17:56
• @xskxzr I'd much rather close the other way around. The proofs here that every finite language is regular are much easier to follow than the proofs of the contrapositive in the question you link. – David Richerby Feb 15 '19 at 11:14

• If $$A$$ is a finite language, then it contains a finite number of strings $$a_0, a_1, \cdots , a_n$$.
• The language $$\{a_i\}$$ consisting of a single literal string $$a_i$$ is regular.
• Therefore, $$A = \{a_0\} \cup \{a_1\} \cup \cdots \cup \{a_n\}$$ is regular.
• @JamesPekon Note that, crucially, a finite language is a finite union of singletons. It's important that the union is finite here, since infinite unions of regular languages are not necessarily regular. Indeed, an infinite union of singletons can generate any infinite language, as we can prove exploiting the trivial equality $L = \bigcup_{w\in L}\{w\}$. – chi Feb 15 '19 at 15:53
There is also a direct proof. Let $$P$$ be the set of all prefixes of words in $$A$$. Since $$A$$ is finite, so is $$P$$. We construct a DFA whose states are $$\{ q_p : p \in P \} \cup \{ q' \}$$. The initial state is $$q_\epsilon$$. A state $$q_p$$ is final iff $$p \in P$$. When at state $$q_p$$ and reading $$\sigma$$, if $$p\sigma \in P$$ then we move to $$q_{p\sigma}$$, otherwise we move to $$q'$$. When at state $$q'$$, we always stay in $$q'$$.
What I described above is the minimal DFA. You can get a somewhat simpler DFA by taking an arbitrary superset of $$P$$, such as the set of all words of length at most $$n$$, where $$n$$ is the length of the longest word in $$A$$.