A Procedure for Checking Equality of Regular Expressions

ABSTRACT

A simple “mechanical” procedure is described for checking equality of regular expressions. The procedure, based on the work of A. Salomaa, uses derivatives of regular expressions and transition graphs. Given a regular expression R, a corresponding transition graph is constructed. It is used to generate a finite set of left-linear equations which characterize R. Two regular events R and S are equal if and only if each constant term in the set of left-linear equations formed for the pair (R S) is (&phgr; &phgr;) or (^ ^). The procedure does not involve any computations with or transformations of regular expressions and is especially appropriate for the use of a computer.

REFERENCES

• 1: AANDERAA, S. On the algebra of regular expressions. Appl. Math., Harvard U., Cambridge, Mass., Jan. 1965, pp: 1-18 (ditto).
• 2: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• 3: HARRISON, M. A. Introduction to Switching and Automata Theory. McGraw-Hill, New York, 1965.
• 4: McNAUGHTON, R. Techniques for manipulating regular expressions. Machines Structures Grop Memo No. 10, MIT Project MAC, Cambridge, Mass., Nov. 1965.
• 5: McNAuGTON, R., AND YAMADA, H. Regular expressions and state graphs for automata. Trans. IRE EC-9 (1960), 39-47.
• 6: Arto Salomaa, Two Complete Axiom Systems for the Algebra of Regular Events, Journal of the ACM (JACM), v.13 n.1, p.158-169, Jan. 1966 [doi>10.1145/321312.321326]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies

General Terms:
Measurement, Performance, Theory