
diff -r dfa7b4ca199f -r 4fcaa5a2d199 handouts/ho02.tex
--- a/handouts/ho02.tex	Wed Mar 15 14:34:10 2017 +0000
+++ b/handouts/ho02.tex	Fri Mar 17 12:15:58 2017 +0000
@@ -265,6 +265,22 @@
 $\ZERO$s, therefore simplifying them away will make the
 algorithm quite a bit faster.
 
+Finally here are three equivalences between regulare expressions which are
+not so obvious:
+
+\begin{center}
+\begin{tabular}{rcl}
+$r^*$  & $\equiv$ & $1 + r\cdot r^*$\\
+$(r_1 + r_2)^*$  & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\
+$(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\
+\end{tabular}
+\end{center}
+
+\noindent
+You can try to establish them. As an aside, there has been a lot of research
+in questions like: Can one always decide when two regular expressions are
+equivalent or not? What does an algorithm look like to decide this?
+
 \subsection*{The Matching Algorithm}
 
 The algorithm we will define below consists of two parts. One




