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

 

Minimization of DFA (Table Filling Method)

Handwritten Notes- Click Here

                                          

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)


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
Check all the remaining unmarked pairs.

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

Blank pairs:
(A,E), (A,G), (B,H)
 
 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

Blank pairs:
(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

No new pair is marked.
Therefore, the unmarked pairs are equivalent states.

Equivalent States
A ≡ E

B ≡ H

Transition Table of Minimized DFA

State

0

1

A

B

F

B

G

C

C

A

C

F

C

G

G

G

A

Number of states before minimization = 7

Number of states after minimization = 5


Video Explanation



Comments

Post a Comment

Popular posts from this blog

Queue ADT

Image
  Queue ADT Handwritten Notes- Click Here A  Queue  is a linear data structure in which elements are inserted at one end and removed from the other end.( Insertion → Rear,  Deletion → Front )                                   ↓ FRONT                                 ↓ REAR A B C D E    A queue follows the FIFO (First In, First Out) principle. This means that the element inserted first is removed first. A  Queue can be implemented using: Array Linked List Basic  Queue  Operations: 1. Enqueue - used to insert  a new element into the queue. 2. Dequeue - used to remove an element from the queue. 3. Peek - used to view the first element without removing it. 4. isEmpty - checks whether the queue contains any elements. 5...
Read more

Entity-Relationship(ER) Model

Image
Entity-Relationship(ER) Model Handwritten Notes - Click Here The Entity-Relationship (ER) Model is a conceptual data model. It helps database designers understand the requirements of a system before creating the actual database tables . It describes the important objects in a system, their properties , and the relationships between them. The three basic concepts of the ER model are Entity Attribute Relationship Entity An entity can be any real-world object, person, place, or class about which we want to store information in a database. In a traditional ER diagram, an entity is represented by a rectangle .                        Example: Employee and Department An employee works for a department. Here, Employee and Department are entities , and Works For is the relationship between them. Weak Entity A weak entity is an entity that depends on another entity for its identification of existence. A weak entity is represen...
Read more

Different types of Data Models in DBMS

Image
             Data Models Handwritten Notes- Click Here A Data Model defines how data is organized, stored, related, and accessed in a database. Types of Data Models in DBMS Hierarchical Data Model Network Data Model Relational Data Model Entity-Relationship (ER) Model Object-Oriented Data Model Object-Relational Data Model 1. Hierarchical Data Model   The Hierarchical Data Model organizes data in the form of a tree structure . Each child record has only one parent record . A parent record can have multiple child records . It mainly represents a one-to-many relationship . Data retrieval is very fast in the hierarchical model.                                   Company                   |            Department             /      ...
Read more