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 (φ φ) or (^ ^). The procedure does not involve any computations with or transformations of regular expressions and is especially appropriate for the use of a computer.

For reduced finite Moore automata corresponding to regular expressions which are finite sums of expressions of the form E+HΣ*G (E, H, G are finite events and Σ is the set of inputs) it is shown that an arbitrary change of the initial state or of the set of final states results in an automaton belonging to the same class. The transition graphs corresponding to the single inputs in definite and reverse-definite automata are investigated.