AUTOMATA AND

COMPILER THEORIES
AND FORMAL
LANGUAGES

Prepared by: Maxil S. Urocay MSCS ongoing

“Prayer to the Holy Spirit by St. Augustine”

Breathe in me, O Holy Spirit,

That my thoughts may all be holy.

Act in me, O Holy Spirit,

That my work, too may be holy.

Draw my heart, O Holy Spirit.

That I love but what is holy.

Strengthen me, O Holy Spirit,

To defend all that is holy.

Prepared by: Maxil S. Urocay MSCS ongoing
 DETERMINISTIC
FINITE AUTOMATA
(DFA)
Prepared by: Maxil S. Urocay MSCS ongoing
WHAT IS AN AUTOMATON?
An automaton is a
theoretical machine that
processes input and produces
output based on transitions
between states.
It operates by
transitioning between
different states based on the
input it receives, following a
set of predefined rules or
functions.
Prepared by: Maxil S. Urocay MSCS ongoing
 TYPES OF AUTOMATA

1. Finite Automata (FA)

2. Pushdown Automata (PDA)
3. Turing Machine (TM)
4. Linear Bounded Automaton (LBA)
5. Quantum Automata
6. Cellular Automata

Prepared by: Maxil S. Urocay MSCS ongoing

WHY STUDY AUTOMATA?

Automata theory is the foundation

of many critical areas in computer
science, especially when it comes
to:

1. Programming Languages
2. Compilers
3. Algorithms

Prepared by: Maxil S. Urocay MSCS ongoing

WHY STUDY AUTOMATA?
Importance in Programming
Languages:

-Automata define the syntax and

structure of languages
-Helps in understanding language
parsing
-Automata are used to recognize
valid syntax patterns
Prepared by: Maxil S. Urocay MSCS ongoing
WHY STUDY AUTOMATA?
Importance in Compilers:

-Compilers convert source code to

machine code
-Automata analyze source code and
recognize patterns
-Crucial for generating appropriate
machine code from syntax

Prepared by: Maxil S. Urocay MSCS ongoing

WHY STUDY AUTOMATA?
Importance in Algorithms:

-Automata theory aids in algorithm

design and analysis
-Key for pattern matching, regular
expressions, and text processing
-Provides efficient methods to solve
computational problems

