diff -r b79e704acb72 -r 5b5a68df6d16 handouts/ho02.tex --- a/handouts/ho02.tex Mon Sep 15 07:25:17 2014 +0100 +++ b/handouts/ho02.tex Mon Sep 15 09:36:02 2014 +0100 @@ -1,29 +1,27 @@ \documentclass{article} -\usepackage{hyperref} -\usepackage{amssymb} -\usepackage{amsmath} -\usepackage[T1]{fontenc} +\usepackage{../style} \usepackage{../langs} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% - \begin{document} \section*{Handout 2} -Having specified what problem our matching algorithm, $match$, is supposed to solve, namely -for a given regular expression $r$ and string $s$ answer $true$ if and only if +Having specified what problem our matching algorithm, +\pcode{match}, is supposed to solve, namely for a given +regular expression $r$ and string $s$ answer \textit{true} if +and only if \[ s \in L(r) \] -\noindent -we can look at an algorithm to solve this problem. -Clearly we cannot use the function $L$ directly for this, because in general -the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no way we can implement -an exhaustive test for whether a string is member of this set or not. +\noindent we can look at an algorithm to solve this problem. +Clearly we cannot use the function $L$ directly for this, +because in general the set of strings $L$ returns is infinite +(recall what $L(a^*)$ is). In such cases there is no way we +can implement an exhaustive test for whether a string is +member of this set or not. The algorithm we will define below consists of two parts. One is the function $nullable$ which takes a regular expression as argument and decides whether it can match the empty string (this means it returns a