# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1350017114 -3600
# Node ID d085fe0c086f44d11c2ff485f3571379d7c4d457
# Parent  e22ba348b209fbc5ce191514f5eff64096f7c3fd
started

diff -r e22ba348b209 -r d085fe0c086f hw04.pdf
Binary file hw04.pdf has changed
diff -r e22ba348b209 -r d085fe0c086f hw04.tex
--- a/hw04.tex	Thu Oct 11 16:52:21 2012 +0100
+++ b/hw04.tex	Fri Oct 12 05:45:14 2012 +0100
@@ -4,36 +4,35 @@
 \usepackage{amssymb}
 \usepackage{amsmath}
 
+\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+
 \begin{document}
 
 \section*{Homework 4}
 
 \begin{enumerate}
-\item Assume you have an alphabet consisting of the letters $a$, $b$ and $c$ only.
-(a) Find a regular expression that recognises the two strings $ab$ and $ac$. (b)
-Find a regular expression that matches all strings \emph{except} these two strings.
-Note, you can only use regular expressions of the form 
+\item Give an automaton that can recognise the language 
+$L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$.
+
+\item Assume that $s^{-1}$ stands for the operation of reversing a
+string $s$. Given the following \emph{reversing} function on regular 
+expressions
+
+and the set
+
 \begin{center}
-$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$
+$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
 \end{center}
 
-\item Define the function $zeroable$ which takes a regular expression as argument
-and returns a boolean.\footnote{In an earlier version there was an error.} The 
-function should satisfy the following property:
+prove that
+
 \begin{center}
-$zeroable(r)$ \;if and only if\; $L(r) = \varnothing$
+$L(rev(r)) = Rev (L(r))$
 \end{center}
 
-\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?
+holds.
 
-\begin{itemize}
-\item \texttt{"}$(a + 3) * b$\texttt{"}
-\item \texttt{"}$)()++ -33$\texttt{"}
-\item \texttt{"}$(a / 3) * 3$\texttt{"}
-\end{itemize}
+\item Palindromes
 
 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so