Design NFA that start with 01 and end with 10

A string 010 (starting with 01 and ending with 10 ) can be accepted through the path

For any other string, the portion between starting 01 and ending 10 can absorbed by the state q2.

Designing NFA step by step:

Step – 1:

Make initial state “q0”.

Design NFA that start with 01 and end with 10

Step -2:

As  “q0” is initial state transition from state “q0” to state “q1“ will 0 to start string from 01.

Design NFA that start with 01 and end with 10

Step -3:

Then create a transition from the state “q1” to state “q2“ will be 1 and there could be any string between 01 and 10 so, self-looping the “q2“ with 0 and 1.

Design NFA that start with 01 and end with 10

Step -4:

As the starting string has been creating know we have to generate a string ending as 10 so, the transition from the state “q2” to state “q3“ will be 1.

Design NFA that start with 01 and end with 10

Step -5:

As string 010 is also accepted so, connect “q1” and “q3“ transition will be of 1.

Design NFA that start with 01 and end with 10

Step -5:

At final q4 will the final state and transition of input alphabet 0 from the state “q3” to state “q4“ and we have got all condition of start with 01 and end with 10.

Design NFA that start with 01 and end with 10
NFA Transition Diagram

Transition table of above NFA:

Design NFA that start with 01 and end with 10
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
  14. Design NFA to accept string containing the substring 0101
  15. Differentiate between NFA and DFA

Leave a Comment

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

x