Prepared by: Maxil S. Urocay MSCS ongoing

 FINITE AUTOMATON (FA

is a mathematical model
used to represent and
recognize patterns in formal
languages.
It consists of a finite set
of states, transitions, and an
input alphabet.

Prepared by: Maxil S. Urocay MSCS ongoing

 COMPONENTS OF FINITE
AUTOMATA

States:
A finite set of states
(including an initial and
accepting state).

Prepared by: Maxil S. Urocay MSCS ongoing

 COMPONENTS OF FINITE
AUTOMATA

Alphabet:
A set of symbols used
as input.

Prepared by: Maxil S. Urocay MSCS ongoing

 COMPONENTS OF FINITE
AUTOMATA

Transitions:
Rules for moving from
one state to another based
on input symbols.

Prepared by: Maxil S. Urocay MSCS ongoing

 COMPONENTS OF FINITE
AUTOMATA

Initial State:
The state where the
automaton starts.

Prepared by: Maxil S. Urocay MSCS ongoing

 COMPONENTS OF FINITE
AUTOMATA

Accepting States:
States that determine
if the input string is
accepted or rejected.

Prepared by: Maxil S. Urocay MSCS ongoing

TYPES OF FINITE AUTOMATA

1. Deterministic Finite
Automaton (DFA)
2. Nondeterministic
Finite Automaton
(NFA)

Prepared by: Maxil S. Urocay MSCS ongoing

 WHAT IS A DETERMINISTIC FINITE
AUTOMATA (DFA)?

DFA
is a type of
automaton that processes
a string of symbols and
decides whether it is
accepted or rejected
based on a deterministic
set of rules.
Prepared by: Maxil S. Urocay MSCS ongoing
 DETERMINISTIC FINITE AUTOMATA
(DFA)?
DFA FEATURES:

-The machine has a finite set of

states.
-At each step, there’s only one
possible move from any state for
a given input symbol
(deterministic).
-The machine processes one input
symbol at a [Link] by: Maxil S. Urocay MSCS ongoing
DETERMINISTIC FINITE AUTOMATA
(DFA)?
The machine has a finite set of
states:

-DFAs only have a limited

number of states to work with.
Each state represents a specific
condition or situation the
automaton is in at any point in
the process.
Prepared by: Maxil S. Urocay MSCS ongoing
DETERMINISTIC FINITE AUTOMATA
(DFA)?
At each step, there’s only one
possible move from any state for
a given input symbol
(deterministic):

-This means that for every

state and input symbol, the DFA
has exactly one defined
transition. There’s no choice or
ambiguity, this is what makes it
Prepared by: Maxil S. Urocay MSCS ongoing
DETERMINISTIC FINITE AUTOMATA
(DFA)?
The machine processes one input
symbol at a time:

-The DFA reads input symbols

one by one and moves from one
state to the next based on the
predefined transitions. The
process is sequential and doesn’t
skip over input symbols.
Prepared by: Maxil S. Urocay MSCS ongoing
VISUAL REPRESENTATION OF DFA

Prepared by: Maxil S. Urocay MSCS ongoing

 VISUAL REPRESENTATION OF DFA

This DFA accepts

any string that
contains at least
one '1’.

Prepared by: Maxil S. Urocay MSCS ongoing

 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

5-Tuple Formal Definition of

DFA
- A DFA is formally defined
by a 5-tuple: (Q,Σ,δ,q0​,F)

Prepared by: Maxil S. Urocay MSCS ongoing

 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

TUPLE
a tuple is an ordered
collection of elements.

Prepared by: Maxil S. Urocay MSCS ongoing

 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

Q: A Finite Set of States

Q represents the set of all

possible states the automaton
can be in at any given time.

Prepared by: Maxil S. Urocay MSCS ongoing

 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

Σ: A Finite Set of Symbols

(Alphabet)

Σ is the alphabet, the set

of symbols the DFA can read.
These symbols are the inputs
that the DFA processes one at
a time.
Prepared by: Maxil S. Urocay MSCS ongoing
 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

δ: Transition Function

δ (delta) is the transition

function that defines how the
automaton moves from one
state to another based on the
current input symbol.
Prepared by: Maxil S. Urocay MSCS ongoing
 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

δ: Transition Function

Formally: δ:Q×Σ→Q, which

means the transition function
takes the current state and an
input symbol and returns the
next state.
Prepared by: Maxil S. Urocay MSCS ongoing
 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

q₀: Initial State

q₀ is the starting state of

the DFA. When the automaton
begins processing a string, it
starts in this state.

Prepared by: Maxil S. Urocay MSCS ongoing

 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

q₀: Initial State

starting state 𝑞0​ in the state

The incoming arrow to the

diagram signifies the initial

state of the DFA. It indicates
where the automaton begins
processing the input string.
Prepared by: Maxil S. Urocay MSCS ongoing
 KEY COMPONENTS OF A DFA
(DETERMINISTIC FINITE AUTOMATA)

F: Set of Accepting (Final)

States

F is the set of accepting or

final states. If, after processing
the entire input string, the DFA
ends in one of these states,
the string is accepted.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Step-by-Step Process:
1. Start at the initial state (q₀).
2. Read the first symbol of the input string.
3. Follow the transition from the current state based
on the input symbol.
4. Repeat the process until the entire string is read.
5. Acceptance Criteria: The DFA accepts the string if
it ends in one of the final states (F). If not, it rejects
the string.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Start at the Initial State (q₀)

The DFA begins its

operation at the initial state,
denoted as q0​.

This is the starting point where

the automaton has not yet
processed any input symbols.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Read the First Symbol of the

Input String

The DFA reads the first

symbol from the input string
(for example, 'a' or 'b’).
The automaton processes this
symbol one by one, meaning it
handles input symbol by
symbol, from left to right.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Follow the Transition Based on

the Input Symbol

After reading an input

symbol, the DFA follows the
transition function δ, which
tells the automaton where to
move based on the current
state and the symbol read.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Repeat the Process Until the

Entire String Is Read

The process continues for

each input symbol in the
string. The DFA keeps moving
between states, following the
transition function, until all the
symbols have been read.
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Acceptance Criteria:
1. The DFA Accepts the String
if It Ends in One of the Final
States (F)

After processing the entire

string, the DFA checks whether
it has ended in an accepting
state (one of the states in F).
Prepared by: Maxil S. Urocay MSCS ongoing
 HOW DOES A DFA PROCESS INPUT?

Acceptance Criteria:
2. If the DFA Does Not End in
an Accepting State, It Rejects
the String
If the DFA ends in a non-
accepting state, the string is
rejected.

Prepared by: Maxil S. Urocay MSCS ongoing

WHAT IS DFA MINIMIZATION?

DFA Minimization
is the process of reducing
the number of states in a DFA
while preserving the same
language.

Prepared by: Maxil S. Urocay MSCS ongoing

WHAT IS DFA MINIMIZATION?

Why It's Important:

Minimizing a DFA can
make it more efficient (in
terms of memory and
computation).

Prepared by: Maxil S. Urocay MSCS ongoing

 WHY MINIMIZE?

Benefits:

Smaller Size: A minimized DFA

has fewer states, making it
easier to store and faster to
operate on.

Prepared by: Maxil S. Urocay MSCS ongoing

 WHY MINIMIZE?

Benefits:

Improved Efficiency: With

fewer states to process, the
automaton can perform
operations faster.

Prepared by: Maxil S. Urocay MSCS ongoing

 WHY MINIMIZE?

Benefits:

Simplicity: A simpler DFA is

easier to understand and
debug, which helps when
implementing or analyzing the
automaton.

Prepared by: Maxil S. Urocay MSCS ongoing

WHAT IS A REGULAR LANGUAGE?

Regular Language
can be described and
recognized by a DFA, which
processes strings symbol by
symbol and determines
whether they belong to the
language based on the DFA’s
state transitions.

Prepared by: Maxil S. Urocay MSCS ongoing

WHAT IS A REGULAR LANGUAGE?

L={strings over {a,b} that end

with ’ab’}

Example strings in this

language: "ab", "aabb", "bab",
"babab".

Prepared by: Maxil S. Urocay MSCS ongoing

 DETERMINISTIC FINITE AUTOMATA

Create a DFA that

accepts all strings
starting with the prefix
"ab".

Prepared by: Maxil S. Urocay MSCS ongoing

 WHAT IS A TRAP STATE?

Trap State:

is a non-accepting
state from which no
accepting state can be
reached.

Prepared by: Maxil S. Urocay MSCS ongoing

 WHY USE TRAP STATES?

Helps Simplify DFA

Construction:

Trap states are used

to reject strings that do
not meet certain
conditions.

Prepared by: Maxil S. Urocay MSCS ongoing

HOW TO REPRESENT A DFA?

Table Representation of a
DFA:

Instead of using
transition diagrams, a
DFA can also be
represented using a
transition table.
Prepared by: Maxil S. Urocay MSCS ongoing
STRUCTURE OF THE TRANSITION
TABLE

The table consists of:

Rows: Each row

represents a state in the
DFA.

Prepared by: Maxil S. Urocay MSCS ongoing

STRUCTURE OF THE TRANSITION
TABLE

The table consists of:

Columns: Each column

represents an input
symbol from the
alphabet (e.g., 'a' and
'b').

Prepared by: Maxil S. Urocay MSCS ongoing

STRUCTURE OF THE TRANSITION
TABLE

The table consists of:

Entries: The entry in the

table shows the next
state based on the
current state and input
symbol.

Prepared by: Maxil S. Urocay MSCS ongoing

 DETERMINISTIC FINITE AUTOMATA

DFA is a theoretical
model that processes
strings symbol by
symbol and decides if
they belong to a specific
language.

DFAs are deterministic:

There is no ambiguity in
transitions Prepared by: Maxil S. Urocay MSCS ongoing
 DETERMINISTIC FINITE AUTOMATA

Efficiency:

DFAs are efficient in

both time and space
because they have a
finite set of states and
perform a single scan of
the input string.

Prepared by: Maxil S. Urocay MSCS ongoing

REAL-WORLD APPLICATION
DFAs are foundational to
several computational
fields, such as:

Text Processing:
Used in applications
like search engines to
find specific patterns in
text.

Prepared by: Maxil S. Urocay MSCS ongoing

REAL-WORLD APPLICATION
DFAs are foundational to
several computational
fields, such as:

Pattern Recognition:
Applied in fields
such as speech
recognition, optical
character recognition
(OCR), and more.
Prepared by: Maxil S. Urocay MSCS ongoing
REAL-WORLD APPLICATION
DFAs are foundational to
several computational
fields, such as:

Compiling:
DFAs are integral to
lexical analysis, where
the source code is
analyzed for tokens (e.g.,
keywords, operators,
identifiers).
Prepared by: Maxil S. Urocay MSCS ongoing
REAL-WORLD APPLICATION
Lexical Analysis in
Compilers:
A DFA can be used
to recognize the
keywords and identifiers
in source code,
transforming it into a
format that the compiler
can process.

Prepared by: Maxil S. Urocay MSCS ongoing

 DETERMINISTIC FINITE AUTOMATA

Create a DFA that

accepts any string of 0's
and 1's ending with
"101"

Prepared by: Maxil S. Urocay MSCS ongoing

 DETERMINISTIC FINITE AUTOMATA

Create a DFA that

accepts a string of a's
and b's ending with
"bba"

Prepared by: Maxil S. Urocay MSCS ongoing

A Deterministic Finite
Automaton is a simple yet
powerful tool for modeling
computation, where every
decision is based on a clear,
predefined set of rules.
Prepared by: Maxil S. Urocay MSCS ongoing
THANK YOU

Prepared by: Maxil S. Urocay MSCS ongoing