# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1350747879 -3600
# Node ID 5529cfb2a81e3700825b41f33962c31c9a60ad7e
# Parent  3a0489b8399063b4594a3b276940d9cb9d84617f
tuned

diff -r 3a0489b83990 -r 5529cfb2a81e hw04.pdf
Binary file hw04.pdf has changed
diff -r 3a0489b83990 -r 5529cfb2a81e hw04.tex
--- a/hw04.tex	Wed Oct 17 23:22:43 2012 +0100
+++ b/hw04.tex	Sat Oct 20 16:44:39 2012 +0100
@@ -13,9 +13,10 @@
 \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 Give an automaton that can recognise the language 
-$L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$.
+\item If a regular expression $r$ does not contain any occurrence of $\varnothing$ 
+is it possible for $L(r)$ to be empty?
 
 \item Assume that $s^{-1}$ stands for the operation of reversing a
 string $s$. Given the following \emph{reversing} function on regular 
@@ -47,7 +48,38 @@
 
 holds.
 
-\item Palindromes
+\item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings 
+that do not contain any substring $bb$ and end in $a$.
+
+\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}
+
+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.)
+
+\item Geven the alphabet $\{a,b\}$. Draw the automaton that has two states, say  $q_0$ and $q_1$.
+The starting state is $q_0$ and the final state is $q_1$. The transition
+function is given by
+
+\begin{center}
+\begin{tabular}{l}
+$(q_0, a) \rightarrow q_0$\\
+$(q_0, b) \rightarrow q_1$\\
+$(q_1, b) \rightarrow q_1$
+\end{tabular}
+\end{center}
+
+What is the languages recognised by this automaton?
+
+\item Give a deterministic finite automaton that can recognise 
+the language $L(a^*\cdot b\cdot b^*)$. 
+
 
 \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 
@@ -59,7 +91,17 @@
 match the regular expression.
 \end{enumerate}
 
-
+% explain what is a context-free grammar and the language it generates 
+%
+% What does it mean for two regular expressions to be equivalent.
+%
+% Define the language L(M) accepted by a deterministic finite automaton M.
+%
+% Draw a parse tree for....
+%
+% does (a + b)*b+ and (a*b+) + (b*b+) define the same language
+%
+% What does it mean for a grammar to be ambiguous
 
 \end{document}