Design NFA that accepts string ending with aab

The Language accepted by the above NFA consist of string ending in aab. A string length n, ending in aab can be accepted by the above NFA if:

  • The machine remains in q0 for the first n-3 inputs.
  • On the last three inputs aab, the machine makes the transition as shown below:
Design NFA that accepts string ending with aab

To reach the final state, and to remain there, it is necessary that the two character of the string should be 10.

Thus the NFA accepts a string, if and only if it ends in 10.

Designing NFA step by step:

Step – 1:

Make initial state “q0” where there is no rule for getting the output of string as we need string ending with aab. So, in this case, any string can be accepted here and for this self-loop of ‘a’ and ‘b’ on the initial state “q0“.

Design NFA that accepts string ending with aab

Step -2:

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

Design NFA that accepts string ending with aab

Step -3:

After step 2 transition of input alphabet ‘a’ from the state “q1” to state “q2“ to get ending with aab.

Design NFA that accepts string ending with aab

Step -4:

After this repeat the above step to get the output string ending with aab. 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 need string ending with aab so, there will be not transition in final state.

Design NFA that accepts string ending with aab
NFA Transition Diagram

Transition table of above NFA:

Design NFA that accepts string ending with aab
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 to accept string containing the substring 0101

Leave a Comment

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

x