**NFA ****Examples**

This lecture will cover various scenarios of different categories to explain **all examples of NFA**. Below is a list of different categories of **NFA examples**.

- Followed by
- Drawing NFA from a given language
- Must contain
- and many more

We covered NFA in the last lecture. Let’s examine some examples of non-deterministic finite automata (NFA).

** NFA Example 01**

Design an NFA with ∑ = {0, 1} for all binary strings where the **second last bit is 1.**

**Solution**

The language generated by this example will include all strings in which the **second-last bit is 1.**

L= {10, 010, 000010, 11, 101011……..}

The following NFA automaton machine accepts all strings where the **second last bit is 1.** Where,

- {q0, q1, q2} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q0,q1
- δ (q1, 0) = q2
- δ (q1, 1) = q2
- δ (q2, 0) = ϕ
- δ (q2, 1) = ϕ

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0 | q0,q1 |

q1 | q2 | q2 |

q2 | – | – |

**NFA ****Example 2**

Please design an NFA with input alphabet ∑ = {0, 1} that accepts all the **strings that end with 01.**

**Solution**

The language generated by this example will include all strings **that end with 01.**

L= {01, 0101, 0000101, 101, 101001……..}

The following NFA automaton machine accepts all strings that** end with 01.** Where,

- {q0, q1, q2} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0,q1
- δ (q0, 1) = q0
- δ (q1, 0) = fi
- δ (q1, 1) = q2
- δ (q2, 0) = ϕ
- δ (q2, 1) = ϕ

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0,q1 | q0 |

q1 | – | q2 |

q2 | – | – |

**NFA ****Example 3**

Construct an NFA with ∑ = {0, 1} in which each string must contain **“double ‘1’ is followed by single ‘0’.**

**Solution**

The language generated by this example will include all strings **that must contain “double ‘1’ is followed by single ‘0’.**

L= {110, 0110, 1110, 10100110……..}

NFA for the above language is Where,

- {q0, q1, q2,q3} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q3} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q0, q1
- δ (q1, 0) = fi
- δ (q1, 1) = q2
- δ (q2, 0) = q3
- δ (q2, 1) = ϕ
- δ (q3, 0) = q3
- δ (q3, 1) = q3

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0 | q0,q2 |

q1 | – | q2 |

q2 | q3 | – |

q3 | q3 | q3 |

**NFA Example 4**

Design an NFA with ∑ = {0, 1} such that **every string includes the substring 1101.**

**Solution**

The language generated by this example will include all strings **that must contain substring 1101.**

L= {1101, 110101, 1101000101, 01101, 1011011……..}

NFA for the above language is Where,

- {q0, q1, q2,q3,q4} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q4} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q0, q1
- δ (q1, 0) = fi
- δ (q1, 1) = q2
- δ (q2, 0) = q3
- δ (q2, 1) = ϕ
- δ (q3, 0) = ϕ
- δ (q3, 1) = q4
- δ (q4, 0) = q4
- δ (q4, 1) = q4

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0 | q0,q1 |

q1 | – | q2 |

q2 | q3 | – |

q3 | – | q4 |

q4 | q4 | q4 |

**NFA ****Example 5**

Draw an NFA with ∑ = {0, 1} **such that the third symbol from the right is “1”.**

**Solution**

The language generated by this example will include all strings **where the third symbol from the right is “1”.**

L= {100, 111, 101, 110, 0100, 1100, 00100, 100101……..}

NFA for the above language is Where,

- {q0, q1, q2} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q3} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q0,q1
- δ (q1, 0) = q2
- δ (q1, 1) = q2
- δ (q2, 0) = q3
- δ (q2, 1) = q3
- δ (q3, 0) = ϕ
- δ (q3, 1) = ϕ

Transition Table for the above Non-Deterministic Finite Automata is –

States | 0 | 1 |

q0 | q0 | q0,q1 |

q1 | q2 | q2 |

q2 | -q3 | q3 |

q3 | – | – |

**NFA ****Example 6**

Construct an NFA with ∑ = {0, 1} in which **each string must contain “11” followed by “00”.**

**Solution**

The language generated by this example will include **each string must contain “11” followed by “00”.**

L= {1100, 01100, 11100, 011001, 00110001 ……..}

NFA for the above language is Where,

- {q0, q1, q2, q3, q4} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q4} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q0,q1
- δ (q1, 0) = ϕ
- δ (q1, 1) = q2
- δ (q2, 0) = q3
- δ (q2, 1) = ϕ
- δ (q3, 0) = q4
- δ (q3, 1) = ϕ
- δ (q4, 0) = q4
- δ (q4, 1) =q4

Transition Table for the above Non-Deterministic Finite Automata is

States | 0 | 1 |

q0 | q0 | q0,q1 |

q1 | – | q2 |

q2 | q3 | – |

q3 | q4 | – |

q4 | q4 | q4 |

**NFA ****Example 7**

Construct an NFA with ∑ = {0, 1}, where **each string must contain either “01” or “10”.**

**Solution**

The language generated by this example will include **each string must contain either “01” or “10”.**

L= {01, 10, 001, 110, 1110, 0001………..}

NFA for the above language is Where,

- {q0, q1, q2, q3, q4} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2,q4} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0,q1
- δ (q0, 1) = q0,q3
- δ (q1, 0) = ϕ
- δ (q1, 1) = q2
- δ (q2, 0) = q2
- δ (q2, 1) = q2
- δ (q3, 0) = q4
- δ (q3, 1) = ϕ
- δ (q4, 0) = q4
- δ (q4, 1) =q4

