patternMajor
Proving Equivalence of Two Regular Expressions
Viewed 0 times
provingregularexpressionstwoequivalence
Problem
Consider the regular expressions
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?
- $(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?
Solution
One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions:
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).
- 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).
Context
StackExchange Computer Science Q#150895, answer score: 31
Revisions (0)
No revisions yet.