Minimization of DFA using partition method(Ardens Theorem)

 

Minimization of DFA using  partition method

Handwritten Notes- Click Here


Example: Minimization of DFA

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

Step 1: Initial Partition

The final state is:{C}
The non-final states are:{A, B, E, F, G, H}

Therefore, the initial partition is:
Π₁ = {{A, B, E, F, G, H}, {C}}
Here, all non-final states are initially placed together, while the final state forms a separate group.


Step 2: First Partition Refinement
Now examine the transitions of the states in each group.
For each state, check where it goes on input 0 and input 1.

Π₁ = {{A, B, E, F, G, H}, {C}}
                 Group①                  ②

Input 0

Input 1

Π₂ = {{A, E, G}, {B, H}, {F}, {C}}
  So, four groups are obtained.


Step 3: Second Partition Refinement
Again, check the transitions of the states within each group.

Π₂ = {{A, E, G}, {B, H}, {F}, {C}}
                    ①            ②     ③     ④

Input 0

Input 1


Π₃ = {{A, E}, {B, H}, {G}, {F}, {C}}
Five groups are obtained.               


Step 4: Check for Further Changes
Now check the groups again.

Π₃ = {{A, E}, {B, H}, {G}, {F}, {C}}
               ①             ②          ③   ④       ⑤

Input 0

Input 1

Πfinal = {{A, E}, {B, H}, {G}, {F}, {C}}

The groups remain unchanged after the next comparison.


Step 5: Construct the Minimized DFA

Each equivalence class is represented by one state.We can represent the new states as

[AE]
[BH]
[G]
[F]
[C]

Minimized State

Input 0

Input 1

[AE]

[BH]

[F]

[BH]

[G]

[C]

[C]

[AE]

[C]

[F]

[C]

[G]

[G]

[G]

[AE]

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