Transition Table for the above Non-Deterministic Finite Automata is

States | 0 | 1 |

q0 | q0,q1 | q0,q3 |

q1 | – | q2 |

q2 | q2 | q2 |

q3 | q4 | – |

q4 | q4 | q4 |

**NFA ****Example 8**

Construct an NFA with ∑ = {0, 1} that accepts all strings that **begin with 1 and end with 0.**

**Solution**

The language generated by this example will include all strings that **begin with 1 and end with 0.**

L= {10, 110, 100, 1100, 1110, 1000 ………}

NFA for the above language is Where,

- {q0, q1, q2} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = ϕ
- δ (q0, 1) = q1
- δ (q1, 0) = q2
- δ (q1, 1) = q1
- δ (q2, 0) =
**q2** - δ (q2, 1) =
**q1**

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | – | q1 |

q1 | q2 | q1 |

q2 | q2 | q1 |

**NFA ****Example 9**

Construct an NFA with ∑ = {0, 1} for the language L = {0^{m}1^{n} | m **≥0 and n≥1** }.

**Solution**

The language-generated strings will be like as

When m=0 and n=1, the string will be 1 because 0

^{0}1^{1}=1.When m=1 and n=2, then the string will be 1 because 0^{1}1^{2}=011.When m=2 and n=3, then the string will be 1 because 0^{2}1^{3}=00111.By choosing a random value, i.e., When m=3, n=2, the string will be 1 because 0^{3}1^{2}=00011.And so on.

So, the NFA transition diagram for the above language is Where,

- {q0, q1} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q1} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q0
- δ (q0, 1) = q1
- δ (q1, 0) = ϕ
- δ (q1, 1) = q1

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0 | q1 |

q1 | – | q2 |

**NFA ****Example 10**

Construct an NFA with ∑ = {0, 1} for the language L = {(01)^{n} | **n≥1** }.

**Solution**

The language-generated strings will be like as

When n=1, the string will be 01 because (01)

^{1}=01. When n=2, the string will be 0101 because (01)^{2}=0101. By choosing a random value, i.e., n=5, then (01)^{5}=0101010101. And so on.

So, the NFA transition diagram for the above language is Where,

- {q0, q1, q2} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q1
- δ (q0, 1) = ϕ
- δ (q1, 0) = ϕ
- δ (q1, 1) = q2
- δ (q2, 0) =
**q1** - δ (q2, 1) =
**ϕ**

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q0q1 | q0 |

q1 | – | q2 |

q2 | – | – |

**NFA ****Example 11**

Construct an NFA with ∑ = {0, 1} for the language L = {(01)^{n} | **n≥0** }.

**Solution**

The language-generated strings will be like as

When n=1, the string will be 01 because (01)

^{0}= null. If n=1, the string will be 01 because (01)^{1}=01. By choosing a random value, i.e., n=4, the result will be (01)^{4}=01010101. And so on.

So, the NFA transition diagram for the above language is Where,

- {q0, q1} refers to the set of states
- {0,1} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q1} refers to the set of final states

Transition function δ is defined as

- δ (q0, 0) = q1
- δ (q0, 1) =
**ϕ** - δ (q1, 0) =
**ϕ** - δ (q1, 1) = q0

Transition Table for the above Non-Deterministic Finite Automata is-

States | 0 | 1 |

q0 | q1 | – |

q1 | – | q0 |

**NFA ****Example 12**

Construct an NFA with ∑ = {a,b,c} where strings **contain some “a’s” followed by some “b’s” followed by some c’s.**

**Solution**

The language-generated strings will be like as

L={abc, aabbcc, aaabbcc, aabbbcc, aaaabbbbccc, ………… }

So, the NFA transition diagram for the above language is Where,

- {q0, q1, q2} refers to the set of states
- {a,b,c} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, a) = q0
- δ (q0, b) = q1
- δ (q0, c) =
**ϕ** - δ (q1, a) =
**ϕ** - δ (q1, b) = q1
- δ (q1, c) = q2
- δ (q2, a) =
**ϕ** - δ (q2, b) =
**ϕ** - δ (q2, c) = q2

Transition Table for the above Non-Deterministic Finite Automata is-

States | a | b | c |

q0 | q0 | q1 | – |

q1 | – | q1 | q2 |

q2 | – | – | q2 |

**NFA ****Example 13**

Construct an NFA with **∑ = {a,b,c, ε} ** where strings **contain some “a’s” followed by some “b’s” followed by some “c’s.**

Note: It is now possible to transition through ε because it is being held by ∑.

**Solution**

The language-generated strings will be like as

L={

ε, abc,aabbcc, aaabbcc, aabbbcc, aaaabbbbccc, ………… }

So, the NFA transition diagram for the above language is Where,

- {q0, q1, q2} refers to the set of states
- {a,b,c} refers to the set of input alphabets
- δ refers to the transition function
- q0 refers to the initial state
- {q2} refers to the set of final states

Transition function δ is defined as

- δ (q0, a) = q0
- δ (q0, b) =
**ϕ** - δ (q0, c) =
**ϕ** - δ (q1, a) =
**ϕ** - δ (q1, b) = q1
- δ (q1, c) =
**ϕ** - δ (q2, a) =
**ϕ** - δ (q2, b) =
**ϕ** - δ (q2, c) = q2

Transition Table for the above Non-Deterministic Finite Automata is-

States | a | b | c |

q0 | q0 | q1 | – |

q1 | – | q1 | q2 |

q2 | – | – | q2 |