I'm trying to make a Deterministic Finite Automaton (DFA) to accept binary strings that start with "1" and have a substring "11" in it, over {0,1}.
Here is the DFA I created:
Problem:
What I've Tried:
Question:
What is the issue with my DFA design? How can I make the DFA processes the string correctly?
It is clear from your DFA that after the input "10", it ends up in the "trap" state. This is not right. The only time there is no possibility anymore to get a valid input is when the input starts with "0". For any input that starts with "1" there should always be a way to extend the input to get into the accept state. So there should be no transition from state q1 to the "trap" state.
You need an additional state, q3, which is the state where you have read one or more "0" (which potentially can still be followed by a "1" or even "11").
Here is how your DFA would look with that additional state: