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?

$\endgroup$
5
  • 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.
    Commented Jan 16, 2016 at 17:50
  • 2
    $\begingroup$ Many regular expressions generate any given language. Finding the shortest one is computationally hard. $\endgroup$ Commented Jan 16, 2016 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$
    – Mahesha999
    Commented Jan 16, 2016 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.
    Commented Jan 16, 2016 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
    Commented Mar 6, 2019 at 8:04

3 Answers 3

6
$\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.

$\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.

$\endgroup$
0
$\begingroup$

Replacing your $\{0,1\}$, respectively by $\{a,b\}$ and using more algebraic notation with $1$ in place of $ε$, the automaton can be presented either as a right-affine system $$ A ≥ a A + b B + 1,\quad B ≥ a C + b B,\quad C ≥ a A + b B,\quad A $$ or a left-affine system $$ A ≥ A a + C a + 1,\quad B ≥ A b + B b + C b,\quad C ≥ B a,\quad A $$ where, in both cases, the last item refers to the "starting expression", following the remainder of the system, which is a fixed-point system of inequations in $(A,B,C)$ whose solution is to be applied to the starting expression. The solution is chosen as the least fixed point solution over a Kleene algebra. That's the contemporary framing of the problem (i.e. inequations, not equations).

Apart from that, everything else you said applies. Your methods - worked out on the left-affine system - yield $$(a + b (b + a b)^* a a)^*,\quad (a + b b^* a (b b^* a)^* a)^*,$$ and you forgot the Kleene-star on the second expression, as your diagram indicates should be there.

All Kleene algebra identities can be derived from a small set of equational properties (namely: those for an idempotent semiring, a.k.a. "dioid" as it is sometimes also known as) ... plus two conditional properties that can be stated as follows: $$μx·(a + b x) = b^* a,\quad μx·(a + x c) = a c^*,$$ where $μx·φ(x)$ denotes the least fixed point solution to $x ≥ φ(x)$. You could call those the "Arden Equations", if you wish. They have no official name. All finite one-sided affine systems have least fixed point solutions - under these axioms. And all properties of the algebras of regular expressions (which are known as the "free Kleene algebras") can be derived from these axioms.

For your case, you have the identity $(u + v)^* = u^* (v u^*)^*$. Thus $$(b + a b)^* = b^* (a b b^*)^*.$$ From this, it follows that $$a + b (b + a b)^* a a = a + b b^* (a b b^*)^* a a.$$

Then, you have the identity $(u v)^* u = u (v u)^*$, from which it follows that $$b b^* (a b b^*)^* a = b b^* a (b b^* a)^*.$$ Thus, $$a + b (b + a b)^* a a = a + b b^* a (b b^* a)^* a.$$ This shows that your two expressions are equal.

Using distributivity $u (v + w) = u v + u w$, you can proceed to write $$a + b b^* (a b b^*)^* a a = (1 + b b^* a (b b^* a)^*) a.$$ From the property $1 + u u^* = u^*$, it follows that $$(1 + b b^* a (b b^* a)^*) a = (b b^* a)^* a.$$

Thus, your expression can also be written as $$((b b^* a)^* a)^*.$$ Using the property $(u^* v)^* = 1 + (u + v)^* v$ (which can be derived from the ones already listed), it follows that $$((b b^* a)^* a)^* = 1 + (b b^* a + a)^* a.$$ Using distributivity on the other side $(u + v) w = u w + v w$ and the other properties already cited, we have $$(b b^* a + a)^* = ((b b^* + 1) a)^* = (b^* a)^* = 1 + (a + b)^* a,$$ which also used commutativity $a + b = b + a$.

Thus $$((b b^* a)^* a)^* = 1 + (b b^* a + a)^* a = 1 + a + (a + b)^* a a.$$

For the right-affine system you can reverse-substitute $C$ in for $a A + b B$ to get: $$ A ≥ C + 1,\quad B ≥ a C + b B,\quad C ≥ a A + b B,\quad A. $$ Nobody ever said you always had to eliminate variables. You can put them back in, too.

