computer-scienceautomatonfinite-state-automaton

DFA for input starting with "1", and having "11" in it. Why it doesn't accept this input?


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:

enter image description here

Problem:

What I've Tried:

Question:

What is the issue with my DFA design? How can I make the DFA processes the string correctly?


Solution

  • 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:

    enter image description here