Epsilon free NFA to DFA Conversion - Examples

 

Every nondeterministic finite automaton (NFA) can be converted to a deterministic finite automaton (DFA).

Subset construction(power set construction) is a method to convert an NFA (Nondeterministic Finite Automaton) to an equivalent DFA (Deterministic Finite Automaton).
It works by treating each DFA state as a set of NFA states.

🔹 Algorithm (ε-free version):

  1. Initial DFA state: A set containing just the initial state of the NFA.

  2. For each DFA state S and each input symbol a:

    • Let T = ∪ δ(q, a) for all q ∈ S

    • T becomes a new DFA state (if not already present).

    • Create a transition from S to T on a.

  3. Repeat until all states and transitions are constructed.

  4. Accepting states of DFA: All those DFA states containing at least one accepting NFA state.

✅ Important Notes:

  • This is a mechanical process.

  • No ε-closure computation is required.

  • The DFA might have up to 2ⁿ states if the NFA has n states.

  • The resulting DFA accepts the same language as the original NFA.

  • The method guarantees equivalence and termination

Example 1: NFA to DFA Conversion

Problem: Draw an NFA that accepts all the strings ending with “1” over Σ {0,1} and convert this NFA to its corresponding DFA.

Step 01: Draw NFA Graph

The following is the NFA graph 

Step 02: Draw the NFA transition Table.

The NFA transition table of the above NFA is given below

Step 03: Conversion of NFA To DFA transition Table

First, Select the first row of the NFA transition table, which will become the first  row of the DFA transition table. It is given below


The q0q1 is a new state and will be added to the states column. Following is the Transitions for q0q1.


The transition of q0q1 against input 0 is q0, and the transition against input 1 is q0q1. Hence, the updated DFA table is given below.


At this stage, all newly generated states are executed successfully for their transitions. So, the DFA table is ready.

Important: As q1 was the final state in NFA Table. That’s why, all those states will be the final states where q1 is present. Simply mark with “*” to represent the final state. 

So, the following is the updated table of DFA with its final states


Step 4: Now draw DFA according to the DFA transition table

The DFA transition table contains two states (q0, q0q1) in its state column. Thus, the desired DFA machine graph will contain these similar states, and transitions will be made according to the DFA transition table.


Example 02: NFA to DFA Conversion

Problem: Draw an NFA of all binary strings in which the 2nd last bit is 1 and convert this NFA to its corresponding DFA.

Step 01: Draw NFA Graph.

The following is the NFA graph


Step 02: Draw the NFA transition Table.

The NFA transition table of the above NFA is given below

Step 03: Conversion of NFA To DFA transition Table

First, Select the first row of the NFA transition table, which will become the first  row of the DFA transition table. It is given below


The q0q1 is a new state and will be added to the states column. Following is the Transitions for q0q1.

([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0} ∪ {q2}  

                      = [q0q2]  // new state generated

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q0q1} ∪ {q2}  

                      = {q0q1q2}  // new state generated

The transition of q0q1 against input 0 is q0q2, and the transition against input 1 is q0q1q2. Hence, the updated DFA table is given below.


q0q2 and q0q1q2 are the new states for the states column. We need to find the transitions for both newly generated states. Following is the Transitions for q0q2.

δ([q0q2], 0) = δ(q0, 0) ∪ δ(q2, 0)  

                      = {q0} 

                      = [q0]   // already found in DFA table

δ([q0q2], 1) = δ(q0, 1) ∪ δ(q2, 1)  

                      = {q0q1}

                      = {q0q1}  

                      = [q0q1]  // already found in DFA table

The transition of q0q2 against input 0 is q0, and the transition against input 1 is q0q1. Hence, the updated DFA table is given below.

Following is the Transitions for q0q1q2.

δ([q0q1q2], 0) = δ(q0, 0) ∪ δ(q1, 0)  ∪ δ(q2, 0)  

                      = {q0} ∪ {} ∪ {q2}

                      = [q0q2]   // already found in DFA table

δ([q0q1q2], 1) = δ(q0, 1) ∪ δ(q1, 1)  ∪ δ(q2, 1)   

                      = {q0} ∪ {q1} ∪ {q2}

                      = [q0q1q2]  // already found in DFA table

The transition of q0q1q2 against input 0 is q0q2, and the transition against input 1 is q0q1q2. Hence, the updated DFA table is given below.

At this stage, all newly generated states are executed successfully for their transitions. So, the DFA table is ready.

Important: As q2 was the final state in NFA, all those states will be the final in DFA where q2 exists. Therefore, the DFA Table with all its final states is given under,


