Vol 11, No. 4 (October, 1964), pp. 481–494 | Janusz A. Brzozowski
The paper introduces the concept of derivatives of regular expressions, which are used to simplify the description of sequential circuits. The authors define a set of operations on sequences and regular expressions, including union, concatenation, iteration, and Boolean functions. They introduce the notion of a derivative of a regular expression with respect to a sequence, which helps in constructing state diagrams for these expressions. The properties of derivatives are discussed, and algorithms are provided to find derivatives and solve characteristic equations. The paper also presents methods for constructing state diagrams for both Moore and Mealy machines from regular expressions, and extends these methods to multiple-output circuits. The results are illustrated with examples and theoretical proofs, demonstrating the effectiveness of the derivative approach in handling regular expressions with arbitrary logical connectives.The paper introduces the concept of derivatives of regular expressions, which are used to simplify the description of sequential circuits. The authors define a set of operations on sequences and regular expressions, including union, concatenation, iteration, and Boolean functions. They introduce the notion of a derivative of a regular expression with respect to a sequence, which helps in constructing state diagrams for these expressions. The properties of derivatives are discussed, and algorithms are provided to find derivatives and solve characteristic equations. The paper also presents methods for constructing state diagrams for both Moore and Mealy machines from regular expressions, and extends these methods to multiple-output circuits. The results are illustrated with examples and theoretical proofs, demonstrating the effectiveness of the derivative approach in handling regular expressions with arbitrary logical connectives.