Tech Taleem Logo

NFA Examples

There are many NFA Examples are as given. But you make sure that you have already read or covered the topic of Non-Deterministic Finite Automata (NFA) in TOC. So, different examples or categories of NFA are as follow.

Non-Deterministic Finite Automata Construction Examples

There are different examples of Non-Deterministic Finite Automata (NDFA or NFA). So, we can divided into a different categories. However, different categories of the following Non-Deterministic Finite Automata (NDFA or NFA) are as given.

Category 1: Accept all Strings

In category 1 we explain NFA that accept all strings over the alphabet symbols which include every possible combination.

NFA Example: 1.1

Draw a NFA which accept only input string “a or b”

Over input alphabets Σ = {a, b}

NFA Example 1.1

At State q0

  • For Input a: Transition goes to q0.
  • For Input b: Transition goes to q0.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q0

So, NFA Transition Table are also given.

NFA Transition Table 1.1

NFA Example: 1.2

Draw a NFA which accept only input string “a, b or c”

Over input alphabets Σ = {a, b}

NFA Example 1.2

At State q0

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q2.
  • For Input c: Transition goes to q2.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0}
  • Input Alphabet = {a, b, c}
  • Initial State = q0
  • Final State = q0

So, NFA Transition Table are also given.

NFA Transition Table 1.2

Category 2: Start With

In category 2 we explain NFA that accept all strings that start with some fixed alphabet.

NFA Example: 2.1

Draw a NFA which accept only input string “a”

Over input alphabets Σ = {a, b}

NFA Example 2.1

At State q0

  • For Input a: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q1.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q1

So, NFA Transition Table are also given.

NFA Transition Table 2.1

NFA Example: 2.2

Draw a NFA which accept only input string “b”

Over input alphabets Σ = {a, b}

NFA Example 2.2

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q1.
  • For Input b: Transition goes to q1.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q1

So, NFA Transition Table are also given.

NFA Transition Table 2.2

NFA Example: 2.3

Draw a NFA which accept only input string “aa”

Over input alphabets Σ = {a, b}

NFA Example 2.3

At State q0

  • For Input a: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q2

So, NFA Transition Table are also given.

NFA Transition Table 2.3

NFA Example: 2.4

Draw a NFA which accept only input string “bba”

Over input alphabets Σ = {a, b}

NFA Example 2.4

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.

At State q3

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q3

So, NFA Transition Table are also given.

NFA Transition Table 2.4

NFA Example: 2.5

Draw a NFA which accept only input string “abab”

Over input alphabets Σ = {a, b}

NFA Example 2.5

At State q0

  • For Input a: Transition goes to q1.

At State q1

  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input b: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q4.
  • For Input b: Transition goes to q4.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3,q4}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q4

So, NFA Transition Table are also given.

NFA Transition Table 2.5

NFA Example: 2.6

Draw a NFA which accept only input string “bbb or baab”

Over input alphabets Σ = {a, b}

NFA Example 2.6

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input b: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q4.
  • For Input b: Transition goes to q4.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q2,q3,q4}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q4

So, NFA Transition Table are also given.

NFA Transition Table 2.6

NFA Example: 2.7

Draw a NFA which accept only input string “aaa or abba”

Over input alphabets Σ = {a, b}

NFA Example 2.7

At State q0

  • For Input a: Transition goes to q1.

At State q1

  • For Input b: Transition goes to q2.
  • For Input a: Transition goes to q3.

At State q2

  • For Input b: Transition goes to q3.

At State q3

  • For Input a: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q4.
  • For Input b: Transition goes to q4.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3,q4}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q4

So, NFA Transition Table are also given.

NFA Transition Table 2.7

NFA Example: 2.8

Draw a NFA which accept only input string “bbbb or baabb”

Over input alphabets Σ = {a, b}

NFA Example 2.8

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input b: Transition goes to q4.

At State q4

  • For Input b: Transition goes to q4.

At State q5

  • For Input a: Transition goes to q5.
  • For Input b: Transition goes to q5.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3,q4,q5}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q5

So, NFA Transition Table are also given.

NFA Transition Table 2.8

NFA Example: 2.9

Draw a NFA which accept only input string “bbbaa or baabaa”

Over input alphabets Σ = {a, b}

NFA Example 2.9

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input b: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q5.

At State q5

  • For Input a: Transition goes to q6.

At State q6

  • For Input a: Transition goes to q6.
  • For Input b: Transition goes to q6.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q2,q3,q4,q5,q6}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q1

So, NFA Transition Table are also given.

NFA Transition Table 2.9

NFA Example: 2.10

Draw a NFA which accept only input string “bbbaa or baabbba”

Over input alphabets Σ = {a, b}

NFA Example 2.10

At State q0

  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q3.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input b: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q6.
  • For Input b: Transition goes to q5.

At State q5

  • For Input b: Transition goes to q6.

At State q6

  • For Input a: Transition goes to q7.
  • For Input b: Transition goes to q5.

