COMPILER DESIGN

COURSE CODE:21CS3204R

TOPIC: INTRODUCTION TO COMPILERS

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.

2
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.

3
Formal Definition of Finite Automata
A finite automaton can be defined as a tuple:
{ Q, Σ, q, F, δ },
where:
• Q: Finite set of states
• Σ: Set of input symbols
• q: Initial state
• F: Set of final states
• δ: Transition function
4
Types of Finite Automata
There are two types of finite automata:
• Deterministic Fintie Automata (DFA)
• Non-Deterministic Finite Automata (NFA)

5
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.

6
Example:
Construct a DFA that accepts all strings ending with ‘a’.
Given: State\Symbol a b
q0 q1 q0
Σ = {a, b}, q1 q1 q0
if the string ends in ‘a’, the machine
Q = {q0, q1},
reaches state q1, which is an
F = {q1} accepting state.

7
2) Non-Deterministic Finite Automata (NFA)
NFA is similar to DFA but includes the following features:
• It can transition to multiple states for the same input.
• It allows null (ϵ) moves, where the machine can change states without
consuming any input.

8
Example:
Construct an NFA that accepts strings ending in ‘a’.
Given: State Transition Table for above Automaton,

Σ = {a, b},
State \Symbol a b
Q = {q0, q1},
q0 {q0,q1} q0
F = {q1}
q1 φ φ

9
REGULAR EXPRESSIONS TO FINITE AUTOMATA

• As the regular expressions can be constructed from Finite Automata using the State
Elimination Method, the reverse method, state decomposition method can be used to
construct Finite Automata from the given regular expressions.
• Note: This method will construct NFA (with or without ε-transitions, depending on the
expression) for the given regular expression.

10
State Decomposition Method
Theorem: Every language defined by a regular expression is also defined by
a Finite Automata.
Proof: Let’s assume L = L(R) for a regular expression R. We prove that L =
L(M) for some ε-NFA M with:
1) Exactly one accepting state.
2) No incoming edges at the initial state.
3) No outgoing edges at the accepting state.
The proof is done by structural induction on R by following the steps below:

11
Step 1: Create a starting state, say q1, and a final state, say q2. Label the
transition q1 to q2 as the given regular expression, R, as in Fig 1. But, if R is
(Q)*, Kleene’s closure of another regular expression Q, then create a single
initial state, which will also be the final state, as in Fig 2.

fig 1 fig 2

12
 Step 2: Repeat the following rules (state decomposition method) by
considering the least precedency regular expression operator first until no
operator is left in the expression. Precedence of operators in regular
expressions is defined as Union < Concatenation < Kleene’s Closure.
Union operator (+) can be eliminated by introducing parallel edges between
the two states as follows.

Fig 3: Removal of Union Operator

13
• The concatenation operator (‘.’ or no operator at all) can be eliminated
by introducing a new state between the states as follows.

Fig 4: Removal of Concatenation Operator

14
Kleene’s Closure (*) can be eliminated by introducing self-loops on states based on
the following conditions:
1. If there is only one outgoing edge at the left-most state, i.e., A in transition A -> B,
then introduce self-loop on state A and label edge A to B as an ε-transition, as shown in
Fig 5.

Fig 5
15
2. Else if there is only one incoming edge at the right-most state, i.e., B in
transition A -> B, then introduce self-loop on state B and label edge A to B as
an ε-transition, as shown in Fig 6.

Fig 6
16
3. Else introduce a new state between two states having self-loop
labeled as the expression. The new state will have ε-transitions with the
previous states as follows, as shown in Fig 7.

Fig 7
17
Subset method is used to obtain FA from the given RE.
Step 1 − Construct a Transition diagram for a given RE by using Non-deterministic finite
automata (NFA) with ε moves.
Step 2 − Convert NFA with ε to NFA without ε.
Step 3 − Convert the NFA to the equivalent Deterministic Finite Automata (DFA).

18
EXAMPLE:

Some basic RE are as follows −

Case 1 − For a regular expression ‘a’, we can construct FA as shown
below −

Case 2 − For a regular expression ‘ab’ we can construct FA, as given

below −

19
Case 3 − For a regular expression (a+b) we can construct FA as follows −

Case 4 − For a RE (a+b)*, We can construct FA as mentioned below −

20
Thank you

21