Proving Equivalence of Two Regular Expressions

Question

Consider the regular expressions

• $(1+01)^*(0+\epsilon)$
• $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$,

where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. Intuitively it seems they are equivalent because they seem to generate the languages of strings without two consecutive $0s$.

a. Is this correct?
b. How it can be proved mathematically?

Answer 1

One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions:

• Show that if $w$ is generated by $r_1$ then it is generated by $r_2$.
• Show that if $w$ is generated by $r_2$ then it is generated by $r_1$.

Another way is to mechanically convert the regular expressions to NFAs, then to DFAs, then use the product construction to construct a DFA for the symmetric difference of the languages generated by the two regular expressions, then to show that no accepting state is reachable from the initial state.

You are suggesting a third way — show that both regular expressions generate a particular language $L$. You can use the methods above, or other methods, to show separately that each of $r_1,r_2$ generate the language $L$.

A fourth way is to use the algebra of regular expressions, some axiomatizations of which are complete for the equational theory of regular expressions (which means that if two regular expressions generate the same language, then this can be proved using the axioms).

Answer 2

If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's regular_expressions library

import computability.regular_expressions

open regular_expression

abbreviation c0 := char ff
abbreviation c1 := char tt

-- the statement is that the two regular expressions match the same thing
example :
  ((c1 + c0*c1).star*(c0 + 1)).matches
    = ((c1.star*c0*c1*c1.star).star + c1.star*(c0 + 1)).matches :=
begin
  simp, -- this gets you started, and turns it into a statement about languages
  sorry
end

Note here that your $0$ is c0, your $1$ is c1, your $x*$ is x.star, your $\epsilon$ is $1$, and your concatenation is *.

To complete this, you have to replace the sorry with the rest of the proof!

Answer 3

If you generate a minimal DFA from a regular expression, then you can label each state uniquely with the lexically smallest string that reaches the state.

This makes it very easy to check for isomorphism between two minimal DFAs, which determines if the languages that generated them are equivalent.

If you number the states in label order, and write out a description of the DFA based on that ordering, then the string you produce is a canonical representation of the language.

Not only can you simply compare two such strings to determine if their generating REs are equivalent, but you can also make a database of them and efficiently check to see if a new language matches any one in the database.

Answer 4

The most direct procedural way that I have found to determine whether two regular expressions $R_0$ and $R_1$ are equivalent is the following:

1. Convert $R_0$ and $R_1$ to NFAs $N_0$ and $N_1$.
2. Convert $N_0$ and $N_1$ to DFAs $D_0 = (Q_0, \Sigma, \delta_0, q_0, F_0)$ and $D_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$.
3. Form a "union" DFA $D = (Q_0 \cup Q_1, \Sigma, \delta_0 \cup \delta_1, -, F_0 \cup F_1)$. The start state doesn't matter (hence the "$-$"). The idea comes from these lecture notes by Ana Bove.
4. Test whether $q_0$ and $q_1$ are equivalent using the table-filling algorithm. Details on the table filling algorithm can be found in these lecture notes by Ryan Williams.

Answer 5

It appears it should be possible to show the regular expressions $r_1=(1+01)^*$ and $r_2=(1^* 011^*)^*+1^*$ generate the same language, by showing that each string generated by $r_1$ can also be generated by $r_2$, and conversely. This equality would be preserved when an optional $0$ is concatenated at the end.