
diff -r 4758a6155878 -r 1ab41c59e3d3 hw/hw04.tex
--- a/hw/hw04.tex	Thu Sep 26 10:39:23 2013 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,109 +0,0 @@
-\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
-
-\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 Assume that $s^{-1}$ stands for the operation of reversing a
-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 whether
-
-\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$.
-
-\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, and a regular expression \texttt{NOT} that recognises
-the complement of a regular expression.)
-
-\item Given 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 
-that it filters out all comments and whitespace from the result.
-
-\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it
-implements the \texttt{findAll} function. This function takes a regular
-expressions and a string, and returns all substrings in this string that 
-match the regular expression.
-\end{enumerate}
-
-% explain what is a context-free grammar and the language it generates 
-%
-%
-% Define the language L(M) accepted by a deterministic finite automaton M.
-%
-%
-% does (a + b)*b+ and (a*b+) + (b*b+) define the same language
-
-
-\end{document}
-
-%%% Local Variables: 
-%%% mode: latex
-%%% TeX-master: t
-%%% End: 




