equal
deleted
inserted
replaced
77 For example $a + b$ and $b + a$ do not count\ldots they |
77 For example $a + b$ and $b + a$ do not count\ldots they |
78 obviously match the same strings, namely $[a]$ and |
78 obviously match the same strings, namely $[a]$ and |
79 $[b]$. |
79 $[b]$. |
80 |
80 |
81 \item What is meant by the notions \emph{evil regular expressions} |
81 \item What is meant by the notions \emph{evil regular expressions} |
82 and by \emph{catastrophic backtracking}? |
82 and by \emph{catastrophic backtracking}? |
|
83 |
|
84 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
|
85 which of the following regular expressions are equyivalent |
|
86 |
|
87 \begin{center} |
|
88 \begin{tabular}{ll} |
|
89 1) & $(ab + bb)^* \cdot (a + b)^*$\\ % no |
|
90 2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\ % yes |
|
91 3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$ % no |
|
92 \end{tabular} |
|
93 \end{center} |
|
94 |
83 |
95 |
84 \item \POSTSCRIPT |
96 \item \POSTSCRIPT |
85 \end{enumerate} |
97 \end{enumerate} |
86 |
98 |
87 \end{document} |
99 \end{document} |