For reaching the final state q_{4} , from the start state q_{0} , 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 q_{0}, for the portion of string before 0101. The machine can remain in q_{4} for the portion of string after 0101.

**Designing NFA step by step:**

### Step – 1:

Make initial state “q_{0}” 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 “q_{0}“.

**Step -2:**

Create transition of input alphabet ‘0’ from state “q_{0}” to state “q_{1}“.

**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.

Transition table of above DFA:

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

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