State Elimination Method

Arden's Method is not capable of converting Ɛ-NFA.

Rules to convert a DFA/NFA//Ɛ-NFA into corresponding Regular Expression. 

Steps of the State Elimination Method:

Preprocessing the FA:

• Single Initial State with No Incoming Transitions: If the initial state has incoming transitions, or if there are multiple initial states (in the case of an NFA), introduce a new, unique initial state and add an 

                                               

$?$

            -transition (or a transition with an empty string) from this new state to the original initial state(s).

• • Single Final State with No Outgoing Transitions: If there are multiple final states or if the single final state has outgoing transitions, introduce a new, unique final state. Change all original final states to non-final states and add
    

    $?$
    -transitions from each of them to the new final state.
• State Elimination:

  • Iteratively select a state (other than the new initial and final states) to eliminate.
  • For each pair of states (A, B) such that there's a path from A to B that goes through the state being eliminated (let's call it Q), modify the transition from A to B.
  • The general formula for eliminating a state Q with a self-loop labeled R from A to B (where
    

    ${?}_{??}$
    is the transition from A to Q,
    

    ${?}_{??}$
    is the self-loop at Q, and
    

    ${?}_{??}$
    is the transition from Q to B) is: 

${?}_{?}^{\prime }={?}_{??}+{?}_{??}({?}_{??}{)}^{*}{?}_{??}$

$R_{AB}$

is the existing transition from A to B (if any), and

$R_{AB}^{\prime }$

is the new transition label. If there's no direct transition

$R_{AB}$

, it is considered to be

$\varnothing$

${\mathrm{<br>}}_{}$

${\mathrm{<br>}}_{}$

${\mathrm{<br>}}_{�}$

${\mathrm{any),\; and }}_{}$

${\mathrm{<div\; style="text-align:\; justify;">is\; the\; new\; transition\; label.\; If\; there\text{'}s\; no\; direct\; transition\; 𝑅𝐴𝐵,\; it\; is\; c</div><div\; style="text-align:\; justify;">o</div><div\; style="text-align:\; justify;">nsidered\; to\; be\; \Phi ,\; if\; no\; transition</div><div\; style="text-align:\; justify;"><br></div><div\; style="text-align:\; justify;"><br></div><div\; style="text-align:\; justify;"><br></div>}}_{}$

• Repeat: Continue eliminating states until only the new initial and new final states remain. The regular expression on the transition from the initial state to the final state will be the equivalent regular expression for the original FA.

Adding new initial state if there is an incoming edge

Adding new final state if there is an outgoing edge

Considering Multiple Final State

Example:

After preprocessing

Eliminate State B and C in any order as you wish answer will be the same in both cases, now let's eliminate B first. Eliminate B and imagine if there wouldn't have been any State B then we reach State C directly from Start state A with the input symbol of 'Ɛb*a' we can neglect Ɛ then input symbol will be 'b*a' from A to C. Outgoing edge from State C to B is now become self Loop since State B is not there, compare images above and below after removal of B state. 

Edge from C is going to B, taking b* and returning to C with 'a' this can happen infinite time hence self-loop of b(b)*a. We can the two self-loops 'a' and 'bb*a' as (bb*a +a) meaning we can traverse one loop at a time. Either a or bb*a as resultant (bb*a + a) is a closure on C state = (bb*a + a)*.

Now after eliminating C state, We would reach final State D directly from initial state A, now we were reaching State C by input of 'b*a' on C state we are taking infinite loops on (bb*a + a) and with Ɛ reaching final state D. hence Finally no normal states remaining we got a stream of input symbols directly from initial to final which is b*a(bb*a + a)*.