ON THE EQUIVALENCE OF REGULAR EXPRESSIONS,
Abstract
Some existing techniques for checking the equivalence of regular expressions are examined and their shortcomings discussed. A checking procedure based on the construction of regular equations is described. First, a set of transition or T-equations is obtained from the given expressions R and S. These are then converted to derivative or D-equations. Finally, a set of D-equations corresponding to the sum of R and S is constructed. It is shown that R = S if and only if the D-equations of the sum of R and S do not contain the empty string lambda. Upper bounds are determined for the number of equations involved in each step of the procedure. Unlike previously-described methods, neither the construction of the graphs nor the computation of derivatives is required. This technique is also applicable to extended regular expressions involving any Boolean operators. A modified procedure involving minimization of the D-equations of R and S is also discussed. R = S if and only if their respective minimized D-equations are isomorphic. Finally, it is shown that these equations lead to a canonical form for equivalent expressions. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1968
- Accession Number
- AD0668672
Entities
People
- John P. Hayes
Organizations
- University of Illinois Urbana–Champaign