2
$\begingroup$

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

Ardens method

enter image description here

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

enter image description here

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 1. One question per question, please. 2. "Any other observations?" is too broad and open-ended; see our help center. 3. We discourage "please check whether my answer is correct" questions (e.g., "Am I making any mistake?"), as only "yes/no" answers are possible, which won't help you or future visitors. Better to ask about a specific conceptual issue you're uncertain about. A good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W.♦ Jan 16 '16 at 17:50
  • 2
    $\begingroup$ Many regular expressions generate any given language. Finding the shortest one is computationally hard. $\endgroup$ – Yuval Filmus Jan 16 '16 at 17:54
  • $\begingroup$ @D.W. thanks, I understand your concern...unfortunately I am working professional & in remaining time I learn for my post grad. So I do not have fellow learners / friends. Doing it on my own. Mostly I end up asking broader questions because people on stackexchange are damn knowledged, so with broader questions I dont limit question hoping that someone will bring up even a small point not usually found in book & I will explore on it. But anyway next time I will be more careful before posting. $\endgroup$ – Maha Jan 16 '16 at 19:33
  • $\begingroup$ @Mahesha999, I sympathize. However, I'm afraid that "please check whether my answer is correct" is still not suitable on this site, for the reasons described in meta discussions here and here. I regret to say you may have to find some other resource to help with those particular kinds of questions, as they're not on-topic here. I understand this site is a great resource; setting and enforcing high standards for quality is part of what enables us to keep this site so awesome. $\endgroup$ – D.W.♦ Jan 16 '16 at 19:58
  • $\begingroup$ FWIW, equivalence of NFA is computable: determinise, minimise, check for isomorphism. (That's worst-case inefficient, but often tractable in exercise settings.) $\endgroup$ – Raphael♦ Mar 6 '19 at 8:04
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$
  • 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.