631
|
1 |
% !TEX program = xelatex
|
0
|
2 |
\documentclass{article}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../style}
|
0
|
4 |
|
876
|
5 |
\newcommand{\solution}[1]{%
|
|
6 |
\begin{quote}\sf%
|
|
7 |
#1%
|
|
8 |
\end{quote}}
|
|
9 |
|
0
|
10 |
\begin{document}
|
|
11 |
|
|
12 |
\section*{Homework 1}
|
|
13 |
|
331
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
|
0
|
16 |
\begin{enumerate}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
\item {\bf (Optional)} If you want to run the code presented
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
in the lectures, install the Scala programming language
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
available (for free) from
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
|
743
|
22 |
\begin{center}
|
|
23 |
\url{http://www.scala-lang.org}
|
|
24 |
\end{center}
|
|
25 |
|
|
26 |
and the Ammonite REPL from
|
|
27 |
|
|
28 |
\begin{center}
|
|
29 |
\url{https://ammonite.io}
|
|
30 |
\end{center}
|
0
|
31 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
If you want to follow the code I present during the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
lectures, read the handout about Scala.
|
0
|
34 |
|
639
|
35 |
%\item {\bf (Optional)} Have a look at the crawler programs.
|
|
36 |
% Can you find a usage for them in your daily programming
|
|
37 |
% life? Can you improve them? For example in cases there
|
|
38 |
% are links that appear on different recursion levels, the
|
|
39 |
% crawlers visit such web-pages several times. Can this be
|
|
40 |
% avoided? Also, the crawlers flag as problematic any page
|
|
41 |
% that gives an error, but probably only 404 Not Found
|
|
42 |
% errors should be flagged. Can you change that?)
|
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
|
640
|
44 |
\item {\bf (Optional)} Have a look at the catastrophic backtracking
|
|
45 |
programs uploaded on KEATS. Convince yourself that they really require
|
|
46 |
a lot of computation time. If you have similar examples in your own
|
|
47 |
favourite programming language, I am happy to hear about it.
|
|
48 |
|
|
49 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
\item Read the handout of the first lecture and the handout
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
about notation. Make sure you understand the concepts of
|
498
|
52 |
strings and languages. In the context of the CFL-course,
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
what is meant by the term \emph{language}?
|
9
|
54 |
|
876
|
55 |
\solution{A language - in this context - is just a set of
|
|
56 |
strings. Some of these sets can actually not be described by
|
|
57 |
regular expressions. Only regular​ languages can. This is
|
|
58 |
something for lecture 3.}
|
|
59 |
|
550
|
60 |
\item Give the definition for regular expressions---this is an
|
498
|
61 |
inductive datatype. What is the
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
meaning of a regular expression? (Hint: The meaning is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
defined recursively.)
|
0
|
64 |
|
876
|
65 |
\solution{Here I would also expect the grammar for basic regular
|
|
66 |
expressions and the definition of the recursive L-function. Discuss
|
|
67 |
differences between $r_1 + r_2$ and $r^+$. Discuss differences between
|
|
68 |
``real-life regexes'' and regexes in this module.}
|
|
69 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
\item Assume the concatenation operation of two strings is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
written as $s_1 @ s_2$. Define the operation of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\emph{concatenating} two sets of strings. This operation
|
394
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
is also written as $\_ \,@\, \_$. According to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
74 |
this definition, what is $A \,@\, \{\}$ equal to?
|
498
|
75 |
Is in general $A\,@\,B$ equal to $B\,@\,A$?
|
0
|
76 |
|
876
|
77 |
\solution{ What is $A @ {[]}$? Are there special cases
|
|
78 |
where $A @ B = B @ A$? }
|
|
79 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
\item Assume a set $A$ contains 4 strings and a set $B$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
contains 7 strings. None of the strings is the empty
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
string. How many strings are in $A \,@\, B$?
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
|
876
|
84 |
\solution{28, but there are corner cases where there are fewer
|
|
85 |
than 28 elements. Can students think of such corner cases?
|
|
86 |
For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ }
|
|
87 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
\item How is the power of a language defined? (Hint: There are two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
89 |
rules, one for $\_^0$ and one for $\_^{n+1}$.)
|
109
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
90 |
|
876
|
91 |
\solution{Two rules: 0-case and n+1 case.}
|
|
92 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
\item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
|
438
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
are in $A^4$? (2) Consider also the case of $A^4$ where one of
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
the strings in $A$ is the empty string, for example $A =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
\{[a], [b], [c], []\}$.
|
293
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
|
876
|
98 |
\solution{121 is correct. But make sure you understand why it is 121
|
|
99 |
in cases you do not have a computer at your fingertips.}
|
|
100 |
|
507
|
101 |
\item (1) How many basic regular expressions are there to match
|
776
|
102 |
\textbf{only} the string $abcd$? (2) How many if they cannot include
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
$\ONE$ and $\ZERO$? (3) How many if they are also not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
allowed to contain stars? (4) How many if they are also
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
not allowed to contain $\_ + \_$?
|
0
|
106 |
|
876
|
107 |
\solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.}
|
|
108 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
\item When are two regular expressions equivalent? Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
think of instances where two regular expressions match
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
the same strings, but it is not so obvious that they do?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
For example $a + b$ and $b + a$ do not count\ldots they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
obviously match the same strings, namely $[a]$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
$[b]$.
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
|
876
|
116 |
\solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$.
|
|
117 |
Can students think about why this is the case?}
|
|
118 |
|
416
|
119 |
\item What is meant by the notions \emph{evil regular expressions}
|
726
|
120 |
and by \emph{catastrophic backtracking}?
|
|
121 |
|
876
|
122 |
\solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$}
|
|
123 |
|
726
|
124 |
\item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,
|
841
|
125 |
which of the following regular expressions are equivalent
|
726
|
126 |
|
|
127 |
\begin{center}
|
|
128 |
\begin{tabular}{ll}
|
|
129 |
1) & $(ab + bb)^* \cdot (a + b)^*$\\ % no
|
|
130 |
2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\ % yes
|
|
131 |
3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$ % no
|
|
132 |
\end{tabular}
|
|
133 |
\end{center}
|
876
|
134 |
|
|
135 |
\solution{no, yes (why?), no.}
|
726
|
136 |
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
137 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
138 |
\item \POSTSCRIPT
|
0
|
139 |
\end{enumerate}
|
|
140 |
|
|
141 |
\end{document}
|
|
142 |
|
|
143 |
%%% Local Variables:
|
|
144 |
%%% mode: latex
|
|
145 |
%%% TeX-master: t
|
|
146 |
%%% End:
|