Introduction to Finite
Automata
Automata Theory
What is Automata Theory?
• Automata theory is the study
of abstract machines.
• Abstract machines are
theoretical representations of
real-world machines (such as
a computer) but without the
unnecessary details
associated with a particular
instance of that machine.
• By removing these details, it is
easier to analyze the operation
of the machine being studied.
Introduction to Finite Automata
• For example, assume that the
machine is a simple light bulb
connected to a power source
via a single toggle switch.
If the lever of the toggle switch
is pushed or flipped, the light
bulb turns on. If the lever is
pushed again, it turns off.
The operation of this machine
can be described by the
following graph:
push lever of
switch
Light Light
Bulb is Bulb is
Off On
push lever of
switch
Introduction to Finite Automata
Each node in the graph
represents the “state” of the
light bulb. The bulb can only
be in one of two states, off or
on.
The edges of the graph show
when the machine moves
between the two states.
Assume initially that the bulb is
turned off (it is in the off state).
If the lever of the toggle switch
is pushed, it moves from the
off state to the on state.
Now the bulb is in the on state.
If the lever is pushed again,
the light bulb moves from the
on state to the off state.
Introduction to Finite Automata
This is now an abstract model
of the light bulb machine. With
this model, the operation of the
machine can be analyzed
without having the actual
physical machine present.
For example, it is easy to see
from the graph that if the lever
of the switch is pushed 6 times
in succession, the light bulb
will end up in its current state.
This abstract model of the light
bulb machine is called an
automaton and the graph that
represents it is called its state
diagram.
Introduction to Finite Automata
• Automata theory therefore
uses abstract or mathematical
models to represent machines
and computers.
Like the light bulb machine, a
computer can also be in one
state or another depending
upon the contents of its main
memory, processor registers,
etc.
When input data arrives or an
event occurs (like the clicking
of the mouse or the typing of a
character on the keyboard),
the computer moves from one
state to another.
Introduction to Finite Automata
The following are just some of
the things that can be done
once models have been
established:
1. Determine the capabilities
and limitations of each
machine.
2. Determine which machine
is more powerful.
3. Determine what each
machine can compute.
Introduction to Finite Automata
• An automaton is not only used
to represent machines
(hardware) but they can also
be used to represent software
(such as operating systems
and compilers).
• The different types of
automata that will be
encountered in this course are
finite automata (deterministic
and nondeterministic), push-
down automata, and Turing
machines.
Introduction to Finite Automata
Finite Automata
Deterministic Finite Automata
• A finite automaton is a
machine that has a limited
(finite) number of states.
• Because of this limitation,
these are normally used to
model computers with a limited
amount of memory or
programs that process only a
small amount of data.
• Discussions here will focus on
hypothetical machines whose
only task is to determine
whether an input string or a
series of input symbols is
acceptable or not based on
some predefined rule.
Introduction to Finite Automata
• Given the following state
diagram of a finite automaton
M1. 0 1
0
q0 q1 qq2
0
1
q3 0, 1
Take note of the following
facts about M1:
1. It has four states labeled
q0, q1, q2, and q3.
2. It has an initial state
which is q0.
3. It has one final or accept
state which is q2.
4. It has edges connecting
the states. These edges
represent transitions.
Introduction to Finite Automata
• Consider the following process
flow for M1:
1. The machine is currently at
the initial state, q0.
2. The system receives a 0
as its input. So the system
moves from q0 to q1.
3. The system receives
another 0 as its second
input. So the system stays
at state q1.
4. The system receives a 1
as its third input. So the
system moves from state
q1 to q2.
Introduction to Finite Automata
5. The system receives a 0
as its fourth input. So the
system moves from state
q2 to q1.
6. The system receives a 1
as its fifth and last input.
So the system moves from
state q1 to q2.
Since the system is now at
state q2 and it is a final state,
then it is said that the system
accepts the input string 00101.
To generalize, M1 accepts any
string that starts with a 0,
followed by any number of 0s
and 1s, as long as the last
input is a 1.
Introduction to Finite Automata
Formal Definition of a Deterministic
Finite Automaton (DFA)
• A deterministic finite
automaton (DFA) is composed
of
1. A finite set of states
designated as Q.
2. A finite set of symbols
(alphabet) used as inputs
designated as Σ.
3. A transition function
designated as δ.
4. A start state designated
as q0.
5. A set of final states or
accept states designated
as F.
Introduction to Finite Automata
• The transition function is a
table that specifies when state
transitions (movement from
one state to another) are
carried out.
For the DFA M1, its transition
function δ is
0 1
q0 q1 q3
q1 q1 q2
q2 q1 q2
q3 q3 q3
For each input symbol, the
automaton can move to only
one state from any given
current state. This is what is
meant by the term
“deterministic.”
Introduction to Finite Automata
• Using the formal definition of a
DFA, M1 can now be described
as a 5-tuple:
M1 = {Q, Σ, δ, q0, F}
where:
1. Q = {q0, q1, q2, q3}
2. Σ = {0, 1}
3. δ:
0 1
q0 q1 q3
q1 q1 q2
q2 q1 q2
q3 q3 q3
4. Start State = q0.
5. F = {q2}
Introduction to Finite Automata
• More examples of DFAs:
1. DFA M2
0, 1
q0 q1
0, 1
2. DFA M3
0 0
q0 q1
Introduction to Finite Automata
3. DFA M4
1 1 0, 1
0 0
q0 q1 q2
4. DFA M5
0, 1
0, 1 0, 1
q0 q1 q2
Introduction to Finite Automata
5. DFA M6
0 1
q1 q2
q0
q3 q4
1 0
6. DFA M7
0 1
0, 1
1
q0 q1 q2
Introduction to Finite Automata
F0093
• For DFA M2:
1. Q = {q0, q1}
2. Σ = {0, 1}
3. δ:
0 1
q0 q1 q1
q1 q0 q0
4. Start State = q0.
5. F = {q0}
M2 accepts all strings
(including the empty string ε)
whose length is even.
Introduction to Finite Automata
F0093
• For DFA M3:
1. Q = {q0, q1}
2. Σ = {0, 1}
3. δ:
0 1
q0 q0 q1
q1 q1 q0
4. Start State = q0.
5. F = {q0}
M3 accepts all strings
(including the empty string ε)
that contain an even number
of 1’s.
Introduction to Finite Automata
F0093
• For DFA M4:
1. Q = {q0, q1, q2}
2. Σ = {0, 1}
3. δ:
0 1
q0 q1 q0
q1 q2 q1
q2 q2 q2
4. Start State = q0.
5. F = {q1}
M4 accepts all strings that only
has exactly one 0.
Introduction to Finite Automata
F0093
• For DFA M5:
1. Q = {q0, q1, q2}
2. Σ = {0, 1}
3. δ:
0 1
q0 q1 q1
q1 q2 q2
q2 q0 q0
4. Start State = q0.
5. F = {q0}
M5 accepts all strings
(including the empty string ε)
whose length is divisible by 3.
Introduction to Finite Automata
F0093
• For DFA M6:
1. Q = {q0, q1, q2, q3, q4)
2. Σ = {0, 1}
3. δ:
0 1
q0 q1 q3
q1 q1 q2
q2 q1 q2
q3 q4 q3
q4 q4 q3
4. Start State = q0.
5. F = {q1, q3}
• M6 accepts all strings that start
and end with the same
symbol.
Introduction to Finite Automata
F0093
• For DFA M7:
1. Q = {q0, q1, q2}
2. Σ = {0, 1}
3. δ:
0 1
q0 q0 q1
q1 q2 q1
q2 q1 q1
4. Start State = q0.
5. F = {q1}
M7 accepts all strings that
have at least one 1 and the
last 1 is always followed by an
even number of consecutive
0s.
Introduction to Finite Automata
F0093
• The set of strings that an
automaton accepts is called
the language of the
automaton.
For example, the language of
DFA M2 is the set of all strings
over the alphabet Σ = {0, 1}
whose length is even.
If L is the language recognized
by a DFA M, then it is
designated as L(M).
So for the language of M2, it
can be mathematically
described as:
L(M2) = {w | the length of w
is even}
Introduction to Finite Automata
F0093
• A language that is recognized
by a DFA is called a regular
language.
For example, the language
composed of all strings over
the alphabet Σ = {0, 1} that
starts and ends with the same
symbol is a regular language
because there is a DFA
(specifically, M6) that
recognizes it.
Therefore, L(M6) is a regular
language.
Introduction to Finite Automata
