Search code examples
regexregular-languagefinite-automata

DFA to RE (Introduction to Automata Theory, Languages and Computation)

I've been struggling with this exercise for a while (3.2.3 from the book mentioned in the title). You are requested to transform a DFA to a RE. The automata is:

enter image description here

I tried to obtain the RE following the algorithm described in section 3.2.2 (state removal method), but I don't get the same RE than JFLAP (maybe it's equivalent, but I'm not sure if I'm applying the steps properly).

First step (state s removal): enter image description here

Second step (state r removal): enter image description here

The resulting RE is: L = (1*+(010*1+00)(1(01)*10*1)*0)* (According to JFLAP it is (1+00(10)*0+(01+00(10)*11)(0+1(10)*11)*1(10)*0)*)

Could please someone tell me where I'm wrong?

Solution

  • When you are removing S On qtheir must be loop 10Because between Sand qtheir is looping of (01). enter image description here

    In above example When we elimnate state 1 ,on state 1 their is loop 10 I hope so you easily understand it.