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?


For an alphabet of $\{a, b, c\}$ constructing a DFA that accepts all strings not containing the substring 'aa' tells you several things about the number of states you need. Firstly, and this is true for any DFA, you need at least one accepting state. Since your DFA is meant to filter out some strings, it requires a 'trap' or 'dead' state, a state that may never reach an accepting state once reached. Now clearly the strings 'a', 'b', 'c', and '' (empty string) do not contain the substring 'aa', therefore we know our initial state must also be an accepting state, which eliminates the next obvious choice for a new state.

So you know you need at least two states in your DFA, one trap state and one accepting state (which is also your initial state). Now you may also know that to construct a DFA that accepts the string 'aa' would require two states at least, so this gives a good guess that one additional state is required before transitioning to the trap state. So now there are three states to work with, if more are required they should come up as you construct your DFA from there.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.