Department of

Computer Science

Automata and Complexity Theory

 Introduction
Why This Course?
• What problems can computers solve?
• What problems cannot be solved?
• What problems are solvable but too slow?
• Why some algorithms scale and others don’t
Real-World Applications
• Spell checkers & regex engines
• Compilers and syntax checking
• Network protocols
• Cryptography & security

Automata and ComplexityTheory By: Metadel A 2

 Introduction of Finite Automata
• Finite automata are abstract machines used to recognize patterns in input sequences.

• forming the basis for understanding regular languages in computer science

• They consist of states, transitions, and input symbols, processing each symbol step-by-step
• If the machine ends in an accepting state after processing the input, it is accepted;
otherwise, it is rejected

• Finite automata come in deterministic (DFA) and non-deterministic (NFA), both of

which can recognize the same set of regular languages. They are widely used in text
processing, compilers, and network protocols.

Automata and ComplexityTheory By: Metadel A 3

Con..
Features of Finite Automata
• Input: Set of symbols or characters provided to the machine.

• Output: Accept or reject based on the input pattern.

• States of Automata: The conditions or configurations of the machine.

• State Relation: The transitions between states.

• Output Relation: Based on the final state, the output decision is made.

Automata and ComplexityTheory By: Metadel A 4

Con..
Features of Finite Automata
• Input: Set of symbols or characters provided to the machine.

• Output: Accept or reject based on the input pattern.

• States of Automata: The conditions or configurations of the machine.

• State Relation: The transitions between states.

• Output Relation: Based on the final state, the output decision is made.

Automata and ComplexityTheory By: Metadel A 5

Con..
The following basic terms are play a great role in automata theory such as Alphabet, string,
language,
Alphabets:
An alphabet is a finite non empty set of symbols, which used to represent the input of a machine.
Alphabets are typically thought of as represented by letters, characters, digits, signs, punctuation,
etc. Conventionally we use the symbol ∑ for an alphabet. Common alphabets include:

• ∑ = {0, 1}: The binary alphabets.

• ∑ = {a, b, c, ……, z}: The set of all lower-case letters.

Automata and ComplexityTheory By: Metadel A 6

Con..
Strings:
• A string is a finite ordered sequence of symbols chosen form some set of alphabet or ∑. For
example, ‘aababbbbaa’is a valid string from the alphabet ∑ = {a, b}, similarly
‘001111000101’is a valid string form the alphabet ∑ = {0, 1}.

Empty string:
• Every alphabet ∑ has a special string called empty string which means the string with zero
• occurrences of symbols. This string represented by ε.
• It is the string that may be chosen from any alphabet whatsoever.

Automata and ComplexityTheory By: Metadel A 7

 Con..
Length of a string:
• The finite occurrence of input symbols form ∑ present the length of a string. If s
denotes the string over alphabet
• ∑ then length of a string is represented by |S|. For instance, ‘001110’ is a string from
the alphabets ∑= {0, 1} has
• length 6. Similarly if ∑ = {a, b} and S = ‘aabbabbba’ then |S| = 9.

• Note: The length of empty string |ε| = 0.

Automata and ComplexityTheory By: Metadel A 8

 Con..
Power of an alphabet:
• If ∑ is an alphabet, we can express the set of all strings of a certain length form that
alphabet by using an exponential notation. We denoted it ∑n to be the set of strings of length n,
each of whose symbols is in given input alphabet ∑.

• For example: ∑0 = {ε} regardless of what alphabet ∑ is, i.e. ε is the only string whose length is
zero.

• If ∑ = {0, 1}, then ∑1 = {0, 1}, similarly ∑2 = {00, 01, 10, 11} or

• ∑3= {000, 001, 010, 011, 100, 101, 110, 111} and so on.

Automata and ComplexityTheory By: Metadel A 9

 Con..
Power of an alphabet:
• If ∑ is an alphabet, we can express the set of all strings of a certain length form that
alphabet by using an exponential notation. We denoted it ∑n to be the set of strings of length n,
each of whose symbols is in given input alphabet ∑.

• For example: ∑0 = {ε} regardless of what alphabet ∑ is, i.e. ε is the only string whose length is
zero.

• If ∑ = {0, 1}, then ∑1 = {0, 1}, similarly ∑2 = {00, 01, 10, 11} or

• ∑3= {000, 001, 010, 011, 100, 101, 110, 111} and so on.

