1

I am reviewing.

I need to write a DFA that accepts a string w such that bab is not a substring.

enter image description here

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.

george
  • 23
  • I immediately see a way to get 'bab': middle to bottom-middle (b), bottom middle to top right (a), top right to final state (b). – Jared Apr 13 '14 at 01:05
  • Actually I see lots of ways to generate 'bab'. – Jared Apr 13 '14 at 01:06
  • but if I remove the a loop from state 1, it won't be a dfa anymore, right? – george Apr 13 '14 at 01:08
  • Yes it would, it means you can only see a 'b' from the initial state. That's still incorrect and doesn't fix the actual problem I pointed out. – Jared Apr 13 '14 at 01:09
  • but the "final" state is not an accepting state – george Apr 13 '14 at 01:14
  • You can go from the bottom-middle state to the top-left state (b), self loop to the top-left state (a), then top-left to top-middle (b). Since the top middle is labeled as an accept state, this DFA would accept 'bbbab' (assuming the top-left is the initial state). – Jared Apr 13 '14 at 02:00
  • There is an algorithm for generating an NFA for any given conditions and then inserting $\varepsilon$ transitions to convert the NFA to a DFA but I forget it and frankly, unless you are going to program a lexer there is no point in knowing it (since you can usually just figure the DFA out for yourself without it). – Jared Apr 13 '14 at 02:03

2 Answers2

1

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.

ml0105
  • 14,674
1

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'.

Jared
  • 6,227