Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors

NFA with ∈ to DFA Indirect Method

Indirect Method: 

In this method,

Step 01: Convert NFA with ∈ moves to NFA without ∈ moves.

Step 02: Than NFA without ∈ moves is converted to the DFA.


RGPV PYQs: 

Convert the following NFA with ε in to DFA using the indirect method of conversion.

NFA with ∈

Solution: 

Step 01: Convert NFA with ∈ moves to NFA without ∈ moves.

  • ∈-Closure of q0: {q0, q1, q2}
  • ∈-Closure of q1: {q1, q2}
  • ∈-Closure of q2: {q2}
StateabC
è q0{q0, q1, q2}{q1, q2}{q2}
q1Φ{q1, q2}{q2}
q2ΦΦ{q2}
Transition table: NFA without ∈


Step 02: NFA without ∈ moves is converted to the DFA using the subset construction method.

StateabC
{q0}{q0, q1, q2}{q1, q2}{q2}
{q1}DeadState{q1, q2}{q2}
{q2}DeadStateDeadState{q2}
{q0, q1, q2}{q0, q1, q2}{q1, q2}{q2}
{q1, q2}DeadState{q1, q2}{q2}
DeadStateDeadStateDeadStateDeadState