Automata and ComplexityTheory By: Metadel A 10

 Con..
Language
• A set of strings formed using the symbols of an alphabet. A language can be finite or
infinite.

• Notation: Often denoted by Example

• If Σ = {a, b}L = {ε, a, aa, bba}

• a finite language = {w ∈ Σ* | w ends with "a"}

• →all strings over {a, b} that end in "a"

Automata and ComplexityTheory By: Metadel A 11

 Con..
1. Identify the Alphabet
Given the following sets, identify which ones are valid alphabets:

a) {0, 1}

b) {a, b, c}

c) {}

d) {apple, banana}

format: Mark "Valid" or "Invalid" and explain why.

Automata and ComplexityTheory By: Metadel A 12
 Con..
Given:
2. Σ = {a, b}Which of the following are valid strings over Σ?
a) bba
b) abc
c) ε
d) baba!
e) baa3.
3. Describe a Language Task:
Let Σ = {0, 1}

Define a language L such that: L contains all strings that end with ‘1’ Write 5 example

strings that belong to L. and Write 2 strings that do not belong to L.

Automata and ComplexityTheory By: Metadel A 13

 Con..
Given:
2. Σ = {a, b}Which of the following are valid strings over Σ?
a) bba
b) abc
c) ε
d) baba!
e) baa3.
3. Describe a Language Task:
Let Σ = {0, 1}

Define a language L such that: L contains all strings that end with ‘1’ Write 5 example

strings that belong to L. and Write 2 strings that do not belong to L.

Automata and ComplexityTheory By: Metadel A 14

 Finite Automata
Formal Definition of Finite Automata

A finite automaton can be defined as a tuple:

