# HG changeset patch # User Christian Urban # Date 1381161576 -3600 # Node ID 09efdf5cf07c9d22e3cc700ea2a90fe948dec90b # Parent 04264d0c43bb4ac7db9069ad423c7dc69faecf1b updated diff -r 04264d0c43bb -r 09efdf5cf07c coursework/cw01.pdf Binary file coursework/cw01.pdf has changed diff -r 04264d0c43bb -r 09efdf5cf07c coursework/cw01.tex --- a/coursework/cw01.tex Mon Oct 07 09:45:11 2013 +0100 +++ b/coursework/cw01.tex Mon Oct 07 16:59:36 2013 +0100 @@ -120,7 +120,7 @@ Similarly test them with $(r_2^+)^+$. Again answer in all six cases with yes or no. \medskip \noindent -These are strings entirely made up of $a$s. Be careful when +These are strings are meant to be entirely made up of $a$s. Be careful when copy-and-pasting the strings so as to not forgetting any $a$ and to not introducing any other character. diff -r 04264d0c43bb -r 09efdf5cf07c handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 04264d0c43bb -r 09efdf5cf07c handouts/ho02.tex --- a/handouts/ho02.tex Mon Oct 07 09:45:11 2013 +0100 +++ b/handouts/ho02.tex Mon Oct 07 16:59:36 2013 +0100 @@ -179,8 +179,9 @@ \] \noindent -holds, which means our algorithm satisfies the specification. This algorithm can be easily -extended for other regular expressions such as $r^{\{n\}}$, $r^?$, $\sim{}r$ and so on. +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}}} diff -r 04264d0c43bb -r 09efdf5cf07c slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 04264d0c43bb -r 09efdf5cf07c slides/slides02.tex --- a/slides/slides02.tex Mon Oct 07 09:45:11 2013 +0100 +++ b/slides/slides02.tex Mon Oct 07 16:59:36 2013 +0100 @@ -1011,62 +1011,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} - -\begin{itemize} -\item symbols, digits -\item identifiers -\item numbers (non-leading zeros) -\item keywords -\item comments -\end{itemize}\bigskip - - -\mbox{}\hfill\bl{\url{http://www.regexper.com}} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} - -A language (a set of strings) is \alert{regular} iff there exists -a regular expression that recognises all its strings.\bigskip\bigskip\pause - - -Do you think there are languages that are {\bf not} regular? -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Automata\end{tabular}} - -A deterministic finite automaton consists of: - -\begin{itemize} -\item a set of states -\item one of these states is the start state -\item some states are accepting states, and -\item there is transition function\medskip - -\small -which takes a state as argument and a character and produces a new state\smallskip\\ -this function might not always be defined -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - \end{document} diff -r 04264d0c43bb -r 09efdf5cf07c slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 04264d0c43bb -r 09efdf5cf07c slides/slides03.tex --- a/slides/slides03.tex Mon Oct 07 09:45:11 2013 +0100 +++ b/slides/slides03.tex Mon Oct 07 16:59:36 2013 +0100 @@ -1,6 +1,6 @@ \documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplainculight} -\usepackage[T1]{fontenc} +\usepackage{beamerthemeplaincu} +%%\usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{mathpartir} \usepackage[absolute,overlay]{textpos} @@ -24,9 +24,13 @@ \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc +\makeatletter +\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}} +\@empty\z@\@empty +\makeatother \lstset{language=Java, - basicstyle=\ttfamily, + basicstyle=\consolas, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, @@ -47,7 +51,7 @@ private,protected,requires,return,sealed,% super,this,throw,trait,true,try,% type,val,var,while,with,yield}, - otherkeywords={=>,<-,<\%,<:,>:,\#,@}, + otherkeywords={=>,<-,<\%,<:,>:,\#,@,->}, sensitive=true, morecomment=[l]{//}, morecomment=[n]{/*}{*/}, @@ -57,7 +61,7 @@ } \lstset{language=Scala, - basicstyle=\ttfamily, + basicstyle=\consolas, keywordstyle=\color{javapurple}\bfseries, stringstyle=\color{javagreen}, commentstyle=\color{javagreen}, @@ -70,8 +74,9 @@ showspaces=false, showstringspaces=false} + % beamer stuff -\renewcommand{\slidecaption}{AFL 03, King's College London, 10.~October 2012} +\renewcommand{\slidecaption}{AFL 03, King's College London, 9.~October 2013} \newcommand{\bl}[1]{\textcolor{blue}{#1}} \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions @@ -97,9 +102,8 @@ \begin{center} \begin{tabular}{ll} Email: & christian.urban at kcl.ac.uk\\ - Of$\!$fice: & S1.27 (1st floor Strand Building)\\ + Office: & S1.27 (1st floor Strand Building)\\ Slides: & KEATS (also home work is there)\\ - & \alert{\bf (I have put a temporary link in there.)}\\ \end{tabular} \end{center} @@ -110,18 +114,39 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Last Week\end{tabular}} +\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} -Last week I showed you +They are often used to recognise:\medskip \begin{itemize} -\item one simple-minded regular expression matcher (which however does not work in all cases), and\bigskip -\item one which works provably in all cases +\item symbols, digits +\item identifiers +\item numbers (non-leading zeros) +\item keywords +\item comments +\end{itemize}\bigskip + + +\mbox{}\hfill\bl{\url{http://www.regexper.com}} +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Last Week\end{tabular}} + +Last week I showed you a regular expression matcher +which works provably in all cases. \begin{center} -\bl{matcher r s} \;\;if and only if \;\; \bl{s $\in$ $L$(r)} -\end{center} -\end{itemize} +\bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$} +\end{center}\bigskip\bigskip + +\small +\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)} + \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -133,18 +158,20 @@ \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} - \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ - \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ - \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then $\epsilon$ else $\varnothing$} & \\ - \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ - \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{if nullable r$_1$}\\ - & & \bl{then ((der c r$_1$) $\cdot$ r$_2$) + (der c r$_2$)}\\ - & & \bl{else (der c r$_1$) $\cdot$ r$_2$}\\ - \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)}\\ + \bl{$der\, c\, (\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ + \bl{$der\, c\, (\epsilon)$} & \bl{$\dn$} & \bl{$\varnothing$} & \\ + \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ + \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ + \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ + & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ + & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ + \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause + + \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ + \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ \end{tabular} \end{center} -``the regular expression after \bl{c} has been recognised'' \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -153,19 +180,24 @@ \mode{ \begin{frame}[c] -For this we defined the set \bl{Der c A} as + +To see what is going on, define \begin{center} -\bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } -\end{center} +\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } +\end{center}\bigskip\bigskip -which is called the semantic derivative of a set -and proved +\small +For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then \begin{center} -\bl{$L$(der c r) $=$ Der c ($L$(r))} +\bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} +$Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\ +$Der\,b\,A$ & $=$ & $\{"ar"\}$\\ +$Der\,a\,A$ & $=$ & $\varnothing$\\ +\end{tabular}} \end{center} - + \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -176,14 +208,14 @@ \begin{frame}[c] \frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}} -If we want to recognise the string \bl{abc} with regular expression \bl{r} +If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$} then\medskip \begin{enumerate} -\item \bl{Der a ($L$(r))}\pause -\item \bl{Der b (Der a ($L$(r)))} -\item \bl{Der c (Der b (Der a ($L$(r))))}\pause -\item finally we test whether the empty string is in set\pause\medskip +\item \bl{$Der\,a\,(L(r))$}\pause +\item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause +\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause +\item finally we test whether the empty string is in this set\pause\medskip \end{enumerate} The matching algorithm works similarly, just over regular expression than sets. @@ -195,12 +227,12 @@ \mode{ \begin{frame}[c] -Input: string \bl{abc} and regular expression \bl{r} +Input: string \bl{$"abc"$} and regular expression \bl{$r$} \begin{enumerate} -\item \bl{der a r} -\item \bl{der b (der a r)} -\item \bl{der c (der b (der a r))}\pause +\item \bl{$der\,a\,r$} +\item \bl{$der\,b\,(der\,a\,r)$} +\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause \item finally check whether the latter regular expression can match the empty string \end{enumerate} @@ -211,10 +243,25 @@ \mode{ \begin{frame}[c] +We proved already + +\begin{center} +\bl{$nullable(r)$} \;if and only if\; \bl{$"" \in L(r)$} +\end{center} + +by induction on the regular expression. + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] + We need to prove \begin{center} -\bl{$L$(der c r) $=$ Der c ($L$(r))} +\bl{$L(der\,c\,r) = Der\,c\,(L(r))$} \end{center} by induction on the regular expression. @@ -226,16 +273,16 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} +\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}} \begin{itemize} \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip -\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already -holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip -\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already -holds for \bl{r$_1$} and \bl{r$_2$}. -\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already -holds for \bl{r}. +\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already +holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip +\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already +holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip +\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already +holds for \bl{$r$}. \end{itemize} \end{frame}} @@ -244,7 +291,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Natural Numbers\\ and Strings\end{tabular}} +\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}} \begin{itemize} \item \bl{$P$} holds for \bl{$0$} and @@ -253,7 +300,7 @@ \end{itemize}\bigskip \begin{itemize} -\item \bl{$P$} holds for \bl{\texttt{""}} and +\item \bl{$P$} holds for \bl{$""$} and \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already holds for \bl{$s$} \end{itemize} @@ -261,26 +308,6 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} - -\begin{center} - \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{r} & \bl{$::=$} & \bl{$\varnothing$} & null\\ - & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / []\\ - & \bl{$\mid$} & \bl{c} & character\\ - & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\ - & \bl{$\mid$} & \bl{r$_1$ + r$_2$} & alternative / choice\\ - & \bl{$\mid$} & \bl{r$^*$} & star (zero or more)\\ - \end{tabular}\bigskip\pause - \end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -290,7 +317,7 @@ A \alert{language} is a set of strings.\bigskip -A \alert{regular expression} specifies a set of strings or language.\bigskip +A \alert{regular expression} specifies a language.\bigskip A language is \alert{regular} iff there exists a regular expression that recognises all its strings.\bigskip\bigskip\pause @@ -340,6 +367,19 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \mode{ \begin{frame}[c] +\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} + +A language (a set of strings) is \alert{regular} iff there exists +a regular expression that recognises all its strings.\bigskip\bigskip\pause + + +Do you think there are languages that are {\bf not} regular? +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}} Lexing separates strings into ``words'' / components. @@ -375,6 +415,26 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}[c] +\frametitle{\begin{tabular}{c}Automata\end{tabular}} + +A deterministic finite automaton consists of: + +\begin{itemize} +\item a set of states +\item one of these states is the start state +\item some states are accepting states, and +\item there is transition function\medskip + +\small +which takes a state as argument and a character and produces a new state\smallskip\\ +this function might not always be defined +\end{itemize} + +\end{frame}} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \end{document}