|
1 \documentclass{article} |
|
2 \usepackage{charter} |
|
3 \usepackage{hyperref} |
|
4 \usepackage{amssymb} |
|
5 \usepackage{amsmath} |
|
6 \usepackage[T1]{fontenc} |
|
7 \usepackage{listings} |
|
8 \usepackage{xcolor} |
|
9 |
|
10 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% |
|
11 |
|
12 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
13 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
14 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
15 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
16 |
|
17 \lstdefinelanguage{scala}{ |
|
18 morekeywords={abstract,case,catch,class,def,% |
|
19 do,else,extends,false,final,finally,% |
|
20 for,if,implicit,import,match,mixin,% |
|
21 new,null,object,override,package,% |
|
22 private,protected,requires,return,sealed,% |
|
23 super,this,throw,trait,true,try,% |
|
24 type,val,var,while,with,yield}, |
|
25 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
26 sensitive=true, |
|
27 morecomment=[l]{//}, |
|
28 morecomment=[n]{/*}{*/}, |
|
29 morestring=[b]", |
|
30 morestring=[b]', |
|
31 morestring=[b]""" |
|
32 } |
|
33 |
|
34 \lstset{language=Scala, |
|
35 basicstyle=\ttfamily, |
|
36 keywordstyle=\color{javapurple}\bfseries, |
|
37 stringstyle=\color{javagreen}, |
|
38 commentstyle=\color{javagreen}, |
|
39 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
40 numbers=left, |
|
41 numberstyle=\tiny\color{black}, |
|
42 stepnumber=1, |
|
43 numbersep=10pt, |
|
44 tabsize=2, |
|
45 showspaces=false, |
|
46 showstringspaces=false} |
|
47 |
|
48 \begin{document} |
|
49 |
|
50 \section*{Handout 2} |
|
51 |
|
52 Having specified what problem our matching algorithm, $match$, is supposed to solve, namely |
|
53 for a given regular expression $r$ and string $s$ answer $true$ if and only if |
|
54 |
|
55 \[ |
|
56 s \in L(r) |
|
57 \] |
|
58 |
|
59 \noindent |
|
60 Clearly we cannot use the function $L$ directly in order to solve this problem, because in general |
|
61 the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no algorithm |
|
62 then can test exhaustively, whether a string is member of this set. |
|
63 |
|
64 The algorithm we define below consists of two parts. One is the function $nullable$ which takes a |
|
65 regular expression as argument and decides whether it can match the empty string. This can be easily |
|
66 defined recursively as follows: |
|
67 |
|
68 |
|
69 \end{document} |
|
70 |
|
71 %%% Local Variables: |
|
72 %%% mode: latex |
|
73 %%% TeX-master: t |
|
74 %%% End: |