
diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw04.tex
--- a/hws/hw04.tex	Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw04.tex	Fri Oct 10 16:59:22 2014 +0100
@@ -4,81 +4,70 @@
 \usepackage{tikz}
 \usetikzlibrary{automata}
 
-
-%%\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
-
 \begin{document}
 
 \section*{Homework 4}
 
 \begin{enumerate}
-\item Why is every finite set of strings a regular language?
-
-\item What is the language recognised by the regular expressions $(\varnothing^*)^*$.
 
 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$,  
 is it possible for $L(r)$ to be empty?
 
 \item Define the tokens and regular expressions for a language
-      consisting of numbers, left-parenthesis $($,
-      right-parenthesis $)$, identifiers and the operations $+$,
-      $-$ and $*$. Can the following strings in this language
-      be lexed?
+  consisting of numbers, left-parenthesis $($, right-parenthesis $)$,
+  identifiers and the operations $+$, $-$ and $*$. Can the following
+  strings in this language be lexed?
 
-\begin{itemize}
+  \begin{itemize}
   \item $(a + 3) * b$
   \item $)()++ -33$
   \item $(a / 3) * 3$
-\end{itemize}
+  \end{itemize}
 
-In case they can, can you give the corresponding token
-sequences.
+  In case they can, can you give the corresponding token
+  sequences.
 
 \item Assume that $s^{-1}$ stands for the operation of reversing a
-string $s$. Given the following \emph{reversing} function on regular 
-expressions
+  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}
+  \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
+  and the set
 
-\begin{center}
-$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
-\end{center}
+  \begin{center}
+    $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
+  \end{center}
 
-prove whether
+  prove whether
 
-\begin{center}
-$L(rev(r)) = Rev (L(r))$
-\end{center}
+  \begin{center}
+    $L(rev(r)) = Rev (L(r))$
+  \end{center}
 
-holds.
-
-\item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings 
-that do not contain any substring $bb$ and end in $a$.
+  holds.
 
-\item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}.
-Give a regular expression that can recognise comments
-of the form 
+\item Assume the delimiters for comments are \texttt{$\slash$*} and
+  \texttt{*$\slash$}.  Give a regular expression that can recognise
+  comments of the form
 
-\begin{center}
-\texttt{$\slash$*~\ldots{}~*$\slash$} 
-\end{center}
+  \begin{center}
+    \texttt{$\slash$*~\ldots{}~*$\slash$} 
+  \end{center}
 
-where the three dots stand for arbitrary characters, but not comment delimiters.
-(Hint: You can assume you are already given a regular expression written \texttt{ALL},
-that can recognise any character, and a regular expression \texttt{NOT} that recognises
-the complement of a regular expression.)
+  where the three dots stand for arbitrary characters, but not comment delimiters.
+  (Hint: You can assume you are already given a regular expression written \texttt{ALL},
+  that can recognise any character, and a regular expression \texttt{NOT} that recognises
+  the complement of a regular expression.)
 
 
 
@@ -92,14 +81,6 @@
 %match the regular expression.
 \end{enumerate}
 
-% explain what is a context-free grammar and the language it generates 
-%
-%
-% 
-%
-%
-% does (a + b)*b+ and (a*b+) + (b*b+) define the same language
-
 
 \end{document}
 




