5
$\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!

| cite | improve this question | |
$\endgroup$
3
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – templatetypedef May 22 '15 at 21:44

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.