NFA in TOC
NFA in TOC stand for Non-Deterministic Finite Automata. NFA is also known as NDFA its means Non-Deterministic Finite Automata. NFA is a type of Finite Automata (FA) that is used to regular languages which can be finite or infinite set of strings. It is a key concept or most important topic in Theory of Automata (TOC). A Non-Deterministic Finite Automata (NFA) is a defined by 5-tuples (Q,Σ,δ,q0,F). These five tuples are as follow.
NFA = (Q,Σ,δ,q0,F)
- Q is a finite and non-empty set of states.
Example: Q = {q0, q1, q2}
- Σ is a finite non-empty set of finite input alphabet.
Example: Σ = {a, b} for alphabet strings.
Example: Σ = {0, 1} for binary strings.
- δ is a transition function that tells us how NFA moves from one state to one or more states based on input.
Example: δ (q0, 1)
| Formula: δ: Q × Σ → 2Q |
- q0 is the initial state and the initial state are always one.
Example: q0 is the initial state where the NFA start.
| Note: q0 ∈ Q |
- F is the set of finite final state.
Example: F = {q2}
| Note: F ⊆ Q |
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}
At State q0
- For Input a: Transition goes to q0.
- For Input b: Transition goes to q0.
NFA Example: 1.2
Draw a NFA which accept only input string “a,b or c”
Over input alphabets Σ = {a,b}
At State q0
- For Input a: Transition goes to q1.
- For Input b: Transition goes to q2.
- For Input c: Transition goes to q2.
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}
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.
NFA Example: 2.2
Draw a NFA which accept only input string “b”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.3
Draw a NFA which accept only input string “aa”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.4
Draw a NFA which accept only input string “bba”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.5
Draw a NFA which accept only input string “abab”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.6
Draw a NFA which accept only input string “bbb or baab”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.7
Draw a NFA which accept only input string “aaa or abba”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.8
Draw a NFA which accept only input string “bbbb or baabb”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.9
Draw a NFA which accept only input string “bbbaa or baabaa”
Over input alphabets Σ = {a,b}
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.
NFA Example: 2.10
Draw a NFA which accept only input string “bbbaa or baabbba”
Over input alphabets Σ = {a,b}
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.
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}
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.
NFA Example: 3.2
Draw a NFA that accept all strings but the second last bit is “a”
Over input alphabets Σ = {a,b}
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.
NFA Example: 3.3
Draw a NFA that accept all strings but the third last bit is “b”
Over input alphabets Σ = {a,b}
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.
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}
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.
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}
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.
NFA Example: 3.6
Draw a NFA that accept all strings which end with “aaa or bbb”
Over input alphabets Σ = {a,b}
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.
NFA Example: 3.7
Draw a NFA that accept all strings which end with “aaaa or abaaa”
Over input alphabets Σ = {a,b}
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.
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}
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.
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}
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.
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}
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.