3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Possible duplicate of Are all irregular languages infinite? $\endgroup$ – xskxzr Feb 14 at 17:56
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Feb 15 at 11:14
6
$\begingroup$

The proof goes something like this:

  • 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.
  • The union of a finite number of regular languages is also regular.
  • Therefore, $A = \{a_0\} \cup \{a_1\} \cup \cdots \cup \{a_n\}$ is regular.
$\endgroup$
  • $\begingroup$ Ahh ok so basically a finite language is just the union of singletons, and since singletons are regular, the union of them is also regular. Thanks! $\endgroup$ – James Pekon Feb 13 at 21:05
  • 1
    $\begingroup$ @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\}$. $\endgroup$ – chi Feb 15 at 15:53
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.