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).

Category 1: Accept all strings

The first category will explain an NFA that accepts all strings over the alphabet symbols, which includes every possible combination of these symbols, including the empty string ε.

NFA Example: 1.1

Design an NFA over the alphabet Σ = {a, b} that accepts any string formed using the symbols “a” or “b”.

Solution

The language generated by this example will include the following strings

L = {ε, a, b, ab, ba, aba, aab, baa, ………….}

The following NFA automaton machine accepts all strings formed using the symbols a or b.

5 Tuples of the above NFA are given below,

• {q0} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) = q0
  • δ (q0, b) = q0
• q0 refers to the initial state
• {q0} refers to the set of final states 

The State Transition Table for the above NFA is given below

States	a	b
q0	q0	q0

NFA Example: 1.2

Design an NFA over the alphabet Σ = {a, b,c,d} that accepts any string formed using the symbols “a”, “b”, “c”,  or “d”.

Solution

The language generated by this example will include the following strings

L = {ε, a, b, c, d, ab, ba, ac, ca, ad, da, abc, abcd, ………….}

The following NFA automaton machine accepts all strings formed using the symbols “a”, “b”, “c”,  or “d”.

5 Tuples of NFA are given below,

• {q0} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) = q0
  • δ (q0, b) = q0
  • δ (q0, c) = q0
  • δ (q0, d) = q0
• q0 refers to the initial state
• {q0} refers to the set of final states 

The state transition table for the above NFA is given below

States	a	b	c	d
q0	q0	q0	q0	q0

Category 2: Start with

The second category will explain an NFA that accepts all strings that start with some fixed alphabet symbols

NFA Example: 2.1

Design an NFA over the alphabet Σ = {a, b} that accepts only the strings that start with “b”

Solution

The language generated by this example will include all strings that start with “bab”

L = {b, ba, bb, bab, baa……..}

The following NFA machine accepts all strings that start with “b”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) =ϕ
  • δ (q0, b) = q1
  • δ (q1, a) = q2
  • δ (q1, b) =q2
• q0 refers to the initial state
• {q1} refers to the set of final states

The transition table for the above NFA is given below

States	a	b
q0	ϕ	q1
q1	q1	q1

NFA Example: 2.2

Design an NFA over the alphabet Σ = {a, b} that accepts only the strings that start with “bab”

Solution

The language generated by this example will include all strings that start with “bab”

L = {bab, baba, babb, babab, babba……..}

The following NFA automaton machine accepts all strings that start with “bab”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) =ϕ
  • δ (q0, b) = q1
  • δ (q1, a) = q2
  • δ (q1, b) =ϕ
  • δ (q2, a) = ϕ
  • δ (q2, b) = q3
  • δ (q3, a) = q3
  • δ (q3, b) = q3
• q0 refers to the initial state
• {q3} refers to the set of final states

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

States	a	b
q0	ϕ	q1
q1	q2	ϕ
q2	ϕ	q3
q3	q3	q3

 

NFA Example: 2.3

Design an NFA over the alphabet Σ = {a, b} that accepts only the strings that start with “aa” or “bb”

Solution

The language generated by this example will include all strings that start with “aa” or “bb”

L = { aa, bb, aaa, bbb, aaab, aaba,……..}

The following NFA automaton machine accepts all strings that start with “bab”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) =q3
  • δ (q0, b) = q1
  • δ (q1, a) =ϕ
  • δ (q1, b) = q2
  • δ (q2, a) = q2
  • δ (q2, b) = q2
  • δ (q3, a) = q4
  • δ (q3, b) =ϕ
  • δ (q4, a) = q4
  • δ (q4, b) = q4
• q0 refers to the initial state
• {q2,q4} refers to the set of final states

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

States	a	b
q0	q3	q1
q1	ϕ	q2
q2	q2	q2
q3	q4	ϕ
q4	q4	q4

NFA Example: 2.4

Design an NFA over the alphabet Σ = {a, b} that accepts only the strings that start with “bbb” or “baab”

Solution

The language generated by this example will include all strings that start with “bbb” or “baab”

