Automaton NFA that include substring "aa" and "bb" $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.
 A: 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.
A: 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.
