equal
deleted
inserted
replaced
1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../langs} |
3 \usepackage{../langs} |
4 \usepackage{../graphics} |
4 \usepackage{../graphics} |
5 \usepackage{../data} |
5 \usepackage{../data} |
6 \usepackage{lstlinebgrd} |
6 |
7 \definecolor{capri}{rgb}{0.0, 0.75, 1.0} |
|
8 |
7 |
9 \begin{document} |
8 \begin{document} |
10 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
11 |
10 |
12 |
11 |
263 rule is applied. Our matching algorithm in the next section |
262 rule is applied. Our matching algorithm in the next section |
264 will often generate such ``useless'' $\ONE$s and |
263 will often generate such ``useless'' $\ONE$s and |
265 $\ZERO$s, therefore simplifying them away will make the |
264 $\ZERO$s, therefore simplifying them away will make the |
266 algorithm quite a bit faster. |
265 algorithm quite a bit faster. |
267 |
266 |
|
267 Finally here are three equivalences between regulare expressions which are |
|
268 not so obvious: |
|
269 |
|
270 \begin{center} |
|
271 \begin{tabular}{rcl} |
|
272 $r^*$ & $\equiv$ & $1 + r\cdot r^*$\\ |
|
273 $(r_1 + r_2)^*$ & $\equiv$ & $r_1^* \cdot (r_2\cdot r_1^*)^*$\\ |
|
274 $(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\ |
|
275 \end{tabular} |
|
276 \end{center} |
|
277 |
|
278 \noindent |
|
279 You can try to establish them. As an aside, there has been a lot of research |
|
280 in questions like: Can one always decide when two regular expressions are |
|
281 equivalent or not? What does an algorithm look like to decide this? |
|
282 |
268 \subsection*{The Matching Algorithm} |
283 \subsection*{The Matching Algorithm} |
269 |
284 |
270 The algorithm we will define below consists of two parts. One |
285 The algorithm we will define below consists of two parts. One |
271 is the function $\textit{nullable}$ which takes a regular expression as |
286 is the function $\textit{nullable}$ which takes a regular expression as |
272 argument and decides whether it can match the empty string |
287 argument and decides whether it can match the empty string |