NFA to an RE Kleene's Theorem

Question

Here is my NFA:

Here is my attempt.

• Create new start and final nodes
• Next eliminate the 2nd node from the left which gives me ab
• Next eliminate the 2nd node from the right which gives me ab*a
• Next eliminate the 2nd node from the left which gives me abb*b
• Next eliminate the 2nd node from the right which gives me b+ab*a

Which leads to abbb (b+aba)*

Is this the correct answer?

Answer 1

No you are not correct :(

_{you not need to create start state. the first state with - sign is the start state. Also a,b label means a or b but not ab}

_{there is a theorem called Arden's theoram, will be quit helpful to convert NFA into RE}

What is Regular Expression for this NFA?

In you NFA the intial part of DFA:

step-1:

(-) --a,b-->(1)   

means (a+b)

step-2: next from stat 1 to 2, note state 2 is accepting state final (having + sign).

(1) --b--->(2+)

So you need (a+b)b to reach to final state.

step-3: One you are at final state 2, any number of b are accepted (any number means one or more). This is because of self loop on state 2 with label b.

So, b* accepted on state-2.

step-4:

Actually there is two loops on state-2.

• one is self loop with label b as I described in step-3. Its expression is b*

• second loop on state-2 is via state-3.
  the expression for second loop on state-2 is aa*b
  why expression aa*b ?

  because:

            a-  
            ||               ====>  aa*b
            ▼|   
  (2+)--a-->(3) --b-->(2+)   
  

So, In step-3 and step-4 because of loop on state-2 run can be looped back via b labeled or via aa*b ===> (b + aa*b)*

So regular expression for your NFA is:

(a+b) b (b + aa*b)*