L = {bbb, baab, bbba, baaba, bbbab, bbbba, baabab, baabba, ……..}

The following NFA automaton machine accepts all strings that start with “bbb” or “baab”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) =ϕ
  • δ (q0, b) = q1
  • δ (q1, a) =q2
  • δ (q1, b) = q3
  • δ (q2, a) = q3
  • δ (q2, b) = ϕ
  • δ (q3, a) =ϕ 
  • δ (q3, b) =q4
  • δ (q4, a) = q4
  • δ (q4, b) = q4
• q0 refers to the initial state
• {q4} refers to the set of final states

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

q0	ϕ	q1
q1	q2	q3
q2	q3	ϕ
q3	ϕ	q4
q4	q4	q4
States	a	b

 

Category 3: End with

The third category will explain an NFA that accepts all strings that end with some fixed alphabet symbols

NFA Example: 3.1

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the strings that end with “bab”.

Solution

The language generated by this example will include all strings that end with “bab”.

L = { bab, abab, bbab, abbab, babab……..}

The following NFA automaton machine accepts all strings that end with “bab”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, a) = q0
  • δ (q0, b) = q0,q1
  • δ (q1, a) = q2
  • δ (q1, b) =ϕ
  • δ (q2, a) =ϕ
  • δ (q2, b) = q3
  • δ (q3, a) = ϕ
  • δ (q3, b) = ϕ

• q0 refers to the initial state
• {q3} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0	q0,q1
q1	q2	ϕ
q2	ϕ	q3
q3	ϕ	ϕ

NFA Example: 3.2

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 machine accepts all strings where the second-to-last bit is “1”.

5 Tuples of the above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {0,1} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, 0) = q0
  • δ (q0, 1) = q0,q1
  • δ (q1, 0) = q2
  • δ (q1, 1) = q2
  • δ (q2, 0) = ϕ
  • δ (q2, 1) = ϕ
• q0 refers to the initial state
• {q2} refers to the set of final states

Transition Table for the above NFA is

States	0	1
q0	q0	q0,q1
q1	q2	q2
q2	ϕ	ϕ

NFA Example: 3.3

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……..}

Required NFA is given below

5 Tuples of the above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {0,1} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, 0) = q0
  • δ (q0, 1) = q0,q1
  • δ (q1, 0) = q2
  • δ (q1, 1) = q2
  • δ (q2, 0) = q3
  • δ (q2, 1) = q3
  • δ (q3, 0) = ϕ
  • δ (q3, 1) = ϕ
• q0 refers to the initial state
• {q3} refers to the set of final states

The state transition table for the above NFA is given below

States	0	1
q0	q0	q0,q1
q1	q2	q2
q2	q3	q3
q3	ϕ	ϕ

NFA Example: 3.4

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 machine accepts all strings that end with “01”.

 

5 Tuples of above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {0,1} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, 0) = q0,q1
  • δ (q0, 1) = q0
  • δ (q1, 0) = ϕ
  • δ (q1, 1) = q2
  • δ (q2, 0) = ϕ
  • δ (q2, 1) = ϕ
• q0 refers to the initial state
• {q2} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0,q1	q0
q1	ϕ	q2
q2	ϕ	ϕ

NFA Example: 3.5

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the strings that end with “aa” or “bb”.

Solution

The language generated by this example will include all strings that end with “aa” or “bb”

L = { aa, bb, aaa, abb, aaaa, aabb, …………… }

The following NFA machine accepts all strings formed by zero or more repetitions of “aa” or “aab”, ending with “b”

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q0,q1
  • δ (q0, b) = q0,q3
  • δ (q1, a) = q2
  • δ (q1, b) = ϕ
  • δ (q2, a) = ϕ
  • δ (q2, b) = ϕ
  • δ (q3, a) = ϕ
  • δ (q3, b) = q4
  • δ (q4, a) = ϕ
  • δ (q4, b) = ϕ

• q0 refers to the initial state
• {q2,q4} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0q1	q0q3
q1	q2	ϕ
q2	ϕ	ϕ
q3	ϕ	q4
q4	ϕ	ϕ

