HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Who invented the state elimination algorithm for converting finite automata into regular expressions?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thefinitewhointoautomataeliminationregularexpressionsalgorithminvented

Problem

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!

Solution

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

Context

StackExchange Computer Science Q#42861, answer score: 5

Revisions (0)

No revisions yet.