Regular expression

The solutions of linear symbolic equations are regular expressions, which represent sets. In other words regular expressions furnish a concise description of the paths through a diagram rather than the diagram itself. Comparisons between regular expressions therefore translate into comparisons between the sets which they represent, and conversely. As a result, boolean operations such as intersection and complementation are possible on regular expressions; union already forms part of the algebra of regular sets.

Likewise, due to the distributive and associative laws, it is possible for diverse regular expressions to represent the same set, creating the problem of recognizing the equality of two different regular expressions.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx