\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}

\begin{document}

\section*{Homework 4}

\HEADER

\begin{enumerate}

\item Given the regular expressions

\begin{center}
\begin{tabular}{ll}    
  1) & $(ab + a)\cdot (\ONE + b)$\\
  2) & $(aa + a)^*$\\
\end{tabular}
\end{center}

there are several values for how these regular expressions can
recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case
\emph{all} the values and indicate which one is the POSIX value.
  

\item If a regular expression $r$ does not contain any occurrence of $\ZERO$,  
is it possible for $L(r)$ to be empty? Explain why, or give a proof.

\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?

  \begin{itemize}
  \item $(a + 3) * b$
  \item $)()++ -33$
  \item $(a / 3) * 3$
  \end{itemize}

  In case they can, can you give the corresponding token
  sequences.

\item Assume $r$ is nullable. Show that
  \[ 1 + r + r\cdot r \;\equiv\; r\cdot r
  \]

  holds.

\item \textbf{(Deleted)} 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(\ZERO)$   & $\dn$ & $\ZERO$\\
      $rev(\ONE)$         & $\dn$ & $\ONE$\\
      $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 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 Simplify the regular expression

\[
(\ZERO \cdot (b \cdot c)) + 
((\ZERO \cdot c) + \ONE)
\]

      Does simplification always preserve the meaning of a
      regular expression? 
     
\item The Sulzmann \& Lu algorithm contains the function
      $mkeps$ which answers how a regular expression can match
      the empty string. What is the answer of $mkeps$ for the
      regular expressions:    

  \[
  \begin{array}{l}
  (\ZERO \cdot (b \cdot c)) + 
  ((\ZERO \cdot c) + \ONE)\\
    (a + \ONE) \cdot (\ONE + \ONE)\\
    a^*
  \end{array}
  \]

\item What is the purpose of the record regular expression in
      the Sulzmann \& Lu algorithm?

\item Recall the functions \textit{nullable} and \textit{zeroable}.
  Define recursive functions \textit{atmostempty} (for regular expressions
  that match no string or only the empty string), \textit{somechars} (for regular
  expressions that match some non-empty string), \textit{infinitestrings} (for regular
  expressions that can match infinitely many strings). 
      
  
%\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.

\item \POSTSCRIPT  
\end{enumerate}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: