diff -r e85600529ca5 -r 4794759139ea hw/hw04.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw/hw04.tex	Sat Jun 15 09:23:18 2013 -0400
@@ -0,0 +1,109 @@
+\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: