[Solved]: Automata that recognizes Kleene closure of permutations of three symbols

Problem Detail: 

This is an automata theory homework question.

I need to create DFA that meets the following criteria:

• Alphabet $\Sigma = \{ a, b, c \}$

• Machine accepts empty string and strings of length that is a multiple of three, with every block of three containing one $a$, one $b$ and one $c$.

So far, I came up with this machine, it is obvious:

However, I can't get it to accept empty string. Does it mean there is a transition q0 → q3?

Update1: Following corrections by Dave Clarke I made some corrections.

1. A regular expression for this machine is $(www)^*$ where $w = \{abc,acb,…\}$. Therefore to represent multiple of three, I need to copy this (on the picture) machine 3 times. Final state should have arrows pointing to the first copy, for transitions marked 'a', 'b','c'.
2. As it was pointed out, since this is DFA, I need to add missing states. This can be accomplished by adding "dead" states.
3. Empty string should correspond to $\varepsilon$-transition from qStarting → qFinal.

Update2: As it was pointed out, my regular expression is wrong ! It should be $(w)^*$. Here is the final machine, that I think should be correct.(I didn't include "dead" state)

Asked By : newprint

Answered By : Dave Clarke

There are a few things wrong with this automata:

1. It does not accept the empty string.
2. It is not a DFA – there should be no undefined transitions in a DFA.
3. It only accepts strings of length three, not multiples of three.

You are on the right track. Dealing with 1. and 3. above are fairly straightforward.
Feed in an empty string. What state do you end up in? What does it mean to accept?
Feed in some longer strings. What's the pattern?
Dealing with 2. is rudimentary too, just a matter of filling in the missing transitions.

It's a good idea to read and understand again the definition of DFA, in particular, understanding what is allowed and what is not allowed.

EDIT: Here is a prettier solution:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2233