127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
1 |
\documentclass{article}
|
253
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../langs}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
4 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
5 |
\begin{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
6 |
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
7 |
\section*{Coursework 1 (Strand 1)}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
8 |
|
358
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
This coursework is worth 5\% and is due on 20 October at
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
16:00. You are asked to implement a regular expression matcher
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
and submit a document containing the answers for the questions
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
below. You can do the implementation in any programming
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
language you like, but you need to submit the source code with
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
which you answered the questions, otherwise a mark of 0\% will
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
be awarded. However, the coursework will \emph{only} be judged
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
according to the answers. You can submit your answers in a
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
17 |
txt-file or pdf.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
\subsubsection*{Disclaimer}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
22 |
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
It should be understood that the work you submit represents your own
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
effort. You have not copied from anyone else. An exception is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
Scala code I showed during the lectures, which you can use.\bigskip
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
\subsubsection*{Tasks}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
The task is to implement a regular expression matcher based on
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
derivatives. The implementation should be able to deal with the usual
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
(basic) regular expressions
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
33 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
34 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
35 |
\varnothing, \epsilon, c, r_1 + r_2, r_1 \cdot r_2, r^*
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
36 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
37 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
38 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
but also with the following extended regular expressions:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
40 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
41 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
42 |
\begin{tabular}{ll}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
43 |
$[c_1 c_2 \ldots c_n]$ & a range of characters\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
44 |
$r^+$ & one or more times $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
45 |
$r^?$ & optional $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
46 |
$r^{\{n,m\}}$ & at least $n$-times $r$ but no more than $m$-times\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
47 |
$\sim{}r$ & not-regular expression of $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
48 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
49 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
50 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
51 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
52 |
In the case of $r^{\{n,m\}}$ we have the convention that $0 \le n \le m$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
53 |
The meaning of these regular expressions is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
54 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
55 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
56 |
\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}l}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
$L([c_1 c_2 \ldots c_n])$ & $\dn$ & $\{[c_1], [c_2], \ldots, [c_n]\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
$L(r^+)$ & $\dn$ & $\bigcup_{1\le i}. L(r)^i$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
$L(r^?)$ & $\dn$ & $L(r) \cup \{[]\}$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
60 |
$L(r^{\{n,m\}})$ & $\dn$ & $\bigcup_{n\le i \le m}. L(r)^i$\\
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
$L(\sim{}r)$ & $\dn$ & $\Sigma^* - L(r)$
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
62 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
63 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
64 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
65 |
\noindent
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
whereby in the last clause the set $\Sigma^*$ stands for the set of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
\emph{all} strings over the alphabet $\Sigma$ (in the implementation the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
alphabet can be just what is represented by, say, the type \pcode{char})).
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
So $\sim{}r$ means `all the strings that $r$
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
cannot match'.
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
71 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
Be careful that your implementation of $nullable$ and $der$ satisfies
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
for every $r$ the following two properties (see also Question 2):
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
74 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
75 |
\begin{itemize}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
\item $nullable(r)$ if and only if $[]\in L(r)$
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
77 |
\item $L(der\,c\,r)) = Der\,c\,(L(r))$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
78 |
\end{itemize}
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
79 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
\noindent
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
{\bf Important!} Your implementation should have explicit cases for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
the basic regular expressions, but also explicit cases for the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
extended regular expressions. That means do not treat the extended
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
regular expressions by just translating them into the basic ones. See
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
also Question 2, where you are asked to explicitly give the rules for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
\textit{nullable} and \textit{der} for the extended regular
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
87 |
expressions.
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
88 |
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
89 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
90 |
\subsection*{Question 1 (unmarked)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
91 |
|
275
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
92 |
What is your King's email address (you will need it in Question 3)?
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
93 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
94 |
\subsection*{Question 2 (marked with 2\%)}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
95 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
96 |
This question does not require any implementation. From the lectures
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
97 |
you have seen the definitions for the functions \textit{nullable} and
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
98 |
\textit{der} for the basic regular expressions. Give the rules for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
99 |
the extended regular expressions:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
100 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
\begin{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
103 |
$nullable([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
104 |
$nullable(r^+)$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
105 |
$nullable(r^?)$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
106 |
$nullable(r^{\{n,m\}})$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
107 |
$nullable(\sim{}r)$ & $\dn$ & $?$\medskip\\
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
108 |
$der\, c\, ([c_1 c_2 \ldots c_n])$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
109 |
$der\, c\, (r^+)$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
110 |
$der\, c\, (r^?)$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
111 |
$der\, c\, (r^{\{n,m\}})$ & $\dn$ & $?$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
112 |
$der\, c\, (\sim{}r)$ & $\dn$ & $?$\\
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
113 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
114 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
115 |
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
116 |
\noindent
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
117 |
Remember your definitions have to satisfy the two properties
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
118 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
119 |
\begin{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
120 |
\item $nullable(r)$ if and only if $[]\in L(r)$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
121 |
\item $L(der\,c\,r)) = Der\,c\,(L(r))$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
122 |
\end{itemize}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
123 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
124 |
\subsection*{Question 3 (marked with 1\%)}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
125 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
126 |
Implement the following regular expression for email addresses
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
127 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
128 |
\[
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
129 |
([a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+)\cdot @\cdot ([a\mbox{-}z0\mbox{-}9\,.-]^+)\cdot .\cdot ([a\mbox{-}z\,.]^{\{2,6\}})
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
130 |
\]
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
131 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
132 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
133 |
and calculate the derivative according to your email address. When
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
134 |
calculating the derivative, simplify all regular expressions as much
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
135 |
as possible, but at least apply the following six simplification
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
136 |
rules:
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
137 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
138 |
\begin{center}
|
272
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
139 |
\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
140 |
$r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
141 |
$\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
142 |
$r \cdot \epsilon$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
143 |
$\epsilon \cdot r$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
144 |
$r + \varnothing$ & $\mapsto$ & $r$\\
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
145 |
$\varnothing + r$ & $\mapsto$ & $r$\\
|
333
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
146 |
$r + r$ & $\mapsto$ & $r$\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
147 |
\end{tabular}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
148 |
\end{center}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
149 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
150 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
151 |
Write down your simplified derivative in the ``mathematicical''
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
152 |
notation using parentheses where necessary.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
153 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
154 |
\subsection*{Question 4 (marked with 1\%)}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
155 |
|
260
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
156 |
Suppose \textit{[a-z]} stands for the range regular expression
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
157 |
$[a,b,c,\ldots,z]$. Consider the regular expression $/ \cdot * \cdot
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
158 |
(\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot *
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
159 |
\cdot /$ and decide wether the following four strings are matched by
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
160 |
this regular expression. Answer yes or no.
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
161 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
162 |
\begin{enumerate}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
163 |
\item \texttt{"/**/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
164 |
\item \texttt{"/*foobar*/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
165 |
\item \texttt{"/*test*/test*/"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
166 |
\item \texttt{"/*test/*test*/"}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
167 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
168 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
169 |
\subsection*{Question 5 (marked with 1\%)}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
170 |
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
171 |
Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
172 |
$(a^{\{19,19\}}) \cdot (a^?)$. Decide whether the following three
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
173 |
strings consisting of $a$s only can be matched by $(r_1^+)^+$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
174 |
Similarly test them with $(r_2^+)^+$. Again answer in all six cases
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
175 |
with yes or no. \medskip
|
130
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
176 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
177 |
\noindent
|
259
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
178 |
These are strings are meant to be entirely made up of $a$s. Be careful
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
179 |
when copy-and-pasting the strings so as to not forgetting any $a$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
180 |
to not introducing any other character.
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
181 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
182 |
\begin{enumerate}
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
183 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
184 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
185 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
186 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
187 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
188 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
189 |
\item \texttt{"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
190 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\
|
216
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
191 |
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
|
127
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
192 |
\end{enumerate}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
193 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
194 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
195 |
\end{document}
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
196 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
197 |
%%% Local Variables:
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
198 |
%%% mode: latex
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
199 |
%%% TeX-master: t
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff
changeset
|
200 |
%%% End:
|