DFA that contains 1101 as a substring

automata dfa
Waqar Danish picture Waqar Danish · Aug 29, 2017 · Viewed 8.8k times · Source

I have to draw a DFA that accepts set of all strings containing 1101 as a substring in it. I tried one by myself but wanted to make sure if it's correct but can't attach the image as I'm a new user.

Thanks

Answer

Mathews Sunny picture Mathews Sunny · Sep 1, 2017

Its an easy DFA. It requires 5 states.

  1. state 0 :
    • On receiving 1 move from state 0 to state 1
    • On receiving 0 stay on state 0
  2. state 1 :
    • On receiving 1 move from state 1 to state 2
    • On receiving 0 move from state 1 to state 0
  3. state 2 :
    • On receiving 0 move from state 2 to state 3
    • On receiving 1 stay on state 2
  4. state 3 :
    • On receiving 1 move from state 3 to state 4
    • On receiving 0 move from state 3 to state 0
  5. state 4 :
    • On receiving 1 stay on state 4
    • On receiving 0 stay on state 4

So it will look like

Related questions

Design DFA accepting binary strings divisible by a number 'n'

I need to learn how to design a DFA such that given any number 'n', it accepts binary strings {0, 1} whose decimal equivalent number is divisible by 'n'. There will be different DFAs for different 'n', but can somebody give a …

Read More
Finding the complement of a DFA?

I am asked to show DFA diagram and RegEx for the complement of the RegEx (00 + 1)*. In the previous problem I had to prove that the complement of a DFA is closed and is a regular expression also, so I know …

Read More
How are finite automata implemented in code?

How does one implement a dfa or an nfa for that matter in Python code? What are some good ways to do it in python? And are they ever used in real world projects?

Read More