119 For example $a + b$ and $b + a$ do not count\ldots they |
119 For example $a + b$ and $b + a$ do not count\ldots they |
120 obviously match the same strings, namely $[a]$ and |
120 obviously match the same strings, namely $[a]$ and |
121 $[b]$. |
121 $[b]$. |
122 |
122 |
123 \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. |
123 \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. |
124 Can students think about why this is the case? - this would need a proof.} |
124 Can students think about why this is the case? - this would need a proof.\bigskip |
|
125 |
|
126 |
|
127 Lemma to prove: $A^* = \{[]\} \cup A \times A^*$ for any language $A$.\bigskip |
|
128 |
|
129 The definition of ${}^*$: $\bigcup n. A^n$\bigskip |
|
130 |
|
131 We first show $\subseteq$ of the lemma: a string $s \in A^*$, must also be in |
|
132 $\bigcup n. A^n$, which means there is an $n$ such that $s\in A^n$. |
|
133 If $n = 0$ then $s = []$ and $s$ is also in $\{[]\} \cup A \times A^*$. |
|
134 If $n$ is bigger than $0$, then $s\in A^n$, which means by |
|
135 definition of power that $s\in A \times A^{n - 1}$. But then |
|
136 also $s \in A \times A^*$. That is one direction.\bigskip |
|
137 |
|
138 The other direction: Two cases: (i) $s\in \{[]\}$ then |
|
139 also $s\in A^*$. (ii) $s\in A \times A^*$ means there exists |
|
140 an $n$ such that $s\in A\times A^n$. This in turn means |
|
141 $s\in A^{n + 1}$ (by definition of power). But this also means $s\in A^*$. |
|
142 So $\{[]\} \cup A \times A^*$ is a subset of $A^*$. Done! |
|
143 } |
125 |
144 |
126 \item What is meant by the notions \emph{evil regular expressions} |
145 \item What is meant by the notions \emph{evil regular expressions} |
127 and by \emph{catastrophic backtracking}? |
146 and by \emph{catastrophic backtracking}? |
128 |
147 |
129 \solution{catastrophic backtracking also applies to other regexes, |
148 \solution{catastrophic backtracking also applies to other regexes, |