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.

I'm supposed to construct a DFA which accepts

{ w | w is a word except 'aa' and 'aaa' }

Is this the correct solution? The thick line state is supposed to be the end state.

EDIT

Sry, somehow mixed two different exercises. Corrected.

EDIT 2

Here's the corrected solution(?)!

share|improve this question

migrated from cstheory.stackexchange.com Feb 22 '11 at 15:27

This question came from our site for theoretical computer scientists and researchers in related fields.

    
CSTheory.stackexchange.com is devoted to research-level theoretical computer science. This question looks more like homework. See the faq –  Dave Clarke Feb 22 '11 at 15:19
    
And where would be the right place to post this? –  Trollhorn Feb 22 '11 at 15:20
    
Try math.stackexchange.com ... I'll transfer the question. –  Dave Clarke Feb 22 '11 at 15:26
    
Thanx. Eleven words more. –  Trollhorn Feb 22 '11 at 15:34
1  
You probably want to make the question more self-contained. And finish the last sentence. –  Dave Clarke Feb 22 '11 at 15:37
show 2 more comments

2 Answers 2

up vote 2 down vote accepted

A more general principle in computer programming:

Don't try to build and optimize something in the same time. Most of the time you will get lost in the process and eventually become frustrated and give back.

A second rule is to break a bigger problem into subproblems that can be solved more easily, then combine the solutions to solve the bigger problem. Important note: This is not always the case. Sometimes, it might be harder than you think to combine the solutions. In this case, it is not.

So what you really need?

a. A $DFA$ that recognizes only $aa$.

b. A $DFA$ that recognizes only $aaa$.

c. Combine the solutions of a and b to create a $DFA$ that recognizes $aa$ $OR$ $aaa$ (not how the sentence mentions "and" but I used $OR$. Why is that? Because of the negation of "except". "Except aa and aaa" translates to "exclude the words aa or aaa".)

d. Switch the reject and accept of the last automaton. So you have $NOT$ ($aa$ $OR$ $aaa$). The reject states are those where the automaton would be "trapped" (if you are missing those, make sure you use every symbol in every state, most of the times those are omitted but are useful for learning how DFAs work.

Basically, $NOT$ ($aa$ $OR$ $aaa$) is the regular expression that describes the language you want. You may already know that for every regular expression there is a DFA that recognizes it and vice versa. After working with a few examples, you should be able to empirically detect regular languages for exercises. There are of course examples that are trickier than this one.

Once you have obtained a regular expression, there are known techniques and algorithms that allow you to create first a non-deterministic automaton , convert the NDFA to a DFA and last but not least, optimize the DFA so the least number of states needed is used. I guess that you don't know about these yet, but they are very helpful. If you are following a course on automata, they will come up soon enough, so no worries. Otherwise, I guess you would have to check lecture notes or wikipedia.

share|improve this answer
add comment

Your automaton is not a DFA (consider fourth state from the left on the top row).

Also, your automaton rejects other words besides $aa$ and $aaa$. Can you see why?

share|improve this answer
    
oh, I see, it also rejects bbaa. –  Trollhorn Feb 22 '11 at 16:04
    
okay, is this one correct? docs.google.com/drawings/… –  Trollhorn Feb 22 '11 at 16:43
    
much better! but it still rejects $a$ as well as the empty string. –  Yuval Filmus Feb 22 '11 at 16:48
    
The thick lines should be the end states :-). –  Trollhorn Feb 22 '11 at 16:50
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.