*63*

# Examples of NFA

### Example 1:

Design a NFA for the transition table as given below:

Present State | 0 | 1 |
---|---|---|

â†’q0 | q0, q1 | q0, q2 |

q1 | q3 | Îµ |

q2 | q2, q3 | q3 |

â†’q3 | q3 | q3 |

**Solution:**

The transition diagram can be drawn by using the mapping function as given in the table.

Here,

### Example 2:

Design an NFA with âˆ‘ = {0, 1} accepts all string ending with 01.

**Solution:**

Hence, NFA would be:

### Example 3:

Design an NFA with âˆ‘ = {0, 1} in which double â€˜1â€™ is followed by double â€˜0â€™.

**Solution:**

The FA with double 1 is as follows:

It should be immediately followed by double 0.

Then,

Now before double 1, there can be any string of 0 and 1. Similarly, after double 0, there can be any string of 0 and 1.

Hence the NFA becomes:

Now considering the string 01100011

### Example 4:

Design an NFA in which all the string contain a substring 1110.

**Solution:**

The language consists of all the string containing substring 1010. The partial transition diagram can be:

Now as 1010 could be the substring. Hence we will add the inputs 0â€™s and 1â€™s so that the substring 1010 of the language can be maintained. Hence the NFA becomes:

Transition table for the above transition diagram can be given below:

Present State | 0 | 1 |
---|---|---|

â†’q1 | q1 | q1, q2 |

q2 | q3 | |

q3 | q4 | |

q4 | q5 |