I am reviewing.
I need to write a DFA that accepts a string w such that bab is not a substring.
Is there any error. Also, any guideline or tips? Since it's a DFA I don't make more than 2 transition from any state and I make sure there is exactly 2 transition state from all states.
My understanding is that NFA may have more than 2 transitions for an alphabet with 2 letters and that's basically the only difference between a DFA and a NFA.
On
This is not correct. Consider $abbbab$. Similarly, I can run $abab$ and it will be accepted.
On state $q_{0}$, you can keep looping on an input of $a$. On an input of $b$, go to state $q_{1}$. Stay at $q_{1}$ on an input of $b$, and transition to state $q_{2}$ on an input of $a$. Transition from state $q_{2}$ to $q_{0}$ on an input of $a$.
For $q_{1}$ and $q_{2}$, transition to $q_{accept}$ on an input of $\epsilon$, the empty string.
In this way, you can never have $bab$ as a substring.
Just reason through it. Can the first letter be 'a' or 'b'? Yes, so you should have two transitions coming from the initial state. If you saw an 'a', what can you see next? Anything right? Well this sounds like the same situation as the initial state, so loop back. Now what if you saw a 'b' first? Can you see a 'b' or an 'a' next? Yes, you can see both! What if you see a 'b'? Then you should just start over in this state (because this was for the first 'b' you saw). But what if you see an 'a' followed by this 'b'? There is only one thing that can come next: 'a' to break the string 'bab'. So the DFA should look something like this.
Edited DFA with properly labeled accept states, a non-accept state (with no outward transitions), and every state has exactly two transitions for 'a' or 'b'.