Minimization of DFA using Table Filling method (Myhill -Nerode Theorem)

 

Minimization of DFA (Table Filling Method)

DFA Minimization is the process of reducing the number of states in a DFA without changing the language accepted by the DFA.

In the Table Filling Method, pairs of states are checked to determine whether they are equivalent or distinguishable.

If two states cannot be distinguished by any input string, they are considered equivalent states and can be combined into one state.

Example: 
                                     

State

Input 0

Input 1

A

B

F

B

G

C

C

A

C

E

H

F

F

C

G

G

G

E

H

G

C

Final State = {C}

Non-Final States = {A, B, E, F, G, H}


Step 1: Construct the State Pair Table

A final state and a non-final state cannot be equivalent.

                 Final State + Non-Final State → Mark(X)

Since C is the only final state, the following pairs are immediately marked:

                     (A,C), (B,C), (C,E), (C,F), (C,G), (C,H)
The remaining pairs are initially left unmarked.

B

Unmarked


C

X

X


E

Unmarked

Unmarked

X


F

Unmarked

Unmarked

X

Unmarked


G

Unmarked

Unmarked

X

Unmarked

Unmarked


H

Unmarked

Unmarked

X

Unmarked

Unmarked

Unmarked

State

A

B

C

E

F

G



Iteration 1
Now check every unmarked pair.

For a pair (A,B):
  • Compare the next state of A and B for input 0.
  • Compare the next state of A and B for input 1.
  • If either resulting pair is already marked X, mark the current pair X.

Pair

0

1

Result

(A,B)

(B,G)

(F,C)

X

(A,E)

(B,H)

(F,F)

Blank

(A,F)

(B,C)

(F,G)

X

(A,G)

(B,G)

(F,E)

Blank

(A,H)

(B,G)

(F,C)

X

(B,E)

(G,H)

(C,F)

X

(B,F)

(G,C)

(C,G)

X

(B,G)

(G,G)

(C,E)

X

(B,H)

(G,G)

(C,C)

Blank

(E,F)

(H,C)

(F,G)

X

(E,G)

(H,G)

(F,E)

X

(E,H)

(H,G)

(F,C)

X

(F,G)

(C,G)

(G,E)

X

(F,H)

(C,G)

(G,C)

X

(G,H)

(G,G)

(E,C)

X

After checking all the pairs, the pairs that remain unmarked are:
(A,E), (A,G), (B,H)
All other pairs have been marked X.
 
 After Iteration 1, the state-pair table

B

X


C

X

X


E

Unmarked

X

X


F

X

X

X

X


G

Unmarked

X

X

X

X


H

X

Unmarked

X

X

X

X

State

A

B

C

E

F

G




Iteration 2
Recheck only the blank pairs from Iteration 1.

Pair

0

1

Result

(A,E)

(B,H)

(F,F)

Blank

(A,G)

(B,G)

(F,E)

X

(B,H)

(G,G)

(C,C)

Blank

The remaining unmarked pairs are:
(A,E), (B,H)

After Iteration 2, the state-pair table

B

X


C

X

X


E

Unmarked

X

X


F

X

X

X

X


G

X

X

X

X

X


H

X

Unmarked

X

X

X

X

State

A

B

C

E

F

G




Iteration 3
Recheck only the blank pairs from Iteration 2.

Pair

0

1

Result

(A,E)

(B,H)

(F,F)

Blank

(B,H)

(G,G)

(C,C)

Blank

Both resulting pairs remain unmarked.
Therefore, the unmarked pairs are equivalent states.




Equivalent States
     A ≡ E
     B ≡ H

Therefore, combine:
A and E → [AE]
B and H → [BH]

The other states remain separate:
C, F, G


Transition Table of Minimized DFA

State

0

1

[AE]

[BH]

F

[BH]

G

C

C

[AE]

C

F

C

G

G

G

[AE]

Number of states before minimization = 7
Number of states after minimization = 5

Thus, the DFA is minimized from 7 states to 5 states without changing the language accepted by the DFA.
 


Handwritten Notes- Download PDF

Video Explanation-Watch on YouTube




Comments

Post a Comment

Popular posts from this blog

B+ Tree in DBMS | B+ Tree in Data Structure

    B+  Tree A B+ Tree is a self-balancing multi-way search tree   All leaf nodes are present at the same level . Actual data records are stored only in the leaf nodes . Internal nodes contain only search keys . It is mainly used for efficient searching and sequential access . B+ Tree supports efficient range queries . Structure of B+ Tree Consider a B+ Tree node containing keys and children: Number of Keys Number of Children 1 2 2 3 3 4 In general, Number of children = Number of keys + 1 The leaf nodes are connected sequentially using links( Linked List ). Rules of B+ Tree For a B+ Tree of order m : At most: A node can have at most m children . A node can contain at most m − 1 keys. At least: An internal node must have at least [ m/2 ] children . An internal node must contain at least [ m/2 ] − 1 keys . Insertion...
Read more

Normalization in DBMS,(1NF,2NF,3NF,BCNF,4NF,5NF)

                      Normalization in DBMS Normalization divides a large table into smaller , logically related tables and connects them using appropriate keys. The main purpose of normalization is to reduce unnecessary duplication of data and prevent problems that may occur when data is inserted, updated, or deleted. 1. First Normal Form (1NF) A relation is said to be in First Normal Form (1NF) when every attribute contains a single, indivisible value . Conditions of   1 NF Each cell must contain only one value. Multiple values should not be stored in the same field. ·         Example Customer Items Purchased Gowsi Rice, Dal Tamil Soap ·   Here, the Items Purchased column contains more than one value for Gowsi . ·   Therefore, the table is not in 1 NF . Converting it into 1NF. ...
Read more

Hashing in Data Structure | Collision Resolution Techniques | Hashing in DBMS

  Hashing in DBMS Hashing is a technique used to map data elements (keys) to specific locations in a hash table using a hash function. It allows insertion and retrieval of data efficiently     Hash Function A hash function converts a key into a hash code (index) , which is used to store and retrieve the data from a hash table.                                 h(k)=k mod m Where: k → Key m → Hash table size h(k) → Hash index  Hash Table A hash table is a data structure that stores data in an array format . Each position in the table is called a bucket , and the position is accessed using the hash function. Example Consider Keys                   (k) = 11, 18, 20, 25, 29, 33 Hash table size (m) = 7 Hash function:    h(k)=k mod m                     ...
Read more