# Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.

-

One-line proof: A finite language can be accepted by a finite machine.

Detailed construction: Suppose the language $\mathcal L$ consists of strings $a_1 ,a_2, \ldots, a_n$.

Consider the following NFA to accept $\mathcal L$: It has a start state $S$ and an accepting state $A$. In between $S$ and $A$ there are $n$ different paths of states, one for each $a_i$. The machine can only get from the beginning of the i'th path to the end if it sees exactly the string $a_i$.

There are $\epsilon$-transitions from $S$ to the beginning of each path, and from the end of each path to $A$.

For example, suppose $\mathcal L$ consists of exactly the three stings fish, dog, and carrot. Then the NFA looks like this:

  .-------- f - i - s - h --.
/                           \
S---- d - o - g --------------A
\                           /
'- c - a - r - r - o - t -
`
-

If a language contains the strings $v_1, v_2, v_3,\dots, v_n$, one possible expression is $$v_1\cup v_2\cup v_3 \cup ...\cup v_n=\bigcup_{i=1}^n v_i.$$ $\cup$ is also commonly written $|$, especially on computers. Since there is a regular expression for the language, the language is regular.

-

Another definition of a regular language is one generated by a regular grammar. If $L = \{v_1, v_2, \dots , v_n\}$ then $$S \to v_1 \\ S \to v_2 \\ \vdots \\S \to v_n$$ is a regular grammar of $L$.

-