Non deterministic automata (NFA) to Deterministic finite automata (DFA) Conversion


  NFA to DFA Conversion

Step 1: Construct the NFA Transition Table

Step 2: Take the initial state of the NFA as the first DFA state.

Step 3:For the first DFA state, calculate the transitions for every input symbol.
             For example:
                            Input 0 → Find the transition
                            Input 1 → Find the transition

Step 4: Whenever a new DFA state is obtained, calculate its transitions again for all input symbols.

Step 5: Continue the Process

             If another new state is obtained, calculate 0 and 1 for that state also.

             Continue this process until no new DFA state is obtained.


Step 6: Identify the Final States

Suppose the original NFA has:

q0 → non-final

q1 → final

Now check each DFA state:

{q0} → does not contain q1 → Not final

{q0,q1} → contains q1 → Final

{q1} → contains q1 → Final


Step 7: Construct the DFA Transition Table and Draw the Equivalent DFA

..(Read more)

Handwritten Notes- Click Here

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