# Need help with constructing a DFA

I am trying to construct the DFA that accepts the following language

$$L_2 := \left\{ w \in \{a,b\}^* \mid \#a(w) \text{ is divisible by } 3 \text{ and } \texttt{babbab} \text{is a substring of } w \right\}$$

My solution is illustrated below. I feel like my current solution is incomplete/wrong. • $aaaababbab$ is in the language but not accepted by your DFA. Nov 4, 2021 at 11:55

Here's an idea to construct such a DFA. Consider differently the two parts of the language: $$L = L_1 \cap L_2$$ where $$L_1 = \{u\in\{a,b\}^*\mid |u|_a \equiv 0 \mod 3\}$$ and $$L_2 = \{ubabbabv\mid u,v\in \{a,b\}^*\}$$.

Note that I reworded "being divisible by $$3$$" into "being equal to $$0$$ modulo $$3$$". This will help to contruct the automaton.

For such an automaton, you need to keep track of the value of $$|u|_a \mod 3$$. This can be done using only three states. An automaton recognizing $$L_1$$ could be the following one, where $$q_i$$ denotes the state where $$|u|_a \equiv i \mod 3$$: Now to build an automaton recognizing $$L$$, you can first build an automaton recognizing $$L_2$$, then triple each states and completing transitions according to the value of $$|u|_a$$.

Though, honestly, this is very tedious and annoying. The person giving this assignment could have chosen a short substring condition.

• Wow, thank you for your help! I don't think I could've done it in such a simplistic, yet effective way. Nov 4, 2021 at 19:35