Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 4 down vote accepted

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 -`
share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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