# 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

# Descriptors:

# Subject Categories:

- Theoretical Mathematics
- Operations Research