NFA Example: 3.6

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the strings that end with “bbb” or “bab”.

Solution

The language generated by this example will include all strings that end with “aa” or “bb”.

L = { bbb, bab, abbb, abab, bbbb, bbab, abbbb …………… }

The following NFA machine accepts all strings formed by zero or more repetitions of “aa” or “aab”, ending with “b”.

 

• {q0, q1, q2, q3, q4, q5} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q0
  • δ (q0, b) = q0,q1
  • δ (q1, a) = q4
  • δ (q1, b) = q2
  • δ (q2, a) = ϕ
  • δ (q2, b) = q3
  • δ (q3, a) = ϕ
  • δ (q3, b) = ϕ
  • δ (q4, a) = ϕ
  • δ (q4, b) = q5
  • δ (q5, a) = ϕ
  • δ (q5, b) = ϕ

• q0 refers to the initial state
• {q2,q4} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0	q0q1
q1	q4	q2
q2	ϕ	q3
q3	ϕ	ϕ
q4	ϕ	q5
q5	ϕ	ϕ

 

Category 4: Start and End with

This category will explain an NFA that accepts all strings that start and end with some fixed alphabet symbols.

NFA Example: 4.1

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 start with 1 and end with 0.

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

Required NFA is given below

5 Tuples of the above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {0,1} refers to the set of input alphabets
• δ refers to the transition function 
  • δ (q0, 0) = ϕ
  • δ (q0, 1) = q1
  • δ (q1, 0) = q2
  • δ (q1, 1) = q1
  • δ (q2, 0) = q2
  • δ (q2, 1) = q1

• q0 refers to the initial state
• {q2} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	ϕ	q1
q1	q2	q1
q2	q2	q1

NFA Example: 4.2

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the strings that start with zero or more repetitions of aa and end with b.

Solution

The language generated by this example will include all strings that start with zero or more repetitions of “aa”, ending with “b”.

L = { b, aab, aaaab, aaaaaab, aaaaaaab,……….. }

The following NFA automaton machine accepts all strings that start with zero or more repetitions of “aa”, ending with “b”.

5 Tuples of the above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q1
  • δ (q0, b) = q2
  • δ (q1, a) = q0 
  • δ (q1, b) = ϕ
  • δ (q2, a) =ϕ
  • δ (q2, b) = ϕ

• q0 refers to the initial state
• {q2} refers to the set of final states

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

States	a	b
q0	q1	q2
q1	q0	ϕ
q2	ϕ	ϕ

 

NFA Example: 4.3

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the strings that start with zero or more repetitions of “aab” and end with “b”.

Solution

The language generated by this example will include all strings that start with zero or more repetitions of “aab”, ending with “b”.

L = { b, aabb, aabaabb, aabaabaabb, aabaabaaabb }

The following NFA machine accepts all strings that start with zero or more repetitions of “aab”, ending with “b”.

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q1
  • δ (q0, b) = q3
  • δ (q1, a) = q2
  • δ (q1, b) = ϕ
  • δ (q2, a) =ϕ
  • δ (q2, b) = q0
  • δ (q3, a) = ϕ
  • δ (q3, b) = ϕ

• q0 refers to the initial state
• {q3} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q1	q3
q1	q2	ϕ
q2	ϕ	q0
q3	ϕ	ϕ

NFA Example: 4.4

Please design an NFA with input alphabet ∑ = {a, b} that accepts all the  strings that start with zero or more repetitions of “aa” or “aab”, and end with “b”.

Solution

The language generated by this example will include all strings that start with zero or more repetitions of “aa” or “aab”, and end with “b”.

L = { b, aab, aabb, aaaab, aabaabb, aabaabb, …………… }

The following NFA automaton machine accepts all strings that start with zero or more repetitions of “aa” or “aab”, and end with “b”.

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q1,q2
  • δ (q0, b) = q4
  • δ (q1, a) = q0
  • δ (q1, b) = ϕ
  • δ (q2, a) =q3
  • δ (q2, b) = ϕ
  • δ (q3, a) = ϕ
  • δ (q3, b) = q0
  • δ (q4, a) = ϕ
  • δ (q4, b) = ϕ

• q0 refers to the initial state
• {q4} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q1q2	q4
q1	q0	ϕ
q2	q3	ϕ
q3	ϕ	q0
q4	ϕ	ϕ

Category 05: Must Contain

This category will explain an NFA that accepts all strings that must contain a particular string as a substring.

NFA Example: 5.1

Construct an NFA with ∑ = {a, b} in which each string must contain zero or more repetitions of  “ab’ or “aab”.

Solution

The language generated by this example will include all strings that contain zero or more repetitions of  “ab’ or “aab”.

L = { ε, ab, aab, abaab, aabab, abaabaabab, …………… }

The following NFA machine accepts all strings that contain zero or more repetitions of  “ab” or “aab”.

5 Tuples of the above NFA are given below,

• {q0, q1, q2} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q1
  • δ (q0, b) = ϕ
  • δ (q1, a) = q2
  • δ (q1, b) = q0
  • δ (q2, a) =ϕ
  • δ (q2, b) = q0

• q0 refers to the initial state
• {q0} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q1	ϕ
q1	q2	q0
q2	ϕ	q0

NFA Example: 5.2

Construct an NFA with ∑ = {a, b} in which each string must contain “ba” or “bb” as a substring

Solution

The language generated by this example will include all strings that contain “ba” or “bb” as a substring.

L = { bb, ba, abb, aba, bbb, bba, abbb, abba, abbbab, aaabbbbbbaaaa,  …………… }

The following NFA automaton machine accepts all strings that contain “ba” or “bb” as a substring.

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q0
  • δ (q0, b) = q0q1
  • δ (q1, a) = q3
  • δ (q1, b) = q2
  • δ (q2, a) = q2
  • δ (q2, b) = q2
  • δ (q3, a) = q3
  • δ (q3, b) = q3

• q0 refers to the initial state
• {q2,q3} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0	q0q1
q1	q3	q2
q2	q2	q2
q3	q3	q3

NFA Example: 5.3

Construct an NFA with ∑ = {a, b} in which each string must contain bbb or baab as a substring

Solution

The language generated by this example will include all strings that contain bbb or baab as a substring.

L = { bbb, baab, abbb, abaab, abbba, abaaba, bbaabb, bbbbb,  …………… }

The following NFA machine accepts all strings that contain “bbb” or “baab” as a substring. 

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q0
  • δ (q0, b) = q0q1
  • δ (q1, a) = q2
  • δ (q1, b) = q3
  • δ (q2, a) = q3
  • δ (q2, b) = ϕ
  • δ (q3, a) = ϕ
  • δ (q3, b) = q4
  • δ (q4, a) = q4
  • δ (q4, b) = q4

• q0 refers to the initial state
• {q4} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0	q0q1
q1	q2	q3
q2	q3	ϕ
q3	ϕ	q4
q4	ϕ	ϕ

NFA Example: 5.4

Construct an NFA with ∑ = {a, b} in which each string must contain “bbaa” or “baba” as a substring

Solution

The language generated by this example will include all strings that contain “bbaa” or “baba” as a substring.

L = { bbaa , baba , abbaa , ababa , bbbaa, bbaba, abbaab , ababab,  …………… }

The above NFA automaton machine accepts all strings that contain “bbb” or “baab” as a substring. 

5 Tuples of the above NFA are given below,

• {q0, q1, q2, q3, q4, q5, q6, q7} refers to the set of states
• {a,b} refers to the set of input alphabets
• δ refers to the transition function

• • δ (q0, a) = q0
  • δ (q0, b) = q0q1
  • δ (q1, a) = q5
  • δ (q1, b) = q2
  • δ (q2, a) = q3
  • δ (q2, b) = ϕ
  • δ (q3, a) = q4
  • δ (q3, b) = ϕ
  • δ (q4, a) = q4
  • δ (q4, b) = q4
  • δ (q5, a) = ϕ
  • δ (q5, b) = q6
  • δ (q6, a) = q7
  • δ (q6, b) = ϕ
  • δ (q7, a) = q7
  • δ (q7, b) = q7

