Construct finite Automata

Question

Im trying to construct finite automata in the form of diagrams accepting certain languages.

One is in all parts the alphabet is $\{a, b\}$. Construct FA $\{w \mid w \text{ has neither $aa$ nor $bb$ as a subword}\}$

I understand that for any word with $aa$ or $bb$ in it, it should not be able to get in to finite state. How ever, after drawing many diagrams with a trial and error approach I'm not really getting anywhere.

How can I construct a FA diagram to prove this rule?

Thanks, Ciaran

Answer 1

1. Start in state $q_i$
2. If you are an in state $q_i$ and read $a$ then move to $q_a$
3. If you are an in state $q_i$ and read $b$ then move to $q_b$
4. If you are an in state $q_a$ and read $a$ then move to $q_{aa}$
5. If you are an in state $q_a$ and read $b$ then move to $q_b$
6. If you are an in state $q_b$ and read $a$ then move to $q_a$
7. If you are an in state $q_b$ and read $b$ then move to $q_{bb}$
8. accept in $q_a, q_b$ and reject in $q_{aa}, q_{bb}$.

Answer 2

You only need three states for an incomplete deterministic automaton. Just add a sink state and the corresponding transitions (dashed transitions in the diagram below) to get a complete DFA for your language.