Abstract :
Abstract—This paper considers the problem of obtaining realizations of synchronous finite automata from their regular expression specifications. A polylinear sequential circuit realization is defined, and it is proven that every synchronous finite automaton has such a realization. A method is developed for the derivation of a polylinear sequential circuit realization of any automaton specified by a regular expression. The method uses a derivative approach and is applied to the reverse of the given regular expression. As a by-product of developing the method, a connection between the state assigmnent problem and regular expressions is established. Another by-product is a simple method for obtaining polylinear sequential circuit realizations of automata specified by flow tables instead of regular expressions.
Keywords :
Index terms—Connection between the state assignment problem and regular expressions, derivative approach, method for obtaining polylinear sequential circuit realizations, regular expression specifications, synchronous finite automata.; Automata; Combinational circuits; Equations; Helium; Sequential circuits; Index terms—Connection between the state assignment problem and regular expressions, derivative approach, method for obtaining polylinear sequential circuit realizations, regular expression specifications, synchronous finite automata.;
