Regular expressions can be extended by adding gotos and Boolean variables. Although such extensions do not increase the class of expressible languages, they do permit shorter expressions for some languages. The output space complexity of eliminating Boolean variables is shown to be double exponential. The complexity of eliminating a single goto from a regular expression is shown to be \( \Omega (n \log n) \), a surprising result considering that $n$ gotos can be eliminated in single exponential space.
If you have any questions or comments regarding this page please send mail to firstname.lastname@example.org.