A Program to Take the Derivative of Regular Expressions
OHIO UNIV ATHENS DEPT OF ELECTRICAL ENGINEERING
Pagination or Media Count:
In analyzing a finite state, sequential machine the designer will often use a flowgraph or flow-chart to describe the internal characteristics of the machine. From these characteristics he can obtain a model representing the external performance of the machine. By the external performance of the machine the author is referring to the input, output characteristics i.e., for a given set of input signals what is the output. For simplicity the author considers machines with two outputs, a 1 or a 0. Thus, the inputs may be divided into two classes, those which produce a 1 output accepted or desired inputs and the remainder which produce a 0 output the rejected inputs. The regular expression provides a formal method for representing all of the possible inputs which are accepted. While the regular expression is a powerful tool its use has been limited by the overwhelming amount of work needed to obtain the sequential machine. The paper describes a program which was written to find the derivatives of the regular expression.
- Computer Programming and Software