I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows:
Let us form the equations
$q_1 = q_10 + q_30 + є$
$q_2 = q_11 + q_21 + q_31$
$q_3 = q_20$
Solving the eq_uations
$q_2 = q_11 + q_21 + (q_20)1 = q_11 + q_2(1 + 01)$
$q_2 = q_11 (1 + 01)^*$
So, $q_1 = q_10 + q_30 + є$
$q_1= q_10 + q_11(1 + 01)^*00 + є$
$= q_1(0 + 1(1 + 01)^*00) + є$
$= є (0 + 1(1 + 01)^*00)^*$
$q_1=(0 + 1(1 + 01)^*00)^*$
So the regular expression for the given automata is $=(0 + 1(1 + 01)^*00)^*$
When I solved above using state reduction method I got different answer:
State Reduction method
So final regex was $0+11^*0(11^*0)^*0$
However this is different from what we get from Arden's method. Am I making any mistake?
Or both are correct?
If correct, is there any way to get same regex as Arden's using state reduction?
Does Arden's method gives shortest regex?
Any other observations about two methods?