# Automata that recognizes Kleene closure of permutations of three symbols

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)

• 1) The automaton does not accept anything to the $^*$; it has no (directed) cycles, so the accepted language is finite. 2) For accepting the empty string, just make the initial state accepting and ensure it is never revisited. 3) Creating a regular expression first is a good idea; going from there to an automaton in a mechanical way is easy. You regular expression is wrong, though; it allows only strings with length a multiple of nine. – Raphael Jun 5 '12 at 18:45
• 4) Whether a DFA has to be complete depends on the definition. As you note, that is a technical, not a conceptual issue. 5) What you propose in 3. only works in general if the target final state is a sink. – Raphael Jun 5 '12 at 18:46
• There are no $\epsilon$-transitions in a DFA. And as Tsuyoshi Ito points out below, the missing transitions don't matter so much. – Dave Clarke Jun 5 '12 at 18:56
• Still wrong. It doesn't accept the empty string. – Dave Clarke Jun 5 '12 at 20:31
• @Raphael: Are such sneaky transitions permitted in DFAs? I think not. – Dave Clarke Jun 6 '12 at 11:07

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:

• I agree with all points, but I would like to add that some books (old ones, I think) define DFA in such a way that they can have missing transitions. – Tsuyoshi Ito Jun 5 '12 at 17:49
• Dave, following your suggestions, I made all three corrections. Thanks ! – newprint Jun 5 '12 at 18:25
• Looks way better than my solution !!!! – newprint Jun 7 '12 at 15:40
• Combining the inital and final states was the key step you missed. The layout was done using Omnigraffle. I was surprised by the result. – Dave Clarke Jun 7 '12 at 15:52