Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