• q0 refers to the initial state
• {q4,q7} refers to the set of final states

The state transition table for the above NFA is

States	a	b
q0	q0	q0q1
q1	q5	q2
q2	q3	ϕ
q3	q4	ϕ
q4	q4	q4
q5	ϕ	q6
q6	q7	ϕ
q7	q7	q7

NFA Example: 5.5

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

5 Tuples of the above NFA are given below

• {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, 0) = q0
  • δ (q0, 1) = q0, q1
  • δ (q1, 0) = fi
  • δ (q1, 1) = q2
  • δ (q2, 0) = q3
  • δ (q2, 1) = ϕ
  • δ (q3, 0) = q3
  • δ (q3, 1) = q3

• q0 refers to the initial state
• {q3} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0	q0,q2
q1	ϕ	q2
q2	q3	ϕ
q3	q3	q3

 NFA Example: 5.6

Design an NFA with ∑ = {0, 1} such that every string must contain the substring “1101”.

Solution

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

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

NFA for the above language is

5 Tuples of the above NFA are given below,

• {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, 0) = q0
  • δ (q0, 1) = q0, q1
  • δ (q1, 0) = ϕ
  • δ (q1, 1) = q2
  • δ (q2, 0) = q3
  • δ (q2, 1) = ϕ
  • δ (q3, 0) = ϕ
  • δ (q3, 1) = q4
  • δ (q4, 0) = q4
  • δ (q4, 1) = q4

• q0 refers to the initial state
• {q4} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0	q0,q1
q1	ϕ	q2
q2	q3	ϕ
q3	ϕ	q4
q4	q4	q4

 

NFA Example: 5.7

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 that must contain “11” followed by “00”.

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

NFA for the above language is

 5 Tuples of the above NFA are given below,

• {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, 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 

• q0 refers to the initial state
• {q4} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0	q0,q1
q1	ϕ	q2
q2	q3	ϕ
q3	q4	ϕ
q4	q4	q4

NFA Example: 5.8

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 that must contain either “01” or “10”.

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

NFA for the above language is

 5 Tuples of the above NFA are given below,

• {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, 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 

• q0 refers to the initial state
• {q2,q4} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0,q1	q0,q3
q1	ϕ	q2
q2	q2	q2
q3	q4	ϕ
q4	q4	q4

NFA Example: 5.9

Construct an NFA with ∑ = {0, 1} which contains the  language L = {0^m1ⁿ | m ≥0 and n≥1 }.

Solution

The language-generated strings will be like

• When m=0  and n=1, the string will be 1 because 0⁰1¹=1.
• When m=1 and n=2, then the string will be 1 because 0¹1²=011.
• When m=2 and n=3, then the string will be 1 because 0²1³=00111.
• By choosing a random value, i.e., When m=3, n=2, the string will be 1 because 0³1²=00011.And so on.

So, the string must have at least one1, but can have zero or more 0s before that.

5 Tuples of the above NFA are given below,

• {q0, q1} refers to the set of states
• {0,1} refers to the set of input alphabets
• δ refers to the transition function
  • δ (q0, 0) = q0
  • δ (q0, 1) = q1
  • δ (q1, 0) = ϕ
  • δ (q1, 1) = q1

• q0 refers to the initial state
• {q1} refers to the set of final states

The state transition table for the above NFA is

States	0	1
q0	q0	q1
q1	ϕ	q2

NFA Example: 5.10

Construct an NFA with ∑ = {0, 1} which contains the language L = {(01)ⁿ | n≥1 }.

Solution

The language-generated strings will be like as

• When n=1, the string will be 01 because (01)¹=01.
• When n=2, the string will be 0101 because (01)²=0101.
• By choosing a random value, i.e., n=5, then  (01)⁵=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: 5.11

Construct an NFA with ∑ = {0, 1} which contains the language L = {(01)ⁿ | n≥0 }.

Solution

The language-generated strings will be like as

• When n=1, the string will be 01 because (01)⁰ = null.
• If n=1, the string will be 01 because (01)¹=01.
• By choosing a random value, i.e., n=4, the result will be  (01)⁴=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: 5.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