# Proving that all equivalent regular expressions are reachable via algebraic laws

Given a set of laws for regular expressions, for example (ripped from this document):

$$\begin{array}{llll} \text{1.} & (A|B)|C = A|(B|C) &\qquad& \text{(associativity of choice)}\\ \text{2.} & (AB)C = A(BC) && \text{(associativity of sequence)}\\ \text{3.} & A|B = B|A && \text{(commutativity of choice)}\\ \text{4.} & \phi|A = A|\phi = A && \text{(choice with empty language)}\\ \text{5.} & \epsilon A = A\epsilon = A && \text{(sequence with empty string)}\\ \text{6.} & \phi A = A \phi = \phi && \text{(sequence with empty language)}\\ \text{7.} & A(B|C) = AB|AC && \text{(left distributivity)}\\ \text{8.} & (A|B)C = AC|BC && \text{(right distributivity)}\\ \text{9.} & A|A = A && \text{(idempotency of choice)}\\ \text{10.} & (A^*)^* = A^* && \text{(repeated closure)}\\ \text{11.} & \phi^* = \epsilon && \text{(closure of empty language)}\\ \text{12.} & \epsilon^* = \epsilon && \text{(closure of empty string)}\\ \end{array}$$

Now, given any two regular expressions $A$ and $B$ which are equivalent (recognize precisely the same language), is there always a way to rewrite $A$ to $B$ by repeatedly applying these laws as rewriting rules? How would one approach proving that there are no equivalent regular expressions not reachable by rewriting from each other using these laws?

EDIT: As JiK points out, we also need at least $A(A^*) = (A^*)A$, and there might be other necessary rules missing. I guess this just demonstrates why a way to prove reachability between equivalent expressions seems necessary.

• How about $A(A*)$ and $(A*)A$? where $A$ is a symbol? It seems to me that law 10 is the only one applicable to these, and you get nowhere with it.
– JiK
Commented Sep 8, 2015 at 9:07

This has been an open problem for some years until a negative answer was given independently by Redko [4] and Conway [1, pp. 105-118]): every complete system of identities for the regular expressions is necessarily infinite. Conway [1, pp. 116-119] conjectured a "good" complete system and this conjecture was ultimately proved by Krob [2, 3]. Interestingly, this system involves identities attached to finite groups.

On the positive side, Salomaa [5] proved that there exists a complete system composed of two identities and of an axiom scheme (which permits essentially to formally solve linear systems).

[1] J.H. Conway, Regular Algebras and Finite Machines (Chapman & Hall, London, 1974).

[2] D.Krob, A complete system of ${\scr B}$-rational identities. Automata, languages and programming (Coventry, 1990), 60--73, Lecture Notes in Comput. Sci., 443, Springer, New York, 1990.

[3] D.Krob, Complete systems of ${\scr B}$-rational identities. Theoret. Comput. Sci. 89 (1991), no. 2, 207--343.

[4] V.N. Redko, On the determining totality of an algebra of regular events, Ukrain. Mat. Z. 16 (1964), 120-126 (in Russian).

[5] A. Salomaa, Two complete axiom systems for the algebra of regular events. J. Assoc. Comput. Mach. 13 (1966), 158--169.

• Just a side note: Redko's article is sometimes also referred to as On defining relations for the algebra of regular events in the literature. Commented Apr 29, 2020 at 11:31
• @StefanH I just reproduced the reference of the Math Reviews. Commented Apr 29, 2020 at 11:35
• Yes, maybe then it should be referred to that way. I just wanted to note that I have seen both variants. Commented Apr 29, 2020 at 11:43

Quick answer: yes ... but not quite in the way you're thinking; and this we've known since the 1990's (A Complete Axiomatization). First, let's audit the structure laid out.

2 & 5 - monoid with $$a, b ↦ ab$$ as the operation and $$ε$$ as the identity

1 & 4 - monoid, with $$a, b ↦ a|b$$ as the operation and $$∅$$ as the identity, and ...

3 - ... it's also an Abelian (or commutative) monoid, and ...

9 - ... it's also idempotent, which makes it an Upper Semi-Lattice with respect to the partial ordering relation given innately by $$b ≤ a$$ iff $$a ≥ b$$ iff $$(∃c)a = c | b$$ iff $$a = a | b$$, relative to which $$a, b ↦ a|b$$ is the least upper bound operator and $$∅$$ is the minimum element. With respect to this ordering relation, the operation $$a,b ↦ a|b$$ is order-preserving

