6
$\begingroup$

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. However, I can't seem to find any references to who first invented this algorithm.

Does anyone know who invented the state elimination algorithm? Ideally, I'd like a reference to a specific paper or textbook.

Thanks!

$\endgroup$

1 Answer 1

5
$\begingroup$

According to my information the technique is by J.A. Brzozowski and E.J. McCluskey. The method is described in Signal Flow Graph Techniques for Sequential Circuit State Diagrams, IEEE Transactions on Electronic Computers, 67 - 76, 1963. https://doi.org/10.1109/PGEC.1963.263416 (subscription needed)

Abstract: This paper considers the application of signal flow graph techniques to the problem of characterizing sequential circuits by regular expressions. It is shown that the methods of signal flow graph theory, with the proper interpretation, apply to state diagrams of sequential circuits. The use of these methods leads to a simple algorithm for obtaining a regular expression describing the behavior of a sequential circuit directly from its state diagram.

(emphasis mine)

Curiously, I could only find the technique in the French edition of wikipedia: Méthode de Brzozowski et McCluskey

$\endgroup$
3
  • 1
    $\begingroup$ Looks good! This paper cites an earlier paper on the transitive closure algorithm, noting that the regular expression generated to bypass a state matches the regular expression used in that earlier algorithm. Thanks for the information! $\endgroup$ May 22, 2015 at 21:44
  • $\begingroup$ I'm curious what brought you back to this question (2015) today, notably adding the observation that it is only found in French wikipedia? $\endgroup$ Jan 22 at 19:16
  • 1
    $\begingroup$ @KennethKho Another question involving expressions and automata I wanted to check lead back to this answer. I then decided to add a link to the original paper. As an afterthought I looked for wikipedia for to check the source, and noted it did not exist. $\endgroup$ Jan 23 at 1:19

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.