Scribd
Upload
59 views13 pages

DFA Minimization Steps and Examples

This document is a lesson plan on minimizing deterministic finite automata (DFA). It begins with objectives to define minimization, understand the procedure, and complete examples. The procedure is described as identifying unreachable states, deriving state values, constructing a new transition table, and diagram. An example is provided showing the full steps: identifying an unreachable state, deriving equivalence classes, constructing the new transition table and diagram, resulting in a minimized DFA. Two additional practice examples are listed to be completed applying the same procedure.

Uploaded by

Monti bro
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
59 views13 pages

DFA Minimization Steps and Examples

This document is a lesson plan on minimizing deterministic finite automata (DFA). It begins with objectives to define minimization, understand the procedure, and complete examples. The procedure is described as identifying unreachable states, deriving state values, constructing a new transition table, and diagram. An example is provided showing the full steps: identifying an unreachable state, deriving equivalence classes, constructing the new transition table and diagram, resulting in a minimized DFA. Two additional practice examples are listed to be completed applying the same procedure.

Uploaded by

Monti bro
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Amritsar College of Engineering & Technology, Amritsar, Punjab, INDIA

NAAC - A grade, NBA accredited courses(2009-12, 2016-18), UGC Autonomous College

SUBJECT: THEORY OF COMPUTATIONS


TOPIC: Minimization of DFA

Er. Pavitar Singh


Assistant Professor
Department of Computer Science and
Engineering

11 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


OBJECTIVES

After going through this topic, you should be able to:

• Define the minimization;


• Understand the procedure for minimization;
• Hands-on with various examples.

22 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Minimization of DFA
 Minimization of DFA means reducing the number of states from given
FA. Thus, we get the FSM(finite state machine) with redundant states
after minimizing the FSM.

Procedure:
 Step 1 : Identify unreachable state if any.
 Step 2 : Derivation of Values.
 Step 3 : Construction of New transition table.
 Step 4 : Construction of New transition diagram.

Note : Minimization is possible for DFA only, if you will be given with
NDFA then it needs to be converted into DFA first.

3 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Example 1 : Construct the minimum state automata
equivalent to the finite automata.

4 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Draw the transition table from the given transition diagram
State/Σ 0 1
→ q0 q1 q5

q1 q6 q2

*q2 q0 q2

q3 q2 q6

q4 q7 q5

q5 q2 q6

q6 q6 q4

q7 q6 q2

Step 1:- Identify unreachable state if any. If unreachable state is there,


remove it from the table. Here you can see from the table, q3 is unreachable
state. So remove it from the table.

5 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Step 2 : Derive the values
Q1• = Set of all final states
= {q2}
Q2• = Except final states all the remaining states.
= {q0,q1,q4,q5,q6,q7} State/Σ 0 1
→ q0 q1 q5
Construction of ∏ starts until ∏n
becomes equal to ∏n+1 q1 q6 q2
∏0 = Combination of Q1• & Q2•
*q2 q0 q2
= {{q2},{q0,q1,q4,q5,q6,q7}}
  ∏1 ={{q2},{q0,q4,q6},{q1,q7},{q5}} q4 q7 q5
∏2= {{q2},{q0,q4},{q6},{q1,q7},{q5}}
∏3= {{q2},{q0,q4},{q6},{q1,q7},{q5}} q5 q2 q6
∏3=∏2 q6 q6 q4
Therefore, Further minimization is not possible.
  q7 q6 q2

6 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Step 3 : Construction of New transition table

State/Σ 0 1

→ [q0, q4 ] [q1, q7 ] [q5]

[q1, q7 ] [q6] [q2]

*[q2] [q0, q4 ] [q2]

[q5] [q2] [q6]

[q6] [q6] [q0, q4 ]

7 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Step 4 : Construction of New transition diagram

8 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Example 2 : Minimize the following finite automata.

9 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Step 1 :

Step 2 : Derivation of values

10 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Step 3 : Construction of New TT

Step 4 : Construction of New TD

11 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Example 3 : Minimize the following finite automata.

12 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC


Solution:

13 Er. Pavitar Singh [Link]@[Link] CSE 7 th Sem. TOC

You might also like