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.

enter image description here

  • $\begingroup$ $aaaababbab$ is in the language but not accepted by your DFA. $\endgroup$
    – nir shahar
    Nov 4, 2021 at 11:55

1 Answer 1


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$:

this one

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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