
diff -r 48b842c997c7 -r 9e42ccbbd1e6 handouts/ho02.tex
--- a/handouts/ho02.tex	Wed Mar 15 14:34:10 2017 +0000
+++ b/handouts/ho02.tex	Wed Mar 22 14:10:01 2017 +0000
@@ -3,8 +3,7 @@
 \usepackage{../langs}
 \usepackage{../graphics}
 \usepackage{../data}
-\usepackage{lstlinebgrd}
-\definecolor{capri}{rgb}{0.0, 0.75, 1.0}
+
 
 \begin{document}
 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
@@ -265,6 +264,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




