equal
deleted
inserted
replaced
11 |
11 |
12 This coursework is worth 3\% and is due on 12 November at 16:00. You are asked to implement |
12 This coursework is worth 3\% and is due on 12 November at 16:00. You are asked to implement |
13 a regular expression matcher and submit a document containing the answers for the questions |
13 a regular expression matcher and submit a document containing the answers for the questions |
14 below. You can do the implementation in any programming language you like, but you need |
14 below. You can do the implementation in any programming language you like, but you need |
15 to submit the source code with which you answered the questions. However, the coursework |
15 to submit the source code with which you answered the questions. However, the coursework |
16 will \emph{only} be judged according to the answers. \bigskip |
16 will \emph{only} be judged according to the answers. You can submit your answers |
|
17 in a txt-file.\bigskip |
17 |
18 |
18 \noindent |
19 \noindent |
19 The task is to implement a regular expression matcher based on derivatives. The implementation |
20 The task is to implement a regular expression matcher based on derivatives. The implementation |
20 should be able to deal with the usual regular expressions |
21 should be able to deal with the usual regular expressions |
21 |
22 |
58 \[ |
59 \[ |
59 [a b c d\ldots z 0 1\ldots 9]\;. |
60 [a b c d\ldots z 0 1\ldots 9]\;. |
60 \] |
61 \] |
61 |
62 |
62 \noindent |
63 \noindent |
63 Be careful that your implementations for $nullable$ and $der$ satisfies for every $r$ the following two |
64 Be careful that your implementation of $nullable$ and $der$ satisfies for every $r$ the following two |
64 properties: |
65 properties: |
65 |
66 |
66 \begin{itemize} |
67 \begin{itemize} |
67 \item $nullable(r)$ if and only if $""\in L(r)$ |
68 \item $nullable(r)$ if and only if $""\in L(r)$ |
68 \item $L(der\,c\,r)) = Der\,c\,(L(r))$ |
69 \item $L(der\,c\,r)) = Der\,c\,(L(r))$ |
82 \] |
83 \] |
83 |
84 |
84 \noindent |
85 \noindent |
85 and calculate the derivative according to your email address. When calculating |
86 and calculate the derivative according to your email address. When calculating |
86 the derivative, simplify all regular expressions as much as possible, but at least apply the following |
87 the derivative, simplify all regular expressions as much as possible, but at least apply the following |
87 six rules: |
88 six simplification rules: |
88 |
89 |
89 \begin{center} |
90 \begin{center} |
90 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
91 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
91 $r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\ |
92 $r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\ |
92 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ |
93 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ |
96 $\varnothing + r$ & $\mapsto$ & $r$\\ |
97 $\varnothing + r$ & $\mapsto$ & $r$\\ |
97 \end{tabular} |
98 \end{tabular} |
98 \end{center} |
99 \end{center} |
99 |
100 |
100 \noindent |
101 \noindent |
101 Write down your simplified derivative. |
102 Write down your simplified derivative in the ``mathematicical'' notation using parentheses where necessary. |
102 |
103 |
103 \subsection*{Question 3 (marked with 1\%)} |
104 \subsection*{Question 3 (marked with 1\%)} |
104 |
105 |
105 Consider the regular expression $/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /$ and decide |
106 Consider the regular expression $/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /$ and decide |
106 wether the following four strings are matched by this regular expression. Answer yes or no. |
107 wether the following four strings are matched by this regular expression. Answer yes or no. |
114 |
115 |
115 \subsection*{Question 4 (marked with 1\%)} |
116 \subsection*{Question 4 (marked with 1\%)} |
116 |
117 |
117 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be $(a^{\{19,19\}}) \cdot (a^?)$. |
118 Let $r_1$ be the regular expression $a\cdot a\cdot a$ and $r_2$ be $(a^{\{19,19\}}) \cdot (a^?)$. |
118 Decide whether the following three strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
119 Decide whether the following three strings consisting of $a$s only can be matched by $(r_1^+)^+$. |
119 Similarly test them with $(r_2^+)^+$. Again answer in all six cases with yes or no. Be careful when |
120 Similarly test them with $(r_2^+)^+$. Again answer in all six cases with yes or no. \medskip |
|
121 |
|
122 \noindent |
|
123 These are strings entirely made up of $a$s. Be careful when |
120 copy-and-pasting the strings so as to not forgetting any $a$ and to not introducing any |
124 copy-and-pasting the strings so as to not forgetting any $a$ and to not introducing any |
121 other character. |
125 other character. |
122 |
126 |
123 \begin{enumerate} |
127 \begin{enumerate} |
124 \item $"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |
128 \item $"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\\ |