Finite automata problem

Question

I need to draw a finite automata over the alphabet $\{a,b,c\}$, such that the following properties hold:

• a word starts with at most two $a$
• a $c$ is always followed by an even number of $b$ (0 included)
• each word has at least size $1$

I came up with the automata below, which is both incomplete (for example at state $4$ there is no transition for input $c$) and non-deterministic (at state $6$ for input $b$ the machine goes to states $4$, $7$).

It clearly accepts the words like $aa, baa, aacbbcbbbb$ that fit the above properties, but, I don't exactly know whether my automata is actually correct (meaning for any word that can be formulated from the above properties), and whether a simpler version of it can be devised, maybe even one that is complete and/or deterministic?

Answer 1

There is a mistake, you automaton does not recognize $abaa$ whereas it should. This can be fixed by making the $b$ transition from state $2$ (the "I started with an $a$" state) go to state $5$ (the "normal" state).

Also, I don't see the purpose of state $7$, it seems you could just add a self-transition on state $4$ with label $c$.

If you do that and add a "trash" state which you use for all transitions you did not write (to make it complete) you get a complete deterministic one with $7$ states.

Answer 2

Let $A = \{a,b,c\}$. The constraints defining your language lead to the following formula, as you want to avoid three leading $a$'s, a suffix of the form $cb^{2n+1}$ and a factor of the form $cb^{2n+1}a$ or $cb^{2n+1}c$. $$ L = A^+ - \Bigr(aaaA^* + A^*c(bb)^*b\bigr(1 + (a+c)A^*\bigr)\Bigl) $$ The complement of this language is $$ K = 1 + aaaA^* + A^*c(bb)^*b\bigl(1 + (a+c)A^*\bigr). $$ You can now use standard techniques to compute the minimal DFA of $K$. Then just change the final states to get the minimal DFA of $L$.

The transitions of the minimal automaton of $L$ are given below

    1  2  3  4  5  6
 a  2  5  0  6  0  6
 b  6  6  4  3  6  6
 c  4  4  0  4  4  4

The initial state is $1$ and the set of final states is $\{2, 4, 5, 6\}$.