# HG changeset patch # User Christian Urban # Date 1381569232 -3600 # Node ID 665087dcf7d247de883e0dbcbd435a05710e3799 # Parent 1be892087df2f577a1536563e5458cbc90e2cd58 added diff -r 1be892087df2 -r 665087dcf7d2 handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 1be892087df2 -r 665087dcf7d2 handouts/ho03.tex --- a/handouts/ho03.tex Sat Oct 12 10:12:38 2013 +0100 +++ b/handouts/ho03.tex Sat Oct 12 10:13:52 2013 +0100 @@ -47,147 +47,8 @@ \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 - -\[ -s \in L(r) -\] - -\noindent -Clearly we cannot use the function $L$ directly in order to solve this problem, because in general -the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no algorithm -then can test exhaustively, whether a string is member of this set. - -The algorithm we 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 -boolean). This can be easily defined recursively as follows: - -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -$nullable(\varnothing)$ & $\dn$ & $f\!\/alse$\\ -$nullable(\epsilon)$ & $\dn$ & $true$\\ -$nullable (c)$ & $\dn$ & $f\!alse$\\ -$nullable (r_1 + r_2)$ & $\dn$ & $nullable(r_1) \vee nullable(r_2)$\\ -$nullable (r_1 \cdot r_2)$ & $\dn$ & $nullable(r_1) \wedge nullable(r_2)$\\ -$nullable (r^*)$ & $\dn$ & $true$ \\ -\end{tabular} -\end{center} - -\noindent -The idea behind this function is that the following property holds: - -\[ -nullable(r) \;\;\text{if and only if}\;\; ""\in L(r) -\] - -\noindent -On the left-hand side we have a function we can implement; on the right we have its specification. - -The other function is calculating a \emph{derivative} of a regular expression. This is a function -which will take a regular expression, say $r$, and a character, say $c$, as argument and return -a new regular expression. Beware that the intuition behind this function is not so easy to grasp on first -reading. Essentially this function solves the following problem: if $r$ can match a string of the form -$c\!::\!s$, what does the regular expression look like that can match just $s$. The definition of this -function is as follows: - -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} - $der\, c\, (\varnothing)$ & $\dn$ & $\varnothing$ & \\ - $der\, c\, (\epsilon)$ & $\dn$ & $\varnothing$ & \\ - $der\, c\, (d)$ & $\dn$ & if $c = d$ then $\epsilon$ else $\varnothing$ & \\ - $der\, c\, (r_1 + r_2)$ & $\dn$ & $der\, c\, r_1 + der\, c\, r_2$ & \\ - $der\, c\, (r_1 \cdot r_2)$ & $\dn$ & if $nullable (r_1)$\\ - & & then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$\\ - & & else $(der\, c\, r_1) \cdot r_2$\\ - $der\, c\, (r^*)$ & $\dn$ & $(der\,c\,r) \cdot (r^*)$ & - \end{tabular} -\end{center} +\section*{Handout 3} -\noindent -The first two clauses can be rationalised as follows: recall that $der$ should calculate a regular -expression, if the ``input'' regular expression can match a string of the form $c\!::\!s$. Since neither -$\varnothing$ nor $\epsilon$ can match such a string we return $\varnothing$. In the third case -we have to make a case-distinction: In case the regular expression is $c$, then clearly it can recognise -a string of the form $c\!::\!s$, just that $s$ is the empty string. Therefore we return the $\epsilon$-regular -expression. In the other case we again return $\varnothing$ since no string of the $c\!::\!s$ can be matched. -The $+$-case is relatively straightforward: all strings of the form $c\!::\!s$ are either matched by the -regular expression $r_1$ or $r_2$. So we just have to recursively call $der$ with these two regular -expressions and compose the results again with $+$. The $\cdot$-case is more complicated: -if $r_1\cdot r_2$ matches a string of the form $c\!::\!s$, then the first part must be matched by $r_1$. -Consequently, it makes sense to construct the regular expression for $s$ by calling $der$ with $r_1$ and -``appending'' $r_2$. There is however one exception to this simple rule: if $r_1$ can match the empty -string, then all of $c\!::\!s$ is matched by $r_2$. So in case $r_1$ is nullable (that is can match the -empty string) we have to allow the choice $der\,c\,r_2$ for calculating the regular expression that can match -$s$. The $*$-case is again simple: if $r^*$ matches a string of the form $c\!::\!s$, then the first part must be -``matched'' by a single copy of $r$. Therefore we call recursively $der\,c\,r$ and ``append'' $r^*$ in order to -match the rest of $s$. - -Another way to rationalise the definition of $der$ is to consider the following operation on sets: - -\[ -Der\,c\,A\;\dn\;\{s\,|\,c\!::\!s \in A\} -\] - -\noindent -which essentially transforms a set of strings $A$ by filtering out all strings that do not start with $c$ and then -strip off the $c$ from all the remaining strings. For example suppose $A = \{"f\!oo", "bar", "f\!rak"\}$ then -\[ -Der\,f\,A = \{"oo", "rak"\}\quad,\quad -Der\,b\,A = \{"ar"\} \quad \text{and} \quad -Der\,a\,A = \varnothing -\] - -\noindent -Note that in the last case $Der$ is empty, because no string in $A$ starts with $a$. With this operation we can -state the following property about $der$: - -\[ -L(der\,c\,r) = Der\,c\,(L(r)) -\] - -\noindent -This property clarifies what regular expression $der$ calculates, namely take the set of strings -that $r$ can match ($L(r)$), filter out all strings not starting with $c$ and strip off the $c$ from the -remaining strings---this is exactly the language that $der\,c\,r$ can match. - -For our matching algorithm we need to lift the notion of derivatives from characters to strings. This can be -done using the following function, taking a string and regular expression as input and a regular expression -as output. - -\begin{center} -\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} - $der\!s\, []\, r$ & $\dn$ & $r$ & \\ - $der\!s\, (c\!::\!s)\, r$ & $\dn$ & $der\!s\,s\,(der\,c\,r)$ & \\ - \end{tabular} -\end{center} - -\noindent -Having $ders$ in place, we can finally define our matching algorithm: - -\[ -match\,s\,r = nullable(ders\,s\,r) -\] - -\noindent -We claim that - -\[ -match\,s\,r\quad\text{if and only if}\quad s\in L(r) -\] - -\noindent -holds, which means our algorithm satisfies the specification. This algorithm was introduced by -Janus Brzozowski in 1964. Its main attractions are simplicity and being fast, as well as -being easily extendable for other regular expressions such as $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on. - -\begin{figure}[p] -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/app5.scala}}} -{\lstset{language=Scala}\texttt{\lstinputlisting{../progs/app6.scala}}} -\caption{Scala implementation of the nullable and derivatives functions.} -\end{figure} \end{document}