6, 7, 8 - or more generally $$a(⋁B)c = ⋁\{abc: b∈B\}$$, for finite sets $$B$$ (i.e. finite distributivity) makes this a semiring, if ignoring property 9, and an idempotent semi-ring (a.k.a. a Dioid), if including property 9. As a consequence, also, the operation $$a, b ↦ ab$$ is order-preserving.

10, 11, 12 - you're thinking too narrowly. In general one uses $$μx·f(x)$$ to denote least fixed point solution to $$x ≥ f(x)$$. It is also (therefore) a solution to the corresponding equation $$x = f(x)$$, if $$f(x)$$ ranges over all the semi-ring operations. One may pose the following $$μx·(a | b x | x c | x d x) = (b^* a c^* d)^* b^* a c^*$$ in place of 10 and 12 and keep 11 ... or you could just go $$μx·(a | b x | x c) = b^* a c^*$$ along with 11, or you could just do this: $$μx·(a | b x) = b^* a$$ and $$μx·(a | x c) = a c^*$$ in place of 10, 11 and 12, or you could just as well do this: $$a ≥ b a → a ≥ b^* a$$ and $$a ≥ a c → a ≥ a c^*$$ in place of 10, 11 and 12, provided that you also add $$a^* ≥ ε | a a^*$$ or $$a^* ≥ ε | a^* a$$ or you might even get away with $$a^* ≥ ε | a^* a a^*$$. In all cases, it's a complete axiomatization for Kleene Algebra and they're all equivalent.

In all cases, the operation $$a ↦ a^*$$ is order-preserving and has your properties 10, 11 and 12 as consequences.

It is complete in the sense that the algebra freely generated from a set $$X$$, subject to these operations and axioms is one and the same, up to isomorphism, as the Kleene algebra of regular expressions over an alphabet $$X$$. For the free Kleene algebra (and generally speaking, only for it), one also has star-completeness: $$⋁_{n≥0}(a^n) = a^*$$ as an emergent property (where $$a^0 = ε$$ and $$a^{n+1} = a a^n$$, for $$n ≥ 0$$), and star-continuity (or better-named: star-distributivity): $$a \left(⋁_{n≥0} b^n\right) c = ⋁_{n≥0} \left(a b^n c\right).$$

Conway, in the 1960's or 1970's, proved there is no finite equational axiomatization. That was a case of Conway pulling a Minsky and dropping the ball (which was also like when von Neumann did his "no hidden variables" fumble that Bohm picked up and ran into the other end zone). It's not the only time Conway stumbled - his game of Life was only monochromatic and totally flubbed by missing the even more interesting game of Life In Color.

To get the more powerful result that Kleene algebras should possess an adjunction with respect to the category of monoids; i.e. that every monoid (in the sense of 2 and 5) can be extended freely to a Kleene algebra, such that its rational subsets comprise that algebra: that absolutely requires infinitary axioms of some sort or another, because you can encode Turing machines in Kleene algebras(!) Star-continuity and star-completeness fit the bill on all accounts.

You can go further. Instead of just star-completeness and star-continuity, do μ-completeness ($$μx·f(x)$$ is defined for all Kleene functions $$f(x)$$!) and μ-continuity: $$⋁_{n≥0} \left(a f^n(0) b\right) = a (μx·f(x)) b,$$ for all Kleene functions $$f(x)$$. By Kleene function, I refer to the class of functions formed using variables (here: just $$x$$), the constants $$ε$$ and $$∅$$ and the operations $$a, b ↦ ab$$, $$a, b ↦ a|b$$ and $$a ↦ a^*$$. You can get multivariate systems after noting that the free extension $$K[X]$$ of a Kleene algebra $$K$$ by a set $$X$$ of indeterminates is a Kleene algebra, such that $$K[X][Y] = K[X ∪ Y]$$, up to isomorphism, where $$X ∩ Y = ∅$$. This algebra is a μ-continuous Chomsky Algebra, and has - as its free algebra generated by a set $$X$$ - the context-free subsets of $$X^*$$, i.e. the context-free languages over the alphabet $$X$$ ... and also has - as the free extension of a monoid $$M$$ - the family of context-free subsets of $$M$$. If you're not familiar with how to define context-free subsets of a general monoid, here are Two Equivalent Ways to do it.

A proof of 12: $$ε^* = ε | ε ε^* ≥ ε$$. That's half the result. From $$ε ≥ ε | ε ε$$, it follows that $$ε$$ is a solution to $$x ≥ ε | ε x$$, the minimal solution which is $$ε^* = ε^* ε = μx·(ε | ε x)$$. Therefore, $$ε ≥ ε^*$$. A proof of 10 is more lengthy, and may be facilitated by the lemma $$x^* x^* = x^*$$, which will also have to be proven. You can try finding them for yourself.