0

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:

  • Input String: "10011"
  • Expected Result: Accepted
  • Actual Result: Rejected

What I've Tried:

  • I traced the transitions for the string "10011" through my DFA, but I ended up in a non-accepting state.
  • I've double-checked my state transitions and acceptance states, but I can't figure out where I might have gone wrong.

Question:

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

Improve this question
0

1 Answer 1

Reset to default
-1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

@Rishi, any feedback on this answer?
Thank You so much for helping. Appreciate it.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.