why DFA to regex by two different methods differ

Question

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows:

Ardens method

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$

1. However this is different from what we get from Arden's method. Am I making any mistake?

2. Or both are correct?

3. If correct, is there any way to get same regex as Arden's using state reduction?

4. Does Arden's method gives shortest regex?

5. Any other observations about two methods?

Answer 1

No, these methods are not guaranteed to yield the shortest regexp. Therefore, there's no reason to expect them to necessarily yield the same regexp.

Given a regexp $R$, finding the shortest regexp $R'$ that is equivalent to $R$ is known to be PSPACE-complete, by a result of Meyer Stockmeyer. Consequently, none of these procedures can be expected to yield the shortest regexp. If they did, then we could just take $R$, convert it to a NFA, then convert it back to a regexp $R'$ using that method, and we'd have an efficient way to find the shortest regexp, implying that P = PSPACE -- something that is not believed to be true.

(In fact, it's even hard to approximate, i.e., to find a regexp that is close to the shortest.)

To learn more, see On Learning Regular Languages on the CSTheory.SE blog.

Answer 2

• There is a unique minimal state machine.
• There is NO unique minimal regular expression.

For example,

$(a b)^*a = a (ba)^*$

So even algorithms that yield a minimal expression need not yield the same result.