1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{hyperref} |
2 \usepackage{../style} |
3 \usepackage{amssymb} |
|
4 \usepackage{amsmath} |
|
5 \usepackage[T1]{fontenc} |
|
6 \usepackage{../langs} |
3 \usepackage{../langs} |
7 |
|
8 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
|
9 |
4 |
10 |
5 |
11 \begin{document} |
6 \begin{document} |
12 |
7 |
13 \section*{Handout 2} |
8 \section*{Handout 2} |
14 |
9 |
15 Having specified what problem our matching algorithm, $match$, is supposed to solve, namely |
10 Having specified what problem our matching algorithm, |
16 for a given regular expression $r$ and string $s$ answer $true$ if and only if |
11 \pcode{match}, is supposed to solve, namely for a given |
|
12 regular expression $r$ and string $s$ answer \textit{true} if |
|
13 and only if |
17 |
14 |
18 \[ |
15 \[ |
19 s \in L(r) |
16 s \in L(r) |
20 \] |
17 \] |
21 |
18 |
22 \noindent |
19 \noindent we can look at an algorithm to solve this problem. |
23 we can look at an algorithm to solve this problem. |
20 Clearly we cannot use the function $L$ directly for this, |
24 Clearly we cannot use the function $L$ directly for this, because in general |
21 because in general the set of strings $L$ returns is infinite |
25 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no way we can implement |
22 (recall what $L(a^*)$ is). In such cases there is no way we |
26 an exhaustive test for whether a string is member of this set or not. |
23 can implement an exhaustive test for whether a string is |
|
24 member of this set or not. |
27 |
25 |
28 The algorithm we will define below consists of two parts. One is the function $nullable$ which takes a |
26 The algorithm we will define below consists of two parts. One is the function $nullable$ which takes a |
29 regular expression as argument and decides whether it can match the empty string (this means it returns a |
27 regular expression as argument and decides whether it can match the empty string (this means it returns a |
30 boolean). This can be easily defined recursively as follows: |
28 boolean). This can be easily defined recursively as follows: |
31 |
29 |