1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 

     7 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

     8 

     9 \begin{document}

    10 

    11 \section*{Homework 4}

    12 

    13 \begin{enumerate}

    14 \item Why is every finite set of strings a regular language?

    15 

    16 \item What is the language recognised by the regular expressions $(\varnothing^*)^*$.

    17 

    18 \item If a regular expression $r$ does not contain any occurrence of $\varnothing$ 

    19 is it possible for $L(r)$ to be empty?

    20 

    21 \item Assume that $s^{-1}$ stands for the operation of reversing a

    22 string $s$. Given the following \emph{reversing} function on regular 

    23 expressions

    24 

    25 \begin{center}

    26 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}

    27 $rev(\varnothing)$   & $\dn$ & $\varnothing$\\

    28 $rev(\epsilon)$         & $\dn$ & $\epsilon$\\

    29 $rev(c)$                      & $\dn$ & $c$\\

    30 $rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\

    31 $rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\

    32 $rev(r^*)$                   & $\dn$ & $rev(r)^*$\\

    33 \end{tabular}

    34 \end{center}

    35 

    36 

    37 and the set

    38 

    39 \begin{center}

    40 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$

    41 \end{center}

    42 

    43 prove whether

    44 

    45 \begin{center}

    46 $L(rev(r)) = Rev (L(r))$

    47 \end{center}

    48 

    49 holds.

    50 

    51 \item Give a regular expression over the alphabet $\{a,b\}$ recognising all strings 

    52 that do not contain any substring $bb$ and end in $a$.

    53 

    54 \item Assume the delimiters for comments are \texttt{$\slash$*} and \texttt{*$\slash$}.

    55 Give a regular expression that can recognise comments

    56 of the form 

    57 

    58 \begin{center}

    59 \texttt{$\slash$*~\ldots{}~*$\slash$} 

    60 \end{center}

    61 

    62 where the three dots stand for arbitrary characters, but not comment delimiters.

    63 (Hint: You can assume you are already given a regular expression written \texttt{ALL},

    64 that can recognise any character, and a regular expression \texttt{NOT} that recognises

    65 the complement of a regular expression.)

    66 

    67 \item Given the alphabet $\{a,b\}$. Draw the automaton that has two states, say  $q_0$ and $q_1$.

    68 The starting state is $q_0$ and the final state is $q_1$. The transition

    69 function is given by

    70 

    71 \begin{center}

    72 \begin{tabular}{l}

    73 $(q_0, a) \rightarrow q_0$\\

    74 $(q_0, b) \rightarrow q_1$\\

    75 $(q_1, b) \rightarrow q_1$

    76 \end{tabular}

    77 \end{center}

    78 

    79 What is the languages recognised by this automaton?

    80 

    81 \item Give a deterministic finite automaton that can recognise 

    82 the language $L(a^*\cdot b\cdot b^*)$. 

    83 

    84 

    85 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as

    86 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so 

    87 that it filters out all comments and whitespace from the result.

    88 

    89 \item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it

    90 implements the \texttt{findAll} function. This function takes a regular

    91 expressions and a string, and returns all substrings in this string that 

    92 match the regular expression.

    93 \end{enumerate}

    94 

    95 % explain what is a context-free grammar and the language it generates 

    96 %

    97 %

    98 % Define the language L(M) accepted by a deterministic finite automaton M.

    99 %

   100 %

   101 % does (a + b)*b+ and (a*b+) + (b*b+) define the same language

   102 

   103 

   104 \end{document}

   105 

   106 %%% Local Variables: 

   107 %%% mode: latex

   108 %%% TeX-master: t

   109 %%% End: