diff -r e85600529ca5 -r 4794759139ea slides02.tex --- a/slides02.tex Sat Jun 15 09:11:11 2013 -0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,494 +0,0 @@ -\documentclass[dvipsnames,14pt,t]{beamer} -\usepackage{beamerthemeplainculight} -\usepackage[T1]{fontenc} -\usepackage[latin1]{inputenc} -\usepackage{mathpartir} -\usepackage[absolute,overlay]{textpos} -\usepackage{ifthen} -\usepackage{tikz} -\usepackage{pgf} -\usepackage{calc} -\usepackage{ulem} -\usepackage{courier} -\usepackage{listings} -\renewcommand{\uline}[1]{#1} -\usetikzlibrary{arrows} -\usetikzlibrary{automata} -\usetikzlibrary{shapes} -\usetikzlibrary{shadows} -\usetikzlibrary{positioning} -\usetikzlibrary{calc} -\usepackage{graphicx} - -\definecolor{javared}{rgb}{0.6,0,0} % for strings -\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 - -\lstset{language=Java, - basicstyle=\ttfamily, - keywordstyle=\color{javapurple}\bfseries, - stringstyle=\color{javagreen}, - commentstyle=\color{javagreen}, - morecomment=[s][\color{javadocblue}]{/**}{*/}, - numbers=left, - numberstyle=\tiny\color{black}, - stepnumber=1, - numbersep=10pt, - tabsize=2, - showspaces=false, - showstringspaces=false} - -\lstdefinelanguage{scala}{ - morekeywords={abstract,case,catch,class,def,% - do,else,extends,false,final,finally,% - for,if,implicit,import,match,mixin,% - new,null,object,override,package,% - private,protected,requires,return,sealed,% - super,this,throw,trait,true,try,% - type,val,var,while,with,yield}, - otherkeywords={=>,<-,<\%,<:,>:,\#,@}, - sensitive=true, - morecomment=[l]{//}, - morecomment=[n]{/*}{*/}, - morestring=[b]", - morestring=[b]', - morestring=[b]""" -} - -\lstset{language=Scala, - basicstyle=\ttfamily, - keywordstyle=\color{javapurple}\bfseries, - stringstyle=\color{javagreen}, - commentstyle=\color{javagreen}, - morecomment=[s][\color{javadocblue}]{/**}{*/}, - numbers=left, - numberstyle=\tiny\color{black}, - stepnumber=1, - numbersep=10pt, - tabsize=2, - showspaces=false, - showstringspaces=false} - -% beamer stuff -\renewcommand{\slidecaption}{AFL 02, King's College London, 3.~October 2012} -\newcommand{\bl}[1]{\textcolor{blue}{#1}} -\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions - -\begin{document} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}<1>[t] -\frametitle{% - \begin{tabular}{@ {}c@ {}} - \\[-3mm] - \LARGE Automata and \\[-2mm] - \LARGE Formal Languages (2)\\[3mm] - \end{tabular}} - - %\begin{center} - %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm} - %\includegraphics[scale=0.31]{pics/ante2.jpg}\\ - %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)} - %\end{center} - -\normalsize - \begin{center} - \begin{tabular}{ll} - Email: & christian.urban at kcl.ac.uk\\ - Of$\!$fice: & S1.27 (1st floor Strand Building)\\ - Slides: & KEATS - \end{tabular} - \end{center} - - -\end{frame}} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Languages\end{tabular}} - -A \alert{language} is a set of strings.\bigskip - -A \alert{regular expression} specifies a set of strings or language. - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} - -Their inductive definition: - - -\begin{textblock}{6}(2,5) - \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} - \end{textblock} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} - -Their implementation in Scala: - -{\lstset{language=Scala}\fontsize{8}{10}\selectfont -\texttt{\lstinputlisting{app51.scala}}} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} - -\begin{textblock}{15}(1,4) - \begin{tabular}{@ {}rcl} - \bl{$L$($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$}\\ - \bl{$L$($\epsilon$)} & \bl{$\dn$} & \bl{$\{$""$\}$}\\ - \bl{$L$(c)} & \bl{$\dn$} & \bl{$\{$"c"$\}$}\\ - \bl{$L$(r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) $\cup$ $L$(r$_2$)}\\ - \bl{$L$(r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{$L$(r$_1$) @ $L$(r$_2$)}\\ - \bl{$L$(r$^*$)} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}\\ - \end{tabular}\bigskip - -\hspace{5mm}\textcolor{gray}{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\ -\textcolor{gray}{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$} -\end{textblock} - -\only<2->{ -\begin{textblock}{5}(11,5) -\textcolor{gray}{\small -A @ B\\ -\ldots you take out every string from A and -concatenate it with every string in B -} -\end{textblock}} - -\only<3->{ -\begin{textblock}{6}(9,12)\small -\bl{$L$} is a function from regular expressions to sets of strings\\ -\bl{$L$ : Rexp $\Rightarrow$ Set[String]} -\end{textblock}} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -\large -\begin{center} -What is \bl{$L$(a$^*$)}? -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -\newcommand{\YES}{\textcolor{gray}{yes}} -\newcommand{\NO}{\textcolor{gray}{no}} -\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}} - -\begin{center} -\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l} -&\bl{(a + b) + c} & \bl{$\equiv^?$} & \bl{a + (b + c)} & \onslide<2->{\YES}\\ -&\bl{a + a} & \bl{$\equiv^?$} & \bl{a} & \onslide<3->{\YES}\\ -&\bl{(a $\cdot$ b) $\cdot$ c} & \bl{$\equiv^?$} & \bl{a $\cdot$ (b $\cdot$ c)} & \onslide<4->{\YES}\\ -&\bl{a $\cdot$ a} & \bl{$\equiv^?$} & \bl{a} & \onslide<5->{\NO}\\ -&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\ -&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\ -\FORALLR &\bl{r $\cdot$ $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<8->{\YES}\\ -\FORALLR &\bl{r + $\epsilon$} & \bl{$\equiv^?$} & \bl{r} & \onslide<9->{\NO}\\ -\FORALLR &\bl{r + $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<10->{\YES}\\ -\FORALLR &\bl{r $\cdot$ $\varnothing$} & \bl{$\equiv^?$} & \bl{r} & \onslide<11->{\NO}\\ -&\bl{c $\cdot$ (a + b)} & \bl{$\equiv^?$} & \bl{(c $\cdot$ a) + (c $\cdot$ b)} & \onslide<12->{\YES}\\ -&\bl{a$^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$ + (a $\cdot$ a$^*$)} & \onslide<13->{\YES} -\end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Meaning of Matching\end{tabular}} - -\large -a regular expression \bl{r} matches a string \bl{s} is defined as - -\begin{center} -\bl{s $\in$ $L$(r)}\\ -\end{center}\bigskip\bigskip\pause - -\small -if \bl{r$_1$ $\equiv$ r$_2$}, then \bl{$s$ $\in$ $L$(r$_1$)} iff \bl{$s$ $\in$ $L$(r$_2$)} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}} - -\begin{itemize} -\item given a regular expression \bl{r} and a string \bl{s}, say yes or no for whether -\begin{center} -\bl{s $\in$ $L$(r)} -\end{center} -or not.\bigskip\bigskip\pause -\end{itemize}\pause - -\small -\begin{itemize} -\item Identifiers (strings of letters or digits, starting with a letter) -\item Integers (a non-empty sequence of digits) -\item Keywords (else, if, while, \ldots) -\item White space (a non-empty sequence of blanks, newlines and tabs) -\end{itemize} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}} - -\small -whether a regular expression matches the empty string:\medskip - - -{\lstset{language=Scala}\fontsize{8}{10}\selectfont -\texttt{\lstinputlisting{app5.scala}}} - - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}} - -\large -If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip - -\small -\bl{der c r} gives the answer -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Derivative of a Rexp (2)\end{tabular}} - -\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$^*$)} &\smallskip\\\pause - - \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\ - \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\ - \end{tabular} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Derivative\end{tabular}} - - -{\lstset{language=Scala}\fontsize{8}{10}\selectfont -\texttt{\lstinputlisting{app6.scala}}} - - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}} - - -{\lstset{language=Scala}\fontsize{8}{10}\selectfont -\texttt{\lstinputlisting{app7.scala}}} - - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[t] -\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} - -Remember their inductive definition:\\[5cm] - -\begin{textblock}{6}(5,5) - \begin{tabular}{@ {}rrl} - \bl{r} & \bl{$::=$} & \bl{$\varnothing$}\\ - & \bl{$\mid$} & \bl{$\epsilon$} \\ - & \bl{$\mid$} & \bl{c} \\ - & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\ - & \bl{$\mid$} & \bl{r$_1$ + r$_2$} \\ - & \bl{$\mid$} & \bl{r$^*$} \\ - \end{tabular} - \end{textblock} - -If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Rexp (2)\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}. -\end{itemize} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}} - -Assume \bl{$P(r)$} is the property: - -\begin{center} -\bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)} -\end{center} - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}} - -If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip - -\begin{itemize} -\item \bl{$P$} holds for the empty string, and\medskip -\item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$} -already holds for \bl{s} -\end{itemize} -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} - -Let \bl{Der c A} be the set defined as - -\begin{center} -\bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } -\end{center} - -Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that - -\begin{center} -\bl{matcher(r, s) if and only if s $\in$ $L$(r)} -\end{center} - - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] -\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} - -A language (set of strings) is \alert{regular} iff there exists -a regular expression that recognises all its strings. - -\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} - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: t -%%% End: -