DFA for all strings avoiding 'aa'

Question

I'm trying to draw a dfa for this description

The set of strings over {a, b, c} that do not contain the substring aa,

current issue i'm facing is how many states to start with, any help how to approach this problem?

Answer 1

It seems to me that you can do this with three states, whose "meanings" are:

(1) I haven't seen two consecutive $a$'s and either I'm just starting (haven't seen anything yet) or the last symbol I saw was not $a$.

(2) I haven't seen two consecutive $a$'s but the last symbol I've seen was $a$.

(3) I've seen two consecutive $a$'s.

Answer 2

A regular expression for this language is $(b\cup c\cup ab\cup ac)^*(a\cup\lambda)$, there $\lambda$ is the empty string. To define a DFA recognizing this language, let the state space be $Q=\{q_0,q_a,q_{aa}\}$, the alphabet $\Sigma=\{a,b,c\}$, the initial state $q_0$, the accept states $F=\{q_0,q_a\}$, and the transition function $\delta$ given by $$ \delta(\alpha,q) = \begin{cases} q_0,& \alpha\in\{b,c\}, q\in\{q_0,q_a\}\\ q_a,& \alpha=a, q=q_0\\ q_{aa},& \alpha = a, q=q_a\\ q_{aa},& \alpha\in\Sigma, q=q_{aa}. \end{cases} $$