93 |
93 |
94 where in (2) you pull out the ``factor'' $r$ (because $r_1 \cdot (r_2 + r_3) \equiv r_1 \cdot r_2 + r_1 \cdot r_3$). |
94 where in (2) you pull out the ``factor'' $r$ (because $r_1 \cdot (r_2 + r_3) \equiv r_1 \cdot r_2 + r_1 \cdot r_3$). |
95 } |
95 } |
96 |
96 |
97 |
97 |
98 \item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a |
98 %\item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a |
99 string $s$. Given the following \emph{reversing} function on regular |
99 % string $s$. Given the following \emph{reversing} function on regular |
100 expressions |
100 % expressions |
101 |
101 % |
102 \begin{center} |
102 % \begin{center} |
103 \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
103 % \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
104 $rev(\ZERO)$ & $\dn$ & $\ZERO$\\ |
104 % $rev(\ZERO)$ & $\dn$ & $\ZERO$\\ |
105 $rev(\ONE)$ & $\dn$ & $\ONE$\\ |
105 % $rev(\ONE)$ & $\dn$ & $\ONE$\\ |
106 $rev(c)$ & $\dn$ & $c$\\ |
106 % $rev(c)$ & $\dn$ & $c$\\ |
107 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
107 % $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
108 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
108 % $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
109 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
109 % $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
110 \end{tabular} |
110 % \end{tabular} |
|
111 % \end{center} |
|
112 % |
|
113 % and the set |
|
114 % |
|
115 % \begin{center} |
|
116 % $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
|
117 % \end{center} |
|
118 % |
|
119 % prove whether |
|
120 % |
|
121 % \begin{center} |
|
122 % $L(rev(r)) = Rev (L(r))$ |
|
123 % \end{center} |
|
124 % |
|
125 % holds. |
|
126 |
|
127 \item Construct a regular expression that can validate passwords. A |
|
128 password should be at least 8 characters long and consist of upper- |
|
129 and lower-case letters and digits. It should contain at least a |
|
130 single lower-case letter, at least a single upper-case letter and at |
|
131 least a single digit. If possible ise the intersection regular |
|
132 expression from CW1, written $\_\&\_$, the bounded regular |
|
133 expressions; you can also assume a regular expression written |
|
134 \texttt{ALL} that can match any character. |
|
135 |
|
136 \solution{ |
|
137 You can build-up the different constraints separately and then |
|
138 use the intersection operator: |
|
139 |
|
140 \begin{center} |
|
141 \begin{tabular}{lll} |
|
142 $ALL^{\{8..\}}$ & \;\&\; & $(ALL^*\cdot [a-z]\cdot ALL^*)$\\ |
|
143 & \;\&\; & $(ALL^*\cdot [A-Z]\cdot ALL^*)$\\ |
|
144 & \;\&\; & $(ALL^*\cdot [0-9]\cdot ALL^*)$\\ |
|
145 \end{tabular} |
111 \end{center} |
146 \end{center} |
112 |
147 } |
113 and the set |
148 |
114 |
|
115 \begin{center} |
|
116 $Rev\,A \dn \{s^{-1} \;|\; s \in A\}$ |
|
117 \end{center} |
|
118 |
|
119 prove whether |
|
120 |
|
121 \begin{center} |
|
122 $L(rev(r)) = Rev (L(r))$ |
|
123 \end{center} |
|
124 |
|
125 holds. |
|
126 |
|
127 \item Assume the delimiters for comments are |
149 \item Assume the delimiters for comments are |
128 \texttt{$\slash$*} and \texttt{*$\slash$}. Give a |
150 \texttt{$\slash$*} and \texttt{*$\slash$}. Give a |
129 regular expression that can recognise comments of the |
151 regular expression that can recognise comments of the |
130 form |
152 form |
131 |
153 |