Step 4: Now draw DFA according to the DFA transition table

The DFA transition table contains four states (q0, q0q1, q0q2, q0q1q2) in its state column. Thus, the desired DFA machine graph will contain these similar states, and transitions will be made according to the DFA transition table.


Example 3: NFA to DFA Conversions

The following is the NFA graph that needs to be converted to a DFA.


Step 02: Draw the NFA transition Table.

The following is the NFA transition table which is derived from the given NFA.

Step 03: Conversion of NFA To DFA transition Table

First, Select the first  rows of the NFA transition table, which will become the first  row of the DFA transition table. It is given below

The q0q1 is a new state (as it does not exist in the NFA table) and will be added to the states column of the DFA table. Following is the Transitions for q0q1.

δ([q0q1], 0) = δ(q0, 0) ∪ δ(q1, 0)  

                      = {q0q1} ∪ {ϕ}  

                      = {q0q1}

δ([q0q1], 1) = δ(q0, 1) ∪ δ(q1, 1)  

                      = {q1} ∪ {q0q1}  

                      = {q0q1}

Following is the updated DFA table

The q1 is a new state and will be added to the states column. Following is the Transitions for q1.

δ([q1], 0) = {qϕ}  

δ([q1], 1) = {q0q1}

The following is the updated DFA table with all  its final states

The above given is the required DFA table

Important: As q1 was the final state in NFA Table. That’s why, all those states will be the final states where q1 is present. Simply mark with “*” to represent the final state.

Step 4: Now draw DFA according to the DFA transition table

The following is the converted DFA from the given NFA.



Comments

Post a Comment

Popular posts from this blog

Theory Of Computation PCCST302 KTU Semester 3 BTech 2024 Scheme

About Me Course Details and Syllabus Module-1 Foundations of Finite Automata Motivation-Computability Need for Mathematical Modelling and automata Introducing automata     on-off switch     coffee vending machine Alphabet, Strings, and Languages Formal Definition of Finite Automata Deterministic Finite Automata - DFA Dead state in DFA Categories of DFA      Category 1: Accept Only the Given Input      Category 2: Starts and ends with      Category 3: Contains substring      Category 4: Specific length     Category 5: Divisibility ( Binary Numbers) Examples  DFA( University Questions) DFA Implementation C Program Non Deterministic Finite Automata - NFA Epsilon NFA  (∈-NFA) Examples NFA( University Questions) Regular Languages Epsilon Closure of NFA Eliminating Epsilon Transitions from NFA Epsilon Free NFA to DFA Conversion - Examples DFA state minimization DFA vs NFA Applications of Fini...
Read more

Non deterministic Finite Automata NFA

Image
  🤖 Formal Definition of NFA An NFA (Nondeterministic Finite Automaton) is a theoretical machine used to recognize regular languages , like a DFA, but it allows multiple transitions for the same input or even no input at all (ε-transitions) . 📘 An NFA is defined as a 5-tuple : M = ( Q , Σ , δ , q 0 , F ) M = (Q, \Sigma, \delta, q_0, F) Where: Symbol Description Q Q A finite set of states Σ \Sigma A finite set called the input alphabet δ \delta The transition function : δ : Q × ( Σ ∪ { ε } ) → 2 Q \delta: Q \times (\Sigma \cup \{\varepsilon\}) \rightarrow 2^Q  (a set of states) q 0 q_0 ​ The initial state , q 0 ∈ Q q_0 \in Q F F The set of accepting states , F ⊆ Q F \subseteq Q 💡 Key Differences from DFA: DFA NFA Only one transition per input                Multiple transitions possible No ε-transitions                ε-transitions allowed Deterministic      ...
Read more

Example DFAs University Questions

Image
 Even number of a's ab as a substring empty set All strings except the empty set over the alphabet {0.1} Accept empty string and 0 every odd position of the string w is 1 begins with 1 ends with 0 {w| w contains at least 3 ones }  {w|w contains the substring 0101 ie; w=x0101y for some x and y} {w|w has length at least 3 and its third symbol is a zero} {w|w starts with 0 and has odd length , or starts with 1 and has even length } construct a DFA which accepts the language L = {a^N | N ≥ 1} String in {a,b} with odd number of a's starting with 01 over the alphabet [1,0} Strings ending with abc Program to build a DFA that checks if a string ends with "01" or "10" build a DFA to accept strings that start and end with same character build DFA that starts and end with 'a' from input (a, b) build a DFA that accepts strings starting and ending with different character DFA of a string starting with 0 and ends with 10? DFA of a string of a's and b's  st...
Read more