THE COMPILATION OF REGULAR EXPRESSIONS INTO INTEGRATED CIRCUITS Extended Abstract
Robert W. Floyd, Jeffrey David Ullman · Foundations of Computer Science · 1980
We consider the design of integrated circuits to imple ment arbitrary regular expressions. In general, we may use the McNaughton-Yamada algorithm to convert a regular e~pression of length n into a nondeterminis tic finite automaton with at most 2n states and 4n transitions. Instead of converting the nondeterminis tic device to a deterministic one, we propose two ways of implementing the nondeterministic device direct,ly. First, we could produce a PLA (programmable logic ar ray) of approximate dimensions 4n X 4n by representing the states directly by columns, rather than coding the states in binary. This approach, while theoretically suboptimal, makes use of carefully developed technol ogy and, because of the care with which PLA implemen tation has been done, may be the preferred technique in many real situations. Another approach is to use the hierarchical structure of the automaton produced from the regular expression to guide a hierarchical layout of the circuit. This method produces a circuit O(v;i) on a side and is, to within a constant factor, the best that can be done in general.