$B = \{w \mid w = xbaby,\text{ where }x, y \in \Sigma^*\}, \Sigma = \{a, b\}$ - DFA

Question

I am having some trouble with this problem. I believe that the language that $B$ recognizes must included a substring "$bab$" in-order to ever hit an acceptance state. Below is a screenshot of my current progress. I was hoping for a hint into the right direction as I am not really sure how to procced.

Answer 1

First off, recall that for a DFA each node has to have exactly one edge per symbol in your alphabet. Thus your first node cannot have two edges labelled B and the same goes for the second.

Indeed the language is as you describe given by all strings which contain the substing "bab". To draw the automata, note that (I label the node so that their name represents the substring I am currently reading.)

• Node "0": start with a node. if you read an A you stay there, if you read B then you head to the node "B"
• Node "B": if you read a B you stay here, if you read A you advance to the node "BA"
• Node "BA": if you read a B you go to the node "BAB", if you read A you have to discard the current substring and go back to node "0"
• Node "BAB": this is a dead end. Once you are in this accepting state anything you read will remain in this node.

Answer 2

The automaton that you’ve diagrammed is not a DFA: for instance, you have two different $b$ transitions out of the initial state, something that is not possible for a deterministic finite automaton.

If $q_0$ is the initial state, you want the automaton to loop at $q_0$ as long as it is reading $a$s, not $b$s; a $b$ should send it to state $q_1$. We’ll use $q_1$ to mean I've just read a $b$, so the DFA should loop at $q_1$ as long as it continues to read $b$s. If it eventually reads an $a$ while in $q_1$, we’ll send it to $q_2$ and use that state to mean that it has just read $ba$. If it gets an $a$ at this point, that $ba$ is wasted, and in effect it’s starting over, so an $a$ should send it back to $q_0$. A $b$, on the other hand, completes the $bab$ subsequence, so the word is now known to be in $B$ and should be accepted; a $b$ should therefore send the DFA to an acceptor state $q_3$ that is a ‘sink’, meaning that every input at that point just loops the DFA at $q_3$.

Answer 3

Hint: You need to include more states with $g_0\overset b\to g_1\overset a\to g_2\overset b\to g_3$ and any time the substring would 'go wrong' just send back to $g_0$.
Also, you need to allow anything on the end state.