Introduction to Automata

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-

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-

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-

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-

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 –

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

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

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-

NFA Example 9

Construct an NFA with ∑ = {0, 1} for the language L = {0m1n | 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 0011=1.When m=1 and n=2, then the string will be 1 because 0112=011.When m=2 and n=3, then the string will be 1 because 0213=00111.By choosing a random value, i.e., When m=3, n=2, the string will be 1 because 0312=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-

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-

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-

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-

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-