\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 astring $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 commentsof 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 recognisesthe 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 transitionfunction 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 asargument 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 itimplements the \texttt{findAll} function. This function takes a regularexpressions 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: