On the Equivalence of Regular Expressions
John P. Hayes · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1968
An alternate method has been suggested by Brzozowski [2 ] which involves the direct computation of a sufficient set of deri vatives of R 0 S.Such computation becomes very unwieldy when even moderately long regular expressions are being considered.Also it is necessary to repeatedly compare each new derivative to all pre ceding ones to determine when the procedure may be halted.This approach has the advantage however that it is directly applicable to extended regular expressions.In this paper, a relatively simple checking procedure involving only the generation and manipulation of regular equations, is described.It is applicable to extended regular expressions and is suitable for checking the equivalence of very long expressions.Due to its algebraic nature, the method is very suited to computer implementation.A modification of this algorithm involving minimization of the derivative equations of the given regular expressions is also described.This is of interest as it leads to a canonical form for equivalent expressions.II.OUTLINE OF THE CHECKING PROCEDURE Suppose two regular expressions R and S are to be checked for equivalence.There are three main steps in the procedures 1.Generation of sets of "transition equations" (called T-equations) from both R and S.