diff -r 92b3e287d87e -r eeff9953a1c1 hw04.tex --- a/hw04.tex Fri Oct 12 05:45:48 2012 +0100 +++ b/hw04.tex Sun Oct 14 23:41:49 2012 +0100 @@ -11,6 +11,9 @@ \section*{Homework 4} \begin{enumerate} +\item Why is every finite set of strings a regular language? + + \item Give an automaton that can recognise the language $L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$. @@ -18,13 +21,25 @@ string $s$. Given the following \emph{reversing} function on regular expressions +\begin{center} +\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} +$rev(\varnothing)$ & $\dn$ & $\varnothing$\\ +$rev(\epsilon)$ & $\dn$ & $\epsilon$\\ +$rev(c)$ & $\dn$ & $c$\\ +$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ +$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ +$rev(r^*)$ & $\dn$ & $rev(r)^*$\\ +\end{tabular} +\end{center} + + and the set \begin{center} $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ \end{center} -prove that +prove whether \begin{center} $L(rev(r)) = Rev (L(r))$