equal
deleted
inserted
replaced
6 \usepackage{../data} |
6 \usepackage{../data} |
7 |
7 |
8 |
8 |
9 \begin{document} |
9 \begin{document} |
10 \fnote{\copyright{} Christian Urban, King's College London, |
10 \fnote{\copyright{} Christian Urban, King's College London, |
11 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021} |
11 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022} |
12 |
12 |
13 |
13 |
14 \section*{Handout 2 (Regular Expression Matching)} |
14 \section*{Handout 2 (Regular Expression Matching)} |
15 |
15 |
16 %\noindent |
16 %\noindent |
334 \[ |
334 \[ |
335 \textit{nullable}(r) \;\;\text{if and only if}\;\; []\in L(r) |
335 \textit{nullable}(r) \;\;\text{if and only if}\;\; []\in L(r) |
336 \] |
336 \] |
337 |
337 |
338 \noindent Note on the left-hand side of the if-and-only-if we have a |
338 \noindent Note on the left-hand side of the if-and-only-if we have a |
339 function we can implement, ofr example in Scala; on the right we have |
339 function we can implement, for example in Scala; on the right we have |
340 its specification (which we cannot implement in a programming language). |
340 its specification (which we cannot implement in a programming language). |
341 |
341 |
342 The other function of our matching algorithm calculates a |
342 The other function of our matching algorithm calculates a |
343 \emph{derivative} of a regular expression. This is a function |
343 \emph{derivative} of a regular expression. This is a function |
344 which will take a regular expression, say $r$, and a |
344 which will take a regular expression, say $r$, and a |
516 |
516 |
517 \begin{figure}[p] |
517 \begin{figure}[p] |
518 \lstinputlisting[numbers=left,linebackgroundcolor= |
518 \lstinputlisting[numbers=left,linebackgroundcolor= |
519 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
519 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
520 {../progs/app5.scala} |
520 {../progs/app5.scala} |
521 \caption{A Scala implementation of \textit{nullable} and |
521 \caption{A Scala implementation of the \textit{nullable} and |
522 derivative function. These functions are easy to |
522 the derivative function. These functions are easy to |
523 implement in functional programming languages. This is because pattern |
523 implement in functional programming languages. This is because pattern |
524 matching and recursion allow us to mimic the mathematical |
524 matching and recursion allow us to mimic the mathematical |
525 definitions very closely. Nearly all functional |
525 definitions very closely. Nearly all functional |
526 programming languages support pattern matching and |
526 programming languages support pattern matching and |
527 recursion out of the box.\label{scala1}} |
527 recursion out of the box.\label{scala1}} |