{ Q, Σ, q, F, δ }, where:
There are two types of finite automata:
• Q: Finite set of states
1. Deterministic Finite Automata (DFA)
• Σ: Set of input symbols
2. Non-Deterministic Finite Automata (NFA
• q: Initial state

• F: Set of final states

• δ: Transition function

Automata and ComplexityTheory By: Metadel A 15

 Types of FiniteAutomata
1. Deterministic Finite Automata (DFA)
A DFA is represented as {Q, Σ, q, F, δ}. In DFA, for each input symbol, the machine transitions
to one and only one state. DFA does not allow any null transitions, meaning every state must
have a transition defined for every input symbol.
DFA consists of 5 tuples {Q, Σ, q, F, δ}.

Q : set of all states.

Σ : set of input symbols. ( Symbols which machine takes as input )

q : Initial state. ( Starting state of a machine )

F : set of final state.

δ : Transition Function, defined as δ : Q X Σ --> Q.

Automata and ComplexityTheory By: Metadel A 16
Con… Transition Table
State diagram

Note: A trap state (also called a dead state or sink state) is a non- accepting state from
which, once entered, the automaton can never reach an accepting state again. It
absorbs all further inputs and keeps the automaton stuck there.
Formally:

In a DFA, every state must have exactly one transition for each symbol in the alphabet.

To ensure this, a trap state is often added so that all "undefined" transitions go into it.

Automata and ComplexityTheory By: Metadel A 17

Example 1:
Construct a DFA that accepts all strings ending with 'a'.
Given: Σ = {a, b},
Q = {q0, q1}, F = {q1}

Transition Diagram

In this example, if the string ends in 'a', the machine reaches state q1, which is an accepting state.

Automata and ComplexityTheory By: Metadel A 18

Example 2: Construct a DFAthat accepts all the strings over the

alphabets ∑ ={0,1} that start with “0”.

Solution:

The given question provides the following

Language ofAccepted Strings = {0, 01, 00, 010, 011, 000, 001,…, }

Some Rejected Strings = {ε, 1, 11, 101, 1001, 110}

Let’s draw the DFA, which accepts all the strings starting with “0”.

Automata and ComplexityTheory By: Metadel A 19

Example 2: Construct a DFAthat accepts all the strings over the

alphabets ∑ ={0,1} that start with “0”.

Solution:

The given question provides the following

Language ofAccepted Strings = {0, 01, 00, 010, 011, 000, 001,…, }

Some Rejected Strings = {ε, 1, 11, 101, 1001, 110}

Let’s draw the DFA, which accepts all the strings starting with “0”.

Automata and ComplexityTheory By: Metadel A 20

 DFADescription

States = {q0, q1, q∅ }

InputAlphabet = {0, 1}

Initial State = q0

Final States = {q1}

Dead State = q∅ (trap state)

Transition Function δ is defined as: δ(q0, 0) = q1

δ(q0, 1) = q∅

δ(q1, 0) = q1 δ(q1, 1) = q1 δ(q∅

, 0) = q∅ δ(q∅ , 1) = q∅

Automata and ComplexityTheory By: Metadel A 21

 Exercise
1. Construct DFA, which accept all the string over alphabets ∑ {0,1} that end with “10”.
2. Construct a DFAwith sigma ∑ = {0, 1}, accepts those string which starts with one and ends with 0.
3. Design a DFAwith sigma ∑ = {0, 1} for the language accepting strings containing at least two ‘0’.
4. Construct DFA, which accept all the string over alphabets ∑= {0,1} where the length of each string is exactly 2.
5. Construct DFA, which accept all the string over alphabets ∑= {0,1} where the length of each string is ≤ 2
6. Construct DFA, which accept all the string over alphabets ∑= {0,1} where the length of each string is ≥ 2.

Automata and ComplexityTheory By: Metadel A 22

2. NFA (Nondeterministic Finite Automaton):
• NFA(Nondeterministic Finite Automaton): Unlike DFA
➢ For a state and an input symbol, there may be zero, one, or many possible next states
• (including ε-moves).
➢ NFA: May have ε-transitions (state changes without reading input).

➢ NFA: For a given input string, there may be multiple paths; if at least one path leads to
a final state, the string is accepted.

Automata and ComplexityTheory By: Metadel A 23

 1. Construct an NFAwith ∑ = {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 NFAis given below
5 Tuples of the above NFAare 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

Automata and ComplexityTheory By: Metadel A 24

2. Construct an NFAwith ∑ = {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……..}

Automata and ComplexityTheory By: Metadel A 25

2. Construct an NFAwith ∑ = {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……..}

Automata and ComplexityTheory By: Metadel A 26

3. An NFA that accepts all binary strings that end with 101.

Solution
Description (5-tuple)
• Alphabet: Σ = {0,1}

• States: Q = {A, B, C, D}
• Start state: A
• Accepting state: F = {D}
• Transition function δ given below
Automata and ComplexityTheory By: Metadel A 27
 State At 0 At 1
A A A,B
B C ∅
C ∅ D
D ∅ ∅

Automata and ComplexityTheory By: Metadel A 28

 Epsilon NFA (∈-NFA)
Epsilon NFA (∈-NFA) is similar to the NFA but with a little difference in that, it has an epsilon (∈) transition that NFA
doesn’t have.
• A Transition that does not consume any input symbol is called an ε-transitions. Epsilon NFA (∈-NFA) is also
called a null NFA or an NFA lambda.
• ∈-NFAstate diagrams usually label Epsilon with the Greek letter “∈”. It is also called lambda.
• ∈-transitions give a convenient way of designing the machine systems.
Due to ε-transitions, the first string of language may be empty.
Formal Definition of Epsilon-NFA
The formal definition of ∈-NFA is represented through 5-tuple (Q, ∑, δ, q0, F) where,
•Q is a finite set of all states (q0, q1, q2, …, qn) where n is a finite number.
•∑ Is a finite set of symbols called the alphabet. i.e. {0, 1}.
•δ : Q x (∑ U ∈) → 2Q is a total function called as transition function.
•q0 is the initial state from which any input is processed (q0 ∈ Q).
•F is a set of final states, where F will be a subset ( ⊆ ) of Q
Automata and ComplexityTheory By: Metadel A 29
 Why we need epsilon NFA?
•Simplifies construction from regular expressions
•Makes combining automata easier
•Provides flexible design while recognizing the same languages

Automata and ComplexityTheory By: Metadel A 30

Automata and ComplexityTheory By: Metadel A 31
 Epsilon NFA (∈-NFA) Department of
Computer Science

The transition table for the above NFA and epsilon NFA diagram is given below

Automata and Complexity Theory By: Metadel A • 32

 Department of
Computer Science
Epsilon NFA (∈-NFA)
∈ – NFA: Example 02
Draw an epsilon NFA that accepts the string “a or b”.

The transition table for the above epsilon NFA diagram is given below

Automata
2/20/2026 and Complexity Theory By: Metadel A • 33 33
 Department of
Computer Science
Difference Between DFAand NFA
• There is not much difference between DFA and NFA because they both accept
regular languages. The basic difference between the DFA and NFA is that their
transition function are different.
• In DFA, the transition function (δ) takes two arguments (state, symbol) as input and returns a
single state as output.
• In NFA, the transition function (δ) takes two arguments (state, symbol) as input and can
return multiple states.

• DFA: One input symbol can go to exactly one next state

• NFA: One input symbol can go to a single, multiple, or no states.
Automata and Complexity Theory By: Metadel A 34
 Department of
Computer Science

Similarity
➢ Four tuples out of five are similar for both DFAand NFAexcept transition.

➢ Both DFA and NFA accept the regular languages

➢ NFAand DFAcontains finite number of states

➢ NFAand DFA both can hold more than one final states
➢ Power of DFA and NFA is same because both types of automata are equivalent in terms of the languages they
can ognize. This equivalence theorem is known as the “subset construction”. It states that every NFA has an
equivalent DFAthat recognizes the same language, and vice versa.

➢ All DFA’s are NFA’s but not vice versa.

Automata and Complexity Theory By: Metadel A 35

 Department of
Computer Science
Conversion from NFA to DFA
There are four basic steps for the conversion of NFA to DFA.
Step 01: Draw an NFA graph (Mostly Given).
Step 02: Draw the NFA transition table from the NFA diagram.
Step 03: Convert the NFA transition table to the DFA transition Table.

• Step 3.1: Select the first two rows of the NFA table to begin constructing the DFA. These two rows will
now serve as the initial rows of the DFA.
• Step 3.2: If any state appears in the input column of the DFA but is not found in the States column of the
DFA, it is considered a New State. Simply copy this new state and puts in the states column and add its all
possible transitions in the DFA table. The transitions for the New State in the DFA table will follow the
NFA transition table. Repeat this procedure until no new states are found in the input columns.
• Step 3.3: If “x” was the final state in the NFA Transition Table, then all those states will be the final states in the DFA Transition Table where “x” exists.

Step 04: Convert the DFA table to the DFA Diagram.

2/19/2026 36
 Department of
Computer Science
Conversion from NFA to DFA
Example 01: NFA to DFA Conversion
Problem: Draw an NFA of all binary strings in which the 2nd last bit is 1 and convert this NFA to its
corresponding DFA

Step 01: Draw NFA Graph.

The following is the NFA graph that has to be converted into a DFA.

Automata and Complexity Theory By: Metadel A • 37

 Department of
Computer Science

Step 02: Draw the NFA transition Table.

The NFA transition table of the above NFA is given below

Automata and Complexity Theory

2/20/2026 By: Metadel A • 38
38
 Department of
Computer Science
Step 03: Conversion of NFA to DFA Transition Table
Let’s start the conversion of the NFA transition table to the DFA transition Table.

Step 3.1: Select the first two rows of the NFA transition table, which will become the first two rows of the DFA
transition table given below.

In the above DFA Table

State Column Contains: “q0”
Input columns contain: “q0”, “q0q1”

2/20/2026 and Complexity Theory

Automata By: Metadel A • 39 39
 Department of
Computer Science
Step 3.2: State “q0q1” is a new state because it is present in the input columns of the DFA but does not exist in the state
column. Put “q0q1” in the state column along with its transitions.

Transition calculations for state “q0q1” For

input “0”

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)

= {q0} ∪ {q2}

= [q0q2]

For input “1”

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)

