A Program to Take the Derivative of Regular Expressions
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1972
- Accession Number
- AD0742716
Entities
People
- William Hartmann
Organizations
- Ohio University