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