Dado un conjunto de leyes para expresiones regulares, por ejemplo (rasgado de este documento):
$$ \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}$$
Ahora bien, dado que cualquiera de los dos expresiones regulares $A$ $B$ cuales son equivalentes (reconocer precisamente el mismo idioma), hay siempre una manera de reescribir $A$ $B$por varias ocasiones la aplicación de estas leyes, como reglas de reescritura? ¿Cómo sería un enfoque demostrando que no hay ningún equivalente expresiones regulares no se puede llegar por la reescritura de cada una usando estas leyes?
EDIT: Como JiK señala, también necesitamos al menos $A(A^*) = (A^*)A$, y podría haber otras reglas necesarias que faltan. Supongo que esto sólo demuestra por qué una forma de demostrar la accesibilidad entre expresiones equivalentes parece necesario.