Now, you can eliminate $A$, applying distributivity (and commutativity) $$ B ≥ a C + b B,\quad C ≥ a + a C + b B,\quad 1 + C. $$ Then you can reverse-substitute $B$ for $a C + b B$ to get $$ B ≥ a C + b B,\quad C ≥ a + B,\quad 1 + C. $$ Then, you can forward-substitute and eliminate $C$ (and apply distributivity) to get $$ B ≥ a a + (a + b) B,\quad 1 + a + B. $$ Finally, use the Arden axiom on $B$ to get $$ B ≥ (a + b)^* a a,\quad 1 + a + B. $$ and substitute out $B$: $$1 + a + (a + b)^* a a.$$

For the left-affine system, if you first factor, you get: $$ A ≥ (A + C) a + 1,\quad B ≥ (A + B + C) b,\quad C ≥ B a,\quad A. $$ This shows that the actual variables are not $(A,B,C)$, but $$(A, D, E) = (A, A + C, A + B + C).$$ Reverse-substitute for $A$ and $B$ in $D$, and for $A$, $B$ and $C$ in $E$, and use commutativity to get $$ A ≥ 1 + D a,\quad B ≥ E b,\quad C ≥ B a,\quad A. $$ Then, reverse-substitute on the left-hand side and use commutativity and distributivity to get: $$ A ≥ 1 + D a,\quad D ≥ 1 + D a + B a = 1 + (B + D) a = 1 + E a,\\ E ≥ 1 + E a + E b = 1 + E (a + b),\quad A. $$ Forward-substitute for and eliminate $A$: $$ D ≥ 1 + E a,\quad E ≥ 1 + E (a + b),\quad 1 + D a. $$ Then, forward substitute for and eliminate $D$ and apply distributivity $$ E ≥ 1 + E (a + b),\quad 1 + a + E a a. $$ Apply the Arden axiom on $E$ $$ E ≥ (a + b)^*,\quad 1 + a + E a a. $$ Then forward-substitute for and eliminate $E$: $$1 + a + (a + b)^* a a.$$

If "simplicity" is measured by star-height, then this is optimial. It has star-height 1, while the other expressions have star-height 2. The problem of minimizing star-height is highly non-trivial, but solved (in the 1990's).

You can go much further with everything ... nowadays.

To get an algebra suited for context-free expressions it suffices to replace the Arden axioms by the μ-continuity/distributivity axiom $$u (μx·φ(x)) v = \sup_{n≥0} u φ^n(0) v,$$ where $$φ^0(x) = x,\quad φ^1(x) = φ(x),\quad φ^2(x) = φ(φ(x)),\quad φ^3(x) = φ(φ(φ(x))),\quad ⋯,$$ and $φ(x)$ is an arbitrary Kleene-polynomial in $x$. Solutions can be expressed Kleene-algebraically, using context-free expressions, e.g. $$μx·(u x v + w) = b (u p + q v)^* d,$$ which - here - extends the Kleene algebra given by $X = \{u,v,w\}$ by the inclusion of the "bracket operators" $Z = \{b,d,p,q\}$ satisfying $$b d = 1 = p q,\quad b q = 0 = p d,\quad x z = z x\quad (x ∈ X,\quad z ∈ Z).$$

They are known equivalently as μ-continuous Chomsky algebras / C-dioids the two characterizations having arisen, respectively, in 2013 and 2008, their equivalence proven in 2018. Their representation as Kleene-algebras with the bracket operators affixed is via a result, (finally and belatedly) put into the peer review literature a few years ago, that is an algebraic generalization of, and a completion of, the Chomsky-Schützenberger Theorem.

So, similar and more elaborate exercises can be used to crunch non-linear fixed-point systems (e.g. systems that correspond to context-free grammars, or translation grammars such as arise in parsing theory) into context-free expressions.

The worst cases, if you allow the sharing of sub-expressions, are cubic in the number of variables for turning one-sided affine systems into regular expressions; but linear (and star-height 1) - for both the affine and more general non-linear systems, if you use the bracket operators $\{b,d,p,q\}$.

If you allow for commutativity of the product - the situation that occurs with Parikh's Theorem - then the Arden axioms, alone, suffice and you can write $μx·φ(x) = φ'(φ(0))^* φ(0)$, where the usual rules of differentiation on polynomials (after noting, for instance, that $d(x^2)/dx = 2x = x$, since $x + x = x$ in Kleene algebras) is extended to the Kleene star with $d(x^*)/dx = x^*$. For commutative Kleene algebras, the star behaves like the exponential: $u^* v^* = (uv)^*$ and $0^* = 1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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