I have tried to convert the following DFA to regular expressions through two different methods: Arden's method, and state elimination one. I have arrived to two different regular expressions: Arden's method: $0(10)^*$. State elimination method: $0(10)^*1$

Are these two regular expressions correct for this DFA?

This is the DFA:

0 1
$\rightarrow$A : Start state B
$\leftarrow$B : Final state A

1 Answer 1


The first result $0(10)^*$ is correct. The second one is not, since the word $0$ should be accepted but dos not belong to $0(10)^*1$. You probably made a mistake when applying the state elimination method.

  • $\begingroup$ Can you show here how did you do state elimination please? $\endgroup$
    – Papa
    Mar 3, 2022 at 19:17
  • 1
    $\begingroup$ Sorry, but you should instead show what you have done in this regard. $\endgroup$
    – J.-E. Pin
    Mar 3, 2022 at 19:24
  • $\begingroup$ It s Ok I corrected it. I had a problem when assigning the DFA's final state to the new GNFA's final state a phi, whereas I should have assigned an epsilon and the rest non final states a phi, I did it and I got the same RE as Arden's one. $\endgroup$
    – Papa
    Mar 3, 2022 at 19:44
  • $\begingroup$ Can you help with this math.stackexchange.com/questions/4395409/anbn-language-vs-anbm $\endgroup$
    – Papa
    Mar 3, 2022 at 21:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .