31
|
1 |
\documentclass{article}
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
292
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../graphics}
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
4 |
|
31
|
5 |
\begin{document}
|
|
6 |
|
|
7 |
\section*{Homework 4}
|
|
8 |
|
347
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
31
|
11 |
\begin{enumerate}
|
34
|
12 |
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
\item If a regular expression $r$ does not contain any occurrence of $\ZERO$,
|
42
|
14 |
is it possible for $L(r)$ to be empty?
|
32
|
15 |
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
\item Define the tokens and regular expressions for a language
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
consisting of numbers, left-parenthesis $($, right-parenthesis $)$,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
identifiers and the operations $+$, $-$ and $*$. Can the following
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
strings in this language be lexed?
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
\begin{itemize}
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
\item $(a + 3) * b$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
\item $)()++ -33$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
\item $(a / 3) * 3$
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
\end{itemize}
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
In case they can, can you give the corresponding token
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
sequences.
|
264
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
32
|
30 |
\item Assume that $s^{-1}$ stands for the operation of reversing a
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
string $s$. Given the following \emph{reversing} function on regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
expressions
|
32
|
33 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
$rev(\ZERO)$ & $\dn$ & $\ZERO$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
37 |
$rev(\ONE)$ & $\dn$ & $\ONE$\\
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
$rev(c)$ & $\dn$ & $c$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
\end{center}
|
34
|
44 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
and the set
|
32
|
46 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
\end{center}
|
31
|
50 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
prove whether
|
32
|
52 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
$L(rev(r)) = Rev (L(r))$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\end{center}
|
31
|
56 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
holds.
|
42
|
58 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
\item Assume the delimiters for comments are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
\texttt{$\slash$*} and \texttt{*$\slash$}. Give a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
regular expression that can recognise comments of the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
form
|
42
|
63 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
\texttt{$\slash$*~\ldots{}~*$\slash$}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
\end{center}
|
42
|
67 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
where the three dots stand for arbitrary characters, but
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
not comment delimiters. (Hint: You can assume you are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
already given a regular expression written \texttt{ALL},
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
that can recognise any character, and a regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
expression \texttt{NOT} that recognises the complement
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
of a regular expression.)
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
\item Simplify the regular expression
|
42
|
76 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
\[
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
(\ZERO \cdot (b \cdot c)) +
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
((\ZERO \cdot c) + \ONE)
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
Does simplification always preserve the meaning of a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
regular expression?
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
\item The Sulzmann \& Lu algorithm contains the function
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
$mkeps$ which answers how a regular expression can match
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
the empty string. What is the answer of $mkeps$ for the
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
regular expressions:
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
91 |
\begin{array}{l}
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
(\ZERO \cdot (b \cdot c)) +
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
((\ZERO \cdot c) + \ONE)\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
(a + \ONE) \cdot (\ONE + \ONE)
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
\end{array}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\item What is the purpose of the record regular expression in
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
the Sulzmann \& Lu algorithm?
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
100 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
|
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
%\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
%argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
%that it filters out all comments and whitespace from the result.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
%\item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
%implements the \texttt{findAll} function. This function takes a regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
%expressions and a string, and returns all substrings in this string that
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
%match the regular expression.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
\item \POSTSCRIPT
|
31
|
112 |
\end{enumerate}
|
|
113 |
|
|
114 |
|
|
115 |
\end{document}
|
|
116 |
|
|
117 |
%%% Local Variables:
|
|
118 |
%%% mode: latex
|
|
119 |
%%% TeX-master: t
|
|
120 |
%%% End:
|