Automaton NFA that include substring "aa" and "bb"

Question

$L=\left\{w \in\{a, b\}^{*} \mid a a \text { and } b b \text { are substrings in } w\right\}$ in NFA I draw an intuitive automaton but I'm not sure it is the minimal one: Here is my attempt. I hope someone can lead me.

Answer 1

Please see whether the below DFA (which is of course also an NFA) works?

Description: S is the starting state and AABB is the terminal state, which is also an accepting state. $\{A, B,AA,BB,AAB,BBA\}$ are all intermediary states.

Answer 2

Here are the steps for constructing the NFA algorithmically:

• Let's first construct the regular expression corresponding to the language $L$, simplest regular expression for $L$ is $((a+b)^{*}aa(a+b)^{*}bb(a+b)^{*})$ $+ (( (a+b)^{*}bb(a+b)^{*}aa(a+b)^{*})$.

• Now use the construction algorithm to convert a regular expression to an NFA (the below figure shows the basic building blocks):

• Using the above buliding blocks, construct the NFA to accept the regular expression $(a+b)^{*}aa(a+b)^{*}bb(a+b)^{*}$, as shown in the next figure:

• Similarly, construct the NFA to accept $(a+b)^{*}bb(a+b)^{*}aa(a+b)^{*}$.

• Next, construct the final NFA to accept $((a+b)^{*}aa(a+b)^{*}bb(a+b)^{*})$ $+ (( (a+b)^{*}bb(a+b)^{*}aa(a+b)^{*})$ from the above two NFAs:

• Using the above algorithm you can construct an NFA from a regular expression algorithmically (i.e., using a program).

• Now, you can always get a succinct DFA by state merging using another algorithm (e.g., by eliminating the ε-transitions by subset construction, etc.) to convert NFA to DFA, but the language recognized by both NFA and DFA remains the same.