At State q7

  • For Input a: Transition goes to q7.
  • For Input b: Transition goes to q7.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q2,q3,q4,q5,q6,q7}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q7

So, NFA Transition Table are also given.

NFA Transition Table 2.10

Category 3: End With

In category 3 we explain NFA that accept all strings that end with some fixed alphabet.

NFA Example: 3.1

Draw a NFA that accept all strings but end with “b”

Over input alphabets Σ = {a, b}

NFA Example 3.1

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q0.

At State q1

  • For Input a: Transition goes to q2.

At State q2

  • For Input b: Transition goes to q3.

At State q3

  • No transition moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q3

So, NFA Transition Table are also given.

NFA Transition Table 3.1

NFA Example: 3.2

Draw a NFA that accept all strings but the second last bit is “a”

Over input alphabets Σ = {a, b}

NFA Example 3.2

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q0.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

At State q3

  • No transitions moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q2

So, NFA Transition Table are also given.

NFA Transition Table 3.2

NFA Example: 3.3

Draw a NFA that accept all strings but the third last bit is “b”

Over input alphabets Σ = {a, b}

NFA Example 3.3

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.

At State q2

  • For Input b: Transition goes to q3.

At State q3

  • No transitions moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q3

So, NFA Transition Table are also given.

NFA Transition Table 3.3

NFA Example: 3.4

Draw a NFA that accept all strings where the third symbol from the right is “a”

Over input alphabets Σ = {a, b}

NFA Example 3.4

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q0.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

At State q3

  • No transitions moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q3

So, NFA Transition Table are also given.

NFA Transition Table 3.4

NFA Example: 3.5

Draw a NFA that accept all strings where the third symbol from the left is “a”

Over input alphabets Σ = {a, b}

NFA Example 3.5

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q1.

At State q1

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q2.
  • For Input b: Transition goes to q2.

At State q3

  • No transitions moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2,q3}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q3

So, NFA Transition Table are also given.

NFA Transition Table 3.5

NFA Example: 3.6

Draw a NFA that accept all strings which end with “aaa or bbb”

Over input alphabets Σ = {a, b}

NFA Example 3.6

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q4.

At State q1

  • For Input a: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • No transitions moves to q3.

At State q4

  • For Input b: Transition goes to q5.

At State q5

  • For Input b: Transition goes to q6.

At State q6

  • No transitions moves to q6.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q2,q3,q4,q5,q6}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q6

So, NFA Transition Table are also given.

NFA Transition Table 3.6

NFA Example: 3.7

Draw a NFA that accept all strings which end with “aaaa or abaaa”

Over input alphabets Σ = {a, b}

NFA Example 3.7

At State q0

  • For Input a: Transition goes to q0 and q1.
  • For Input b: Transition goes to q0.

At State q1

  • For Input a: Transition goes to q3.
  • For Input b: Transition goes to q2.

At State q2

  • For Input a: Transition goes to q3.

At State q3

  • For Input a: Transition goes to q4.

At State q4

  • For Input a: Transition goes to q5.

At State q5

  • No transitions moves to q3.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q2,q3,q4,q5}
  • Input Alphabet = {a, b}
  • Initial State = q0
  • Final State = q5

So, NFA Transition Table are also given.

NFA Transition Table 3.7

Category 4: Start and End with

In category 4 we explain NFA that accept all strings that start and end with some fixed alphabet.

NFA Example: 4.1

Draw a NFA that accept all strings that start with “0”  and end with “1”

Over input alphabets Σ = {0,1}

NFA Example 4.1

At State q0

  • For Input 0: Transition goes to q1.

At State q1

  • For Input 0: Transition goes to q1.
  • For Input 1: Transition goes to q2.

At State q2

  • For Input 1: Transition goes to q2.
  • For Input 0: Transition goes to q1.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1q2}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2

So, NFA Transition Table are also given.

NFA Transition Table 4.1

NFA Example: 4.2

Draw a NFA that accept all strings that start with “1 or more repetitions of 11” and end with “0”

Over input alphabets Σ = {0,1}

NFA Example 4.2

At State q0

  • For Input 1: Transition goes to q0 and q1.

At State q1

  • For Input 0: Transition goes to q2.

At State q2

  • No transitions moves to q2.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2

So, NFA Transition Table are also given.

NFA Transition Table 4.2

NFA Example: 4.3

Draw a NFA that accept all strings that start with “00” and end with “1 or more repetitions of 1”

Over input alphabets Σ = {0,1}

NFA Example 4.3

At State q0

  • For Input 0: Transition goes to q0 and q1.

At State q1

  • For Input 1: Transition goes to q2.

At State q2

  • For Input 1: Transition goes to q2.

Explanation:

Hence, the more explanation of the above NFA are as given.

  • States = {q0,q1,q2}
  • Input Alphabet = {0,1}
  • Initial State = q0
  • Final State = q2

So, NFA Transition Table are also given.

NFA Transition Table 4.3

"Your Support, Our Priority"

"We Make It Easy"