patternMinor
Who invented the state elimination algorithm for converting finite automata into regular expressions?
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!
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
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.