Editing Regular expression (section)

===Deciding equivalence of regular expressions===
As seen in many of the examples above, there is more than one way to construct a regular expression to achieve the same results.

It is possible to write an [[algorithm]] that, for two given regular expressions, decides whether the described languages are equal; the algorithm reduces each expression to a [[minimal deterministic finite state machine]], and determines whether they are [[isomorphism|isomorphic]] (equivalent).

Algebraic laws for regular expressions can be obtained using a method by Gischer which is best explained along an example: In order to check whether (''X''+''Y'')<sup>&lowast;</sup> and (''X''<sup>&lowast;</sup> ''Y''<sup>&lowast;</sup>)<sup>&lowast;</sup> denote the same regular language, for all regular expressions ''X'', ''Y'', it is necessary and sufficient to check whether the particular regular expressions (''a''+''b'')<sup>&lowast;</sup> and (''a''<sup>&lowast;</sup> ''b''<sup>&lowast;</sup>)<sup>&lowast;</sup> denote the same language over the alphabet Σ={''a'',''b''}. More generally, an equation ''E''=''F'' between regular-expression terms with variables holds if, and only if, its instantiation with different variables replaced by different symbol constants holds.<ref>{{cite report |last=Gischer |first=Jay L. |institution=Stanford Univ., Dept. of Comp. Sc. |title=(Title unknown) |type=Technical Report |number=STAN-CS-TR-84-1033 |date=1984}}{{Title missing|date=February 2023}}</ref><ref>{{cite book |isbn=978-0-201-44124-6 |last1=Hopcroft |first1=John E. |last2=Motwani |first2=Rajeev |last3=Ullman |first3=Jeffrey D. |name-list-style=amp |title=Introduction to Automata Theory, Languages, and Computation |location=Upper Saddle River, New Jersey |publisher=Addison Wesley |date=2003 |pages=117–120 |quote=This property need not hold for extended regular expressions, even if they describe no larger class than regular languages; cf. p.121.}}</ref>

Every regular expression can be written solely in terms of the [[Kleene star]] and [[union (set theory)|set unions]] over finite words. This is a surprisingly difficult problem. As simple as the regular expressions are, there is no method to systematically rewrite them to some normal form. The lack of axiom in the past led to the [[star height problem]]. In 1991, [[Dexter Kozen]] axiomatized regular expressions as a [[Kleene algebra#History|Kleene algebra]], using equational and [[Horn clause]] axioms.<ref>{{harvtxt|Kozen|1991}}{{page needed|date=February 2015}}</ref>
Already in 1964, Redko had proved that no finite set of purely equational axioms can characterize the algebra of regular languages.<ref>{{cite journal |last=Redko |first=V.N. |url=http://umj.imath.kiev.ua/article/?article=10002 |title=On defining relations for the algebra of regular events |journal=Ukrainskii Matematicheskii Zhurnal |date=1964 |volume=16 |number=1 |pages=120–126 |access-date=2018-03-28 |archive-date=2018-03-29 |archive-url=https://web.archive.org/web/20180329121016/http://umj.imath.kiev.ua/article/?article=10002 |url-status=live |language=Russian}}</ref>