Design NFA to accept string containing the substring 0101

For reaching the final state q4 , from the start state q0 , a sub-string 0101 is required.

Any string, containing a sub string 0101 will be accepted by the above NFA. The machine can remain in q0, for the portion of string before 0101. The machine can remain in q4 for the portion of string after 0101.

Designing NFA step by step:

Step – 1:

Make initial state “q0” where there is no rule for get output of string as we need 0101 as sub-string. So, in this case, any string can be accept here and for this self-loop of ‘0’ and ‘1’ on initial state “q0“.

Design NFA to accept string containing the substring 0101

Step -2:

Create transition of input alphabet ‘0’ from state “q0” to state “q1“.

Design NFA to accept string containing the substring 0101

Step -3:

After this repeat step 2 to get the output of 0101 as a substring. As in DFA, there is a rule that each state should have an equal alphabet transition. There is no rule for any transition so, there could be an N number of transitions as given below.

In a final state, we have looped the ‘0’ and ‘1’ because 0101 should be substring so, any string is acceptable after 0101.

Design NFA to accept string containing the substring 0101
NFA Transition Diagram

Transition table of above DFA:

Design NFA to accept string containing the substring 0101
NFA Transition Table

In the above table -> represents the initial state, Ф represents the null state or nothing, and * represents the final state. In this post, the initial and final state is same which is the final state.

Recommended:

  1. Introduction to Finite Automata
  2. Deterministic Finite Automata (DFA)
  3. Number of 1’s is a multiple of 3 on {0,1} using DFA
  4. Number of 1’s is not multiple of 3 on {0,1} using DFA
  5. DFA for Number of 1’s is even/odd and number of 0’s is even/odd
  6. DFA for number of 0’s divisible by five and 1’s divisible by 3
  7. DFA for All string of length at most five
  8. DFA for All strings ending with abb
  9. DFA for strings in which leftmost symbol differ from rightmost
  10. Design DFA that contain word ‘CAT’ using word ‘CHARIOT’
  11. Design DFA which accept a binary number divisible by 3
  12. Non-Deterministic finite Automata
  13. Design NFA that accepts string ending with aab

Leave a Comment

Your email address will not be published. Required fields are marked *