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

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?

-
Note that the problem asks you for what's sufficient, not what's necessary. Proving that M states are sufficient is pretty straightforward - you should be able to draw the DFA that recognizes $w_1w_2\ldots w_m$ pretty easily. It's also true that roughly M states are necessary, but that turns out to be a much harder fact to prove; fortunately that's not what's being asked here. – Steven Stadnicki Feb 20 '13 at 22:32
@StevenStadnicki: What did you mean by your last sentence, exactly? – Tara B Feb 20 '13 at 23:26

2 Answers

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.

-

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

-