Accession Number:

AD0668672

Title:

ON THE EQUIVALENCE OF REGULAR EXPRESSIONS,

Descriptive Note:

Corporate Author:

ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s):

Report Date:

1968-04-01

Pagination or Media Count:

31.0

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

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE