30
$\begingroup$

I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than the one in the book by Hopcroft and Ullman (1979). In there, the sets $R_{ij}^k$ are used to represent sets of strings that take the DFA from state $q_i$ to $q_j$ without going through any state numbered higher than $k$. This construction, although obviously correct and very useful, is rather technical.

I'm writing a monograph about algebraic automata theory and I don't want to distract my audience with too many technical details (at least not with details that are irrelevant for the results I want to show), but I do want to include a proof of the equivalence between DFA and regular expressions for the sake of completeness. For the record, I'm using Glushkov automata to go from a regular expression to a DFA. It seemed more intuitive than $\varepsilon$-transitions, which I didn't define at all (again, because I don't need them).

What other algorithms are known to go from a DFA to a regular expression? I value simplicity over efficiency (that's ``better'' for me in this case), but that is not a requirement.

Thanks in advance for your help!

$\endgroup$
8
  • 1
    $\begingroup$ It's not a different algorithm, but the $R^k_{ij}$ algorithm can be expressed algebraically, using the $k$th power of a matrix of regular expressions in the appropriate algebra. Perhaps you'll find this more elegant/concise. I'm looking for a reference. $\endgroup$
    – Max
    Dec 1, 2011 at 7:44
  • 1
    $\begingroup$ The $R^k_{ij}$ algorithm is essentially a variant of the Floyd-Warshall algorithm for the All-pairs-shortest-path problem, so you may find the presentation in terms of matrix multiplication by searching for these keywords. $\endgroup$ Dec 1, 2011 at 8:31
  • 2
    $\begingroup$ I concur. It is basically Floyd-Warshall algorithm. It can also be derived it using standard dynamic programming techniques (just like Floyd-Warshall can). $\endgroup$
    – david
    Dec 1, 2011 at 10:29
  • $\begingroup$ I am sure I answered a question like this before, but I can't find it. $\endgroup$
    – Raphael
    Dec 1, 2011 at 11:18
  • $\begingroup$ @Max could you find a reference? I'm interested in the matrix representation, it should be more appealing to algebrists actually. $\endgroup$
    – Janoma
    Dec 1, 2011 at 13:56

3 Answers 3

19
$\begingroup$

Two more constructions: Brzozowski-McCluskey aka state elimination [1], and Gaussian elimination in a system of equations using Arden's Lemma. The best source on these is probably Jacques Sakarovitch's book [2].

[1] J. Brzozowski, E. McCluskey Jr., Signal flow graph techniques for sequential circuit state diagrams, IEEE Transactions on Electronic Computers EC-12 (1963) 67–76.

[2] J. Sakarovitch, Elements of Automata Theory. Cambridge University Press, 2009.

$\endgroup$
4
  • 3
    $\begingroup$ I find the approach of solving equations using Arden's Lemma the simplest and easiest to explain, that's why I present it that way in an introductory theory class. $\endgroup$ Dec 1, 2011 at 8:27
  • $\begingroup$ The method of a system of equations sounds brilliant. Unfortunately, the library of my university doesn't have the book you mention (Sakarovitch), but I'm going to look elsewhere. $\endgroup$
    – Janoma
    Dec 1, 2011 at 13:53
  • 4
    $\begingroup$ The comparison of constructions is also found in Sakarovitch's paper "The Language, the Expression and the (small) Automaton", CIAA 2005, LNCS 3845, Springer (2006) 15-30. See infres.enst.fr/~jsaka/PUB/Files/LESA.pdf $\endgroup$ Dec 4, 2011 at 0:37
  • 2
    $\begingroup$ Also, note that the ordering in which the states are processed can greatly affect the size of the resulting regular expression. This holds always true: whether you do it with Arden's lemma, McNaughton-Yamada, state elimination, or another variant. Several simple heuristics for choosing a good elimination ordering are available. $\endgroup$ Dec 4, 2011 at 0:49
16
$\begingroup$

Kozen's book "Automata & Computability" mentions an elegant generalization of this Floyd-Warshall algorithm. Since you mentioned appealing to algebraists, you might find it useful. You'll find it on page 58-59 of that text. (I think google books has a preview.)

Basically, you can define a Kleene algebra on matrices whose entries are from a Kleene algebra. Addition/union of matrices is coordinate-wise addition. Multiplication/concatenation of matrices is just like regular matrix multiplication. Kleene star for $2 \times 2$ matrices is defined as:

$\begin{bmatrix} a & b \\ c & d \end{bmatrix}^* = \begin{bmatrix} (a+bd^*c)^* & (a+bd^*c)^*bd^* \\ (d+ca^*b)^*ca^* & (d+ca^*b)^* \end{bmatrix} $

You can see that if the left-hand matrix is the transition matrix of a 2-state DFA, then the $i,j$-entry of right-hand matrix describes the set of paths (of any length) from state $i$ to state $j$.

Then Kleene star of larger matrices is defined recursively: divide the $n \times n$ matrix into 4 quadrants/submatrices $a,b,c,d$, of dimensions $m\times m$, $m\times (n-m)$, $(n-m) \times m$, and $(n-m) \times (n-m)$, and apply the $2 \times 2$ rule above now with the matrix minors instead of "scalar" entries. (Analogously to how regular matrix multiplication can be defined recursively based on the rule for $2 \times 2$.)

So if you have an $n$-state NFA and its corresponding transition matrix $T$. Then an equivalent regular expression is $\sum_{f \in F} (T^*)_{s,f}$, where $s$ is the start state. $T^*$ can be evaluated recursively using the definition above.

Kozen claims that the case where you evaluate the matrix-star recursively using $m=1$ corresponds to the $R_{ij}^k$ algorithm.

Another derivation of the Kleene algebra structures over matrices appears in A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events by Kozen.

$\endgroup$
14
$\begingroup$

By far the nicest procedure I have seen is the one mentioned by Sylvain. In particular, it seems to yield more concise expressions than others.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

$\endgroup$
2
  • $\begingroup$ I also prefer that proof. I find it elegant and easy to explain. Even Arden's Lemma is not hard. I think this will be the method I will include in my document. $\endgroup$
    – Janoma
    Dec 3, 2011 at 14:38
  • $\begingroup$ @Raphael Saw the example in cs.stackexchange and found that there is some difference between the notations. You have used both $+$ and $\cup$ in document, but you have used only $\cup$ in the above document. I think both meant the same thing. For the consistency of notation you could consider changing that. Anyway that document saved my day :). Thanks for writing documents like this and releasing under open license. $\endgroup$
    – user3162
    Feb 28, 2013 at 0:28

Your Answer

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

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