1
$\begingroup$

The question asks to write the shortest regular expression possible to the following automaton:

enter image description here

I see only one way to tackle the problem:

Use one of the methods mentioned here How to convert finite automata to regular expressions? and then get a regular expression.

If for example I use the Transitive closure method, it will be hard to say that the regular expression at the end is "the shortest as possible".

My question is there any better way to tackle the problem than to use one of the conversion method of automata to regular expression.

I saw in this post Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one? that minimizing regular expressions is very hard, so according to it, starting with a long regular expression and trying to "shrink" it is not a good approach.

$\endgroup$

2 Answers 2

3
$\begingroup$

Frame it as the least fixed point solution to the following system in Kleene algebra: $$ A ≥ 1 + a B + b C,\quad B ≥ 1 + a D + b E,\quad C ≥ 1 + a D + b D,\\ D ≥ a B + b C,\quad E ≥ a C + b B,\quad A. $$ where the final term ($A$) indicates the "starting expression".

The worst case, generally, is cubic in the size of the system. One of the sample/test files in RegEx, which I put up on GitHub in the 2010's, shows the layout for a degree 4 system. The program "dfa" in it will be of particular use. If you run "dfa" on the demo file, you get a full matrix system with 4 variables.

As one optimization, here, substitute in for all the single-reference items (here: $A$ and $E$) and as another optimization, factor out (here: the $D$ in the inequation for $C$): $$ B ≥ 1 + a D + b a C + b b B,\quad C ≥ 1 + (a + b) D,\quad D ≥ a B + b C,\quad 1 + a B + b C. $$

The next best optimization is to in-line substitute $D$. It has the fewest references and no "$1 + ⋯$" in it: $$ B ≥ 1 + a (a B + b C) + b a C + b b B,\quad C ≥ 1 + (a + b) (a B + b C),\quad 1 + a B + b C. $$ Factor out the "B" and "C": $$ B ≥ 1 + (a a + b b) B + (a b + b a) C,\quad C ≥ 1 + (a + b) a B + (a + b) b C,\quad 1 + a B + b C. $$

You have a full system of degree 2 and you're making use of both variables in the starting expression, so I don't think you'll get any better than that. In general, the least fixed point solution to $$ B ≥ m + w B + x C,\quad C ≥ n + y B + z C $$ is $$ B = (w^* x z^* y)^* (w^* m + w^* x z^* n),\quad C = (z^* y w^* x)^* (z^* n + z^* y w^* m). $$

This can be more succinctly written as $$d = w^* m,\quad e = z^* n,\quad f = w^* x,\quad g = z^* y,\quad B = (f g)^* (d + f e),\quad C = (g f)^* (e + g d).$$

Applying this to the system on hand: $$m = 1,\quad n = 1,\quad w = a a + b b,\quad x = a b + b a,\quad y = (a + b) a,\quad z = (a + b) b,$$ and substituting in for $B$ and $C$, we get $$ w = a a + b b,\quad x = a b + b a,\quad y = (a + b) a,\quad z = (a + b) b,\\ d = w^*,\quad e = z^*,\quad f = w^* x,\quad g = z^* y,\\ 1 + a (f g)^* (d + f e) + b (g f)^* (e + g d). $$ Setting $v = a + b$, this can be written $$ v = a + b,\quad w = a a + b b,\quad x = a b + b a,\quad y = v a,\quad z = v b,\\ d = w^*,\quad e = z^*,\quad f = d x,\quad g = e y,\\ 1 + a (f g)^* (d + f e) + b (g f)^* (e + g d). $$

Just to check, this can be fed into "dfa" (which uses "|" instead of "+"). Strangely, I tried this two separate ways and it kept insisting that it's a much smaller system - namely this one (up to a change of notation): $$ A ≥ 1 + a B + b B,\quad B ≥ 1 + a D + b D,\quad D ≥ a B + b B,\quad A. $$ In other words, your $B = C$ and $D = E$. Oops. They are equivalent states. I didn't see that.

Apply the same methods to this system, instead. Factor $$ A ≥ 1 + (a + b) B,\quad B ≥ 1 + (a + b) D,\quad D ≥ (a + b) B,\quad A. $$ Remove the single references ($D$ and $A$): $$ B ≥ 1 + (a + b) (a + b) B,\quad 1 + (a + b) B. $$ Solve for $B$: $$B = ((a + b)(a + b))^*,$$ and the result is $$1 + (a + b)((a + b)(a + b))^*,$$ or more succinctly, $$v = a + b,\quad 1 + v (v v)^*.$$

There's a lot of heuristics. The one we should have used at the outset is: equivalent state reduction (which "dfa" uses and used).

In general, though, I don't think there is a clean-cut one-size-fits-all series of optimizations, though the ones used easily crunched your example. In general, cubic is the worst case - provided you maximally share sub-expressions (as I did in the cases all throughout, above).

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for the detail answer !! $\endgroup$
    – Daniel
    Commented Apr 20 at 9:51
3
$\begingroup$

To solve this question, you should not blindly apply some algorithm. Instead, start by understanding what the given automaton does. When you do this, you will see that the automaton is needlessly complicated for the language it describes - so any direct translation from automata to regular expressions will probably be horrible.

Also, once you've figured out which language the automaton describes, it shouldn't be too difficult to come up with a regular expression and some sense of why this is the shortest you can hope for.

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