Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$?

Question

DFA

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$?

For part 2, wouldn't it require M states if the word length is M?

Answer 1

Actually, if you want an automaton that accepts only the word $w_1\ldots w_m$, you'll need $m+1$ states (draw the obvious automaton to accept this word and check how many states it has).

As Steven said in a comment, you're only being asked how many states suffice, so if you can show you can always accept $w_1\ldots w_m$ using $m+1$ states, then that's fine for what the question asks. However, note that re-using a state on a path to an accept state causes the automaton to have a loop in that path, which will cause it to accept infinitely many words. So if you want to accept the language consisting of only that one word, you'll need $m+1$ states.

Answer 2

A language over the alphabet $\Sigma$ will be a regular language given that it follows the following clauses:

1. $\epsilon$, {$a$} for $a\in\Sigma$.
2. If $L_1$ and $L_2$ are regular languages, then $L_1\cup L_2$, $L_1L_2$, and $L^*$ are also regular.
3. $L$ is not a regular language unless taken from those two clauses.

A finite set of words taken from some alphabet will clearly be a regular language. As for the second part, you need $m+1$ states (hint: there is a tiny element in the first clause that should give you the reason to this).