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. NFA examples (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……..}

NFA examples (2)

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-

States01
q0q0,q1q0
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 examples (3)

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-

States01
q0q0q0,q2
q1–q2
q2q3–
q3q3q3

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-

States01
q0q0q0,q1
q1–q2
q2q3–
q3–q4
q4q4q4

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 examples (5)

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 –

States01
q0q0q0,q1
q1q2q2
q2-q3q3
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 examples (6)

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

States01
q0q0q0,q1
q1–q2
q2q3–
q3q4–
q4q4q4

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 examples (7)

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

States01
q0q0,q1q0,q3
q1–q2
q2q2q2
q3q4–
q4q4q4

 

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 examples (8)

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-

States01
q0–q1
q1q2q1
q2q2q1

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.

NFA examples (9)

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-

States01
q0q0q1
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.

NFA examples (10)

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-

States01
q0q0q1q0
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.

NFA examples (11)

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-

States01
q0q1–
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, ………… }

NFA examples (12)

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-

Statesabc
q0q0q1–
q1–q1q2
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, ………… }

NFA examples (13)

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-  

Statesabc
q0q0q1–
q1–q1q2
q2––q2