52 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings |
52 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings |
53 are in $A^4$? (2) Consider also the case of $A^4$ where one of |
53 are in $A^4$? (2) Consider also the case of $A^4$ where one of |
54 the strings in $A$ is the empty string, for example $A = |
54 the strings in $A$ is the empty string, for example $A = |
55 \{[a], [b], [c], []\}$. |
55 \{[a], [b], [c], []\}$. |
56 |
56 |
57 \item How many basic regular expressions are there to match |
57 \item (1)How many basic regular expressions are there to match |
58 the string $abcd$? (ii) How many if they cannot include |
58 the string $abcd$? (2) How many if they cannot include |
59 $\ONE$ and $\ZERO$? (iii) How many if they are also not |
59 $\ONE$ and $\ZERO$? (3) How many if they are also not |
60 allowed to contain stars? (iv) How many if they are also |
60 allowed to contain stars? (4) How many if they are also |
61 not allowed to contain $\_ + \_$? |
61 not allowed to contain $\_ + \_$? |
62 |
62 |
63 \item When are two regular expressions equivalent? Can you |
63 \item When are two regular expressions equivalent? Can you |
64 think of instances where two regular expressions match |
64 think of instances where two regular expressions match |
65 the same strings, but it is not so obvious that they do? |
65 the same strings, but it is not so obvious that they do? |
66 For example $a + b$ and $b + a$ do not count\ldots they |
66 For example $a + b$ and $b + a$ do not count\ldots they |
67 obviously match the same strings, namely $[a]$ and |
67 obviously match the same strings, namely $[a]$ and |
68 $[b]$. |
68 $[b]$. |
69 |
69 |
70 \item What is meant by the notions \emph{evil regular expressions} |
70 \item What is meant by the notions \emph{evil regular expressions} |
71 and \emph{catastrophic backtracking}? |
71 and by \emph{catastrophic backtracking}? |
72 |
72 |
73 \item \POSTSCRIPT |
73 \item \POSTSCRIPT |
74 \end{enumerate} |
74 \end{enumerate} |
75 |
75 |
76 \end{document} |
76 \end{document} |