Deterministic Finite Automata with 6 states

Question

I am really new to this and to sure how to start. I am trying to do this question for practice

Let segma = {a,b}. Consider the set of all strings in segma* that have an odd number of occurrences of the substring "ab" but do not have "bb" as a substring. Give a DFA with six states accepting the set.

I did change my solution.

Answer 1

Here is an idea of how to approach this question. Think about the conditions you need to meet.

First, you need to have an odd number of "ab", which means your DFA should have a "counter" loop that every time you encounter odd number of "ab", your DFA will be in a state, such that this state has an edge that allows your DFA to move toward the accepting state. Conversely every time you encounter even number of "ab", your DFA should be in a state, such that this state cannot move forward, unless you encounter another "ab".

Second, the string cannot have "bb". This means that if you ever encounter a single "b", a subsequent "b" will drive your DFA to a sink, which means your DFA rejects the string.

It might be easier to associate each character condition to the edges, so that if a certain condition is met, your DFA can move to a certain state.