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

Remove ∈ transitions from NFA

RGPV PYQs

NFA with ∈

Solution.

Step 01: Find ∈-closure of (q1), (q2) and (q3).

  • ∈-closure of (q1) = {q1, q2, q3}
  • ∈-closure of (q2) = {q2, q3}
  • ∈-closure of (q3) = {q3}

For each state find the next state for each input.

See the table below,

State012
->q1{q1,q2,q3}{q2,q3}{q3}
q2φ{q2,q3}{q3}
q3φφ{q3}

From the question diagram, it is clear that only with ∈ input q1 and q2 state can reach to the final state.

So, now without ∈ input, q1 and q2 is also treated as final states.

As shown in diagram below.

NFA without ∈