\documentclass{article}+ −
\usepackage{../style}+ −
\usepackage{../graphics}+ −
+ −
\begin{document}+ −
+ −
\section*{Homework 4}+ −
+ −
\HEADER+ −
+ −
\begin{enumerate}+ −
+ −
\item If a regular expression $r$ does not contain any occurrence of $\varnothing$, + −
is it possible for $L(r)$ to be empty?+ −
+ −
\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 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 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+ −
+ −
\[+ −
(\varnothing \cdot (b \cdot c)) + + −
((\varnothing \cdot c) + \epsilon)+ −
\]+ −
+ −
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}+ −
(\varnothing \cdot (b \cdot c)) + + −
((\varnothing \cdot c) + \epsilon)\\+ −
(a + \varepsilon) \cdot (\varepsilon + \varepsilon)+ −
\end{array}+ −
\]+ −
+ −
\item What is the purpose of the record regular expression+ −
in the Sulzmann \& Lu algorithm?+ −
+ −
+ −
%\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}+ −
+ −
+ −
\end{document}+ −
+ −
%%% Local Variables: + −
%%% mode: latex+ −
%%% TeX-master: t+ −
%%% End: + −