\documentclass{article}\usepackage{../style}\usepackage{../graphics}\begin{document}\section*{Homework 4}\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 How many basic regular expressions are there to match the string $abcd$? (ii) How many if they cannot include $\epsilon$ and $\varnothing$? (iii) How many if they are also not allowed to contain stars? (iv) How many if they are also not allowed to contain $\_ + \_$?%\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: