[go: up one dir, main page]
Scribd
Upload
153 views10 pages

DFA Minimization

The document summarizes the steps to minimize a deterministic finite automaton (DFA). It explains that minimizing a DFA means reducing the number of states. The key steps involve: 1) removing unreachable states, 2) constructing a transition table, 3) splitting it into tables for final and non-final states, 4) finding and merging similar rows that have the same transitions, 5) repeating until no similar rows remain, and 6) combining the tables. An example demonstrates applying the steps to minimize a sample 5-state DFA into a 3-state minimized DFA.

Uploaded by

Mahesh Thosar
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
153 views10 pages

DFA Minimization

The document summarizes the steps to minimize a deterministic finite automaton (DFA). It explains that minimizing a DFA means reducing the number of states. The key steps involve: 1) removing unreachable states, 2) constructing a transition table, 3) splitting it into tables for final and non-final states, 4) finding and merging similar rows that have the same transitions, 5) repeating until no similar rows remain, and 6) combining the tables. An example demonstrates applying the steps to minimize a sample 5-state DFA into a 3-state minimized DFA.

Uploaded by

Mahesh Thosar
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
You are on page 1/ 10

JD College of Engineering and

Management, Nagpur, B.tech Second


year (2021-22)
Semester : 4
Branch : IT
Subject : Theory Of Computation
Topic : DFA Minimization

Group No 8 Guided by :
Students name and roll number :
Prof. Supriya Sawwashere
Dhammadip mendhe(IT27)
Swaraj badole(IT54)
Joel craig(IT32)
Shoyeb sheikh (IT51)
Shrutik taksande (IT52)
INDEX :-

 DFA Minimization
 DFA Minimization steps
 Example
 DFA Minimization

• 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.
 We have to follow the various steps to
minimize the DFA. These are as follows:

Step 1: Remove all the states that are unreachable from


the initial state via any set of the transition of DFA.

Step 2: Draw the transition table for all pair of states.

Step 3: Now split the transition table into two


tables T1 and T2. T1 contains all final states,
and T2 contains non-final states.
Step 4: Find similar rows from T1 such that:

1. δ (q, a) = p  
2. δ (r, a) = p  

That means, find the two states which have the


same value of a and b and remove one of them.

Step 5: Repeat step 3 until we find no similar rows


available in the transition table T1.

Step 6: Repeat step 3 and step 4 for table T2 also.

Step 7: Now combine the reduced T1 and T2 tables. The


combined transition table is the transition table of
minimized DFA.
 Example
:

Solution:

Step 1: In the given DFA, q2 and q4 are the


unreachable states so remove them.
Step 2: Draw the transition table for the rest of the states.

State 0 1

→q0 q1 q3
q1 q0 q3
*q3 q5 q5
*q5 q5 q5

Step 3: Now divide rows of transition table into two sets as:

1. One set contains those rows, which start from non-final


states:
State 0 1

q0 q1 q3
q1 q0 q3
2. Another set contains those rows, which starts from final states.

State 0 1

q3 q5 q5
q5 q5 q5

Step 4: Set 1 has no similar rows so set 1 will be the same.

Step 5: In set 2, row 1 and row 2 are similar since q3 and q5 transit to the same
state on 0 and 1. So skip q5 and then replace q5 by q3 in the rest.

State 0 1

q3 q3 q3
Step 6: Now combine set 1 and set 2 as:
Thank You

You might also like