Take the 2-minute tour ×
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.

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?

share|improve this question
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

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.