Introduction to Automata

Finite Automata

Moore and Mealy Machine

Regular Expressions

Derivation in Automata

Context Free Language

Turing Machine

MIX

Difference b/w NFA and DFA

There are many differences between NFA and DFA. Both are important types of Finite Automata (FA) in Theory of Computation (TOC). Before discussing their differences, make sure you have already read or covered the topics of NFA in TOC and DFA in TOC. Now, let’s discuss the main difference between NFA and DFA.

NON-Deterministic Finite Automata (NFA)

i) NFA or NDFA stand for NON-Deterministic Finite Automata.

ii) For each input symbol there can be multiple transition.

iii) NFA is not complete. It means that NFA does not need to be complete.

iv) ε NFA move occurs.

v) In NFA we use this formula δ: Q × Σ → 2^Q

^{vi) It is easy to design.}

^{vii) All NFA are not DFA.}

NON-Deterministic Finite Automata (NFA) Construction Examples

There are many categories and different examples of Non-Deterministic Finite Automata (NFA). But in this NFA construction examples we discuss four categories and we discuss only two examples of every categories.

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}

This example generates the following strings.

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

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 Example: 1.2

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

Over input alphabets Σ = {a, b}

This example generates the following strings.

L = {ε, a, b, c, ab, ac, bc, abc, …………}

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.

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 all string that start with “a”

Over input alphabets Σ = {a, b}

This example generates the following strings.

L = {ε, a, ab, aba, aab, abb, …………….}

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 Example: 2.2

Draw a NFA which accept all strings that start with “b”

Over input alphabets Σ = {a, b}

This example generates the following strings.

L = {ε, b, bab, baa, baba, ……………….}

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.

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}

This example generates the following strings.

L = {ε, a, b, ab, bab, aab, aaab, ……………….}

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 Example: 3.2

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

Over input alphabets Σ = {a, b}

This example generates the following strings.

L = {ε, ab, baa, aab, aaab, abab, ……………….}

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.

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}

This example generates the following strings.

L = {ε, 01, 001, 011, 0101, ……………………}

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

This example generates the following strings.

L = {ε, 110, 1100, 1110, 11110, 11100, ………………….}

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.

Deterministic Finite Automata (DFA)

i) DFA stand for Deterministic Finite Automata.

ii) For each input symbol there can be only one transition.

iii) DFA is always complete.

iv) ε DFA move not occur.

v) In DFA we use this formula δ: Q × Σ → Q.

^{vi) It is difficult to design.}

^{vii) All DFA are NFA.}

Deterministic Finite Automata (DFA) Construction Examples

There are many categories and different examples of Deterministic Finite Automata (DFA). But in this DFA construction examples we discuss four categories and we discuss only one example of every categories.