= {q0q1} ∪ {q2}

= {q0q1q2}
Automata and Complexity Theory By: Metadel A • 40
 Department of
Computer Science
The transition of state “q0q1” against input “0” is “q0q2”, and the transition against input “1” is “q0q1q2”. Hence, the
updated DFA table is given below.

In the above DFA Table

State Column Contains: “q0”, “q0q1”

Input columns contain: “q0”, “q0q1”, “q0q2”, “q0q1q2”
Repeat Step 3.2: “q0q2” and “q0q1q2” are new states because it is present in the input columns of the DFA
but do not exist in the state column. Put “q0q2” and “q0q1q2” in the state column along with their transitions.

Automata and Complexity Theory By: Metadel A • 41

 Department of
Computer Science
Transition calculations for state “q0q2”

For input “0”

δ([q0q2], 0) = δ(q0, 0) ∪ δ(q2, 0)

= {q0}

= [q0]

For input “1”

δ([q0q2], 1) = δ(q0, 1) ∪ δ(q2, 1)

= {q0q1}

= {q0q1}

= [q0q1]
Automata and Complexity Theory By: Metadel A • 42
 Department of
Computer Science

Transition calculations for state “q0q1q2”

For input “0”

δ([q0q1q2], 0) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q2, 0)

= {q0} ∪ {} ∪ {q2}

= [q0q2]

For input “1”

δ([q0q1q2], 1) = δ(q0, 1) ∪ δ(q1, 1) ∪ δ(q2, 1)

= {q0} ∪ {q1} ∪ {q2}

= [q0q1q2]

Automata and Complexity Theory By: Metadel A • 43

 Department of
Computer Science
Hence, the updated DFA table is given below, where
• The Transition of “q0q1q2” against input “0” is “q0q2”, and the transition against input “1” is “q0q1q2”.

• The Transition of “q0q2” against input “0” is “q0”, and the transition against input “1” is “q0q1”.

DFA Transition Table Continues.. In the

above DFA Table

State Column Contains: “q0”, “q0q1”, “q0q2”, “q0q1q2”

Input columns contain: “q0”, “q0q1”, “q0q2”, “q0q1q2”
At this stage, no new state remains. The DFA table is one step away to complete.

Step 3.3: State “q2” was the final state in the NFA Table. That’s why all those states will be the final states where “q2” is present in the
DFA state column. Simply mark with “*” to represent the final state.

Here is the complete DFA transition table with its final states
 Department of
Computer Science

• Step 4: Now draw the DFA according to the DFA transition table
• The DFA transition table contains four states (q0, q0q1, q0q2, q0q1q2) in its state column. Thus, the desired
• DFA machine graph will contain these states, and transitions will be made according to the DFA transition
• table.

Automata and Complexity Theory By: Metadel A 45

 Department of
Computer Science
• The DFA minimization is the process of reducing states in a deterministic finite automaton (DFA) and
maintaining its language recognition abilities.

• That means, DFA minimization is aimed at finding a DFA with the least number of states that can
recognize the same language as the original DFA.

Some of the benefits of minimizing DFA:

• Reduced memory usage:

• Improved computational efficiency:

• Enhanced understanding

• Simplified hardware implementation:

Automata and Complexity Theory By: Metadel A 46

 Department of
Computer Science

Rules for DFAMinimization

• Step 1: Remove Unreachable States From the start state, mark all states that can be
reached on some input symbol. Any state not marked = unreachable, remove them
(they don’t affect the language).

• Step 2: Initial Partition

Partition states into two sets:

1. Final states (F)

2. Non-final states (Q – F)
Automata and Complexity Theory By: Metadel A 47
 Department of
Computer Science
Step 3: Refinement of Partitions Check each block (subset) of the partition:

For each input symbol, see which block the transition goes to. If two states in the same block go to different blocks, then they

are not equivalent, so split the block. Keep repeating until no further split is possible.

Step 4: Form Equivalence Classes Each block in the final partition = one state in the minimized DFA.

If two states are in the same block, they are equivalent and merged.

Step 5: Construct the Minimized DFA

States = final partition blocks.

Start state = block containing the original start.

Final states = blocks containing at least one original final.

Automata and Complexity Theory By: Metadel A 48

 Department of
Computer Science
Construct a minimum state automata equivalent to given automata?

Automata and Complexity Theory By: Metadel A 49

 Department of
Computer Science

Step 01: Remove steps which are unreachable from initial states.
Step 02: Split final states and non final states.
A0 = {q4} F
A1 = {q0,q1,q2,q3} NF
π0 = {q4}, {q0,q1,q2,q3}
A0 cannot be partition further
In A1,

• q0 is 1 equivalent to q2 for input a, but not equivalent to q1 and q3.

• q1 is 1 equivalent to q3 for input a and b, but not to q0 and q2.

Automata and Complexity Theory By: Metadel A 50
 Department of
Computer Science

Minimization of DFA
So, A1 can be partitioned as,
• B0 = {q0, q2}
• B1 = {q1, q3}
• π1 = {q4}, {q0,q2}, {q1,q3}
Now, B0 and B1 can not be partitioned further.
• π2 = {q4}, {q0,q2}, {q1,q3}
• π2 = π1
In minimized DFA, we have three states,
• {q4},
• {q0,q2},
• {q1,q3}

Automata and Complexity Theory By: Metadel A 51

 Department of
Computer Science

Automata and Complexity Theory By: Metadel A 52

 Department of
Computer Science

Course Name 53 53