# HG changeset patch # User Christian Urban # Date 1475930730 -3600 # Node ID e7d0157f047134d863197cb75d51043892b9eac5 # Parent 3056a4c071b043089246fc57fc3f6c992860066a updated slides diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides03.tex --- a/slides/slides03.tex Fri Oct 07 22:08:03 2016 +0100 +++ b/slides/slides03.tex Sat Oct 08 13:45:30 2016 +0100 @@ -11,7 +11,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 03, King's College London} +\renewcommand{\slidecaption}{CFL 03, King's College London} \begin{document} @@ -20,7 +20,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-2mm] \LARGE Formal Languages (3)\\[3mm] \end{tabular}} @@ -34,7 +34,20 @@ \end{center} \end{frame} - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{Scala Book, Exams} + +\begin{itemize} +\item www.inf.kcl.ac.uk/~urbanc/ProgInScala2ed.pdf +\item homeworks (exam 80\%) +\item coursework (20\%) +\end{itemize} + +\end{frame} +%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -79,9 +92,9 @@ \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\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ + \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ + \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ \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$}\\ @@ -120,7 +133,7 @@ \bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} \end{center} -by induction on the regular expression.\bigskip\pause +by induction on the regular expression \bl{$r$}.\bigskip\pause \begin{center} {\huge\bf\alert{Any Questions?}} @@ -138,7 +151,7 @@ \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} \end{center} -by induction on the regular expression. +also by induction on the regular expression \bl{$r$}. \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -147,7 +160,7 @@ \frametitle{Proofs about Rexps} \begin{itemize} -\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip +\item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} 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 @@ -184,8 +197,8 @@ \begin{center} \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ - & \bl{$\mid$} & \bl{$\epsilon$} & empty string / "" / $[]$\\ + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\ + & \bl{$\mid$} & \bl{$\ONE$} & 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\\ @@ -473,11 +486,11 @@ \begin{center} \begin{tabular}[t]{l@{\hspace{10mm}}l} -\raisebox{1mm}{\bl{$\varnothing$}} & +\raisebox{1mm}{\bl{$\ZERO$}} & \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] \node[state, initial] (q_0) {$\mbox{}$}; \end{tikzpicture}\\\\ -\raisebox{1mm}{\bl{$\epsilon$}} & +\raisebox{1mm}{\bl{$\ONE$}} & \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] \node[state, initial, accepting] (q_0) {$\mbox{}$}; \end{tikzpicture}\\\\ @@ -715,7 +728,7 @@ \footnotesize \begin{center} \begin{tabular}{ll} -DFA: & NFA:\\ +DFA: & (original) NFA:\\ \raisebox{10mm}{% \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=0pt, @@ -1053,6 +1066,7 @@ \end{center}\pause\bigskip \onslide<2->{ +You know how to solve since school days, no? \begin{center} \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ @@ -1088,7 +1102,7 @@ \onslide<2->{ \begin{center} \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} -\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ +\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$}\\ \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ @@ -1151,8 +1165,8 @@ \begin{center} \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} -$rev(\varnothing)$ & $\dn$ & $\varnothing$\\ -$rev(\epsilon)$ & $\dn$ & $\epsilon$\\ +$rev(\ZERO)$ & $\dn$ & $\ZERO$\\ +$rev(\ONE)$ & $\dn$ & $\ONE$\\ $rev(c)$ & $\dn$ & $c$\\ $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides04.tex --- a/slides/slides04.tex Fri Oct 07 22:08:03 2016 +0100 +++ b/slides/slides04.tex Sat Oct 08 13:45:30 2016 +0100 @@ -10,7 +10,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} -\renewcommand{\slidecaption}{AFL 04, King's College London} +\renewcommand{\slidecaption}{CFL 04, King's College London} \begin{document} @@ -19,7 +19,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-2mm] \LARGE Formal Languages (4)\\[3mm] \end{tabular}} @@ -61,7 +61,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}} +\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} \begin{tikzpicture} \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, @@ -77,12 +77,9 @@ legend entries={Python,Ruby,my NFA}, legend pos=north west, legend cell align=left] -\addplot[blue,mark=*, mark options={fill=white}] - table {re-python.data}; -\addplot[brown,mark=pentagon*, mark options={fill=white}] - table {re-ruby.data}; -\addplot[red,mark=triangle*, mark options={fill=white}] - table {nfasearch.data}; +\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; +\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; +\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; \end{axis} \end{tikzpicture} @@ -111,7 +108,7 @@ \begin{center} \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} -\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ +\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ @@ -241,7 +238,7 @@ \small -for example $a^nb^n$ is not regular +for example \bl{$a^nb^n$} is not regular \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -542,8 +539,8 @@ \begin{columns} \begin{column}{3cm} \begin{tabular}{@{}rrl@{}} - \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\ - & \bl{$\mid$} & \bl{$\epsilon$} \\ + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ + & \bl{$\mid$} & \bl{$\ONE$} \\ & \bl{$\mid$} & \bl{$c$} \\ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ @@ -589,7 +586,7 @@ \begin{center} \begin{tabular}{lcl} - \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\ + \bl{$mkeps\,\ONE$} & \bl{$\dn$} & \bl{$Empty$}\\ \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ & & \bl{then $Left(mkeps(r_1))$}\\ & & \bl{else $Right(mkeps(r_2))$}\\ @@ -660,9 +657,9 @@ \small \begin{tabular}{ll} \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ -\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ -\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ -\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ +\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ \end{tabular} \end{bubble} \end{textblock}} @@ -735,9 +732,9 @@ \small \begin{tabular}{ll} \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ -\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ -\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ -\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ +\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ \end{tabular} \end{bubble} \end{textblock} @@ -831,30 +828,12 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Records} - -\begin{itemize} -\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause - -\item \bl{$nullable(x:r) \dn nullable(r)$} -\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$} -\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} -\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} -\end{itemize}\bigskip\bigskip\pause - -\small -for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \begin{itemize} -\item Regular expression for email addresses +\item A regular expression for email addresses \begin{center} \begin{tabular}{l} @@ -868,7 +847,7 @@ \texttt{christian.urban@kcl.ac.uk} \]} -\item result environment: +\item the result environment: \begin{center} \begin{tabular}{l} @@ -941,9 +920,9 @@ \end{center} \small -\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$} +\hspace{4.5cm}\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$} $\mapsto$ -\bl{$\epsilon$} +\bl{$\ONE$} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -954,22 +933,22 @@ \def\arraystretch{1.05} \begin{center} -\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{5mm}}l} +\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l} & & & \hspace{5mm}rectification \\ & & & \hspace{5mm}functions:\\ -\bl{$r \cdot \varnothing$} & $\mapsto$ & \bl{$\varnothing$} & \\ -\bl{$\varnothing \cdot r$} & $\mapsto$ & \bl{$\varnothing$} & \\ -\bl{$r \cdot \epsilon$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ -\bl{$\epsilon \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ -\bl{$r + \varnothing$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ -\bl{$\varnothing + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\ +\bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\ +\bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\ +\bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ +\bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ +\bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ +\bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\ \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$} \end{tabular} \end{center}\medskip\pause \small old \bl{$simp$} returns a rexp;\\ -new \bl{$simp$} returns a rexp and a rectification~fun. +new \bl{$simp$} returns a rexp and a rectification~function. \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -984,9 +963,9 @@ \quad case \bl{$r = r_1 + r_2$}\\ \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ -\qquad case \bl{$r_{1s} = \varnothing$}: +\qquad case \bl{$r_{1s} = \ZERO$}: return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ -\qquad case \bl{$r_{2s} = \varnothing$}: +\qquad case \bl{$r_{2s} = \ZERO$}: return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ \qquad case \bl{$r_{1s} = r_{2s}$}: return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ @@ -1010,12 +989,14 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] {\footnotesize\lstinputlisting[language=Scala,numbers=none, xleftmargin=-5mm] {../progs/app05.scala}} \end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -1027,13 +1008,13 @@ \quad case \bl{$r = r_1 \cdot r_2$}\\ \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ -\qquad case \bl{$r_{1s} = \varnothing$}: - return \bl{$(\varnothing, f_{error})$}\\ -\qquad case \bl{$r_{2s} = \varnothing$}: - return \bl{$(\varnothing, f_{error})$}\\ -\qquad case \bl{$r_{1s} = \epsilon$}: +\qquad case \bl{$r_{1s} = \ZERO$}: + return \bl{$(\ZERO, f_{error})$}\\ +\qquad case \bl{$r_{2s} = \ZERO$}: + return \bl{$(\ZERO, f_{error})$}\\ +\qquad case \bl{$r_{1s} = \ONE$}: return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ -\qquad case \bl{$r_{2s} = \epsilon$}: +\qquad case \bl{$r_{2s} = \ONE$}: return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ \qquad otherwise: return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ @@ -1107,17 +1088,17 @@ \begin{frame}[c] \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -$zeroable(\varnothing)$ & $\dn$ & $true$\\ -$zeroable(\epsilon)$ & $\dn$ & $f\!alse$\\ -$zeroable (c)$ & $\dn$ & $f\!alse$\\ -$zeroable (r_1 + r_2)$ & $\dn$ & $zeroable(r_1) \wedge zeroable(r_2)$ \\ -$zeroable (r_1 \cdot r_2)$ & $\dn$ & $zeroable(r_1) \vee zeroable(r_2)$ \\ -$zeroable (r^*)$ & $\dn$ & $f\!alse$\\ +\bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\ +\bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ +\bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ +\bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ +\bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\ +\bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ \end{tabular} \end{center} \begin{center} -$zeroable(r)$ if and only if $L(r) = \varnothing$ +\bl{$zeroable(r)$} if and only if \bl{$L(r) = \{\}$} \end{center} diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides05.pdf Binary file slides/slides05.pdf has changed diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides05.tex --- a/slides/slides05.tex Fri Oct 07 22:08:03 2016 +0100 +++ b/slides/slides05.tex Sat Oct 08 13:45:30 2016 +0100 @@ -12,7 +12,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 05, King's College London} +\renewcommand{\slidecaption}{CFL 05, King's College London} \begin{document} @@ -22,7 +22,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-2mm] \LARGE Formal Languages (5)\\[3mm] \end{tabular}} @@ -48,8 +48,8 @@ \begin{columns} \begin{column}{3cm} \begin{tabular}{@{}rrl@{}} - \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\ - & \bl{$\mid$} & \bl{$\epsilon$} \\ + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ + & \bl{$\mid$} & \bl{$\ONE$} \\ & \bl{$\mid$} & \bl{$c$} \\ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ @@ -108,9 +108,9 @@ \small \begin{tabular}{ll} \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ -\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ -\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ -\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ +\bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ +\bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ +\bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ \end{tabular} \end{bubble} \end{textblock} @@ -179,9 +179,9 @@ \end{center} \small -\hspace{4.5cm}\bl{$(b \cdot c) + (\varnothing + \epsilon)$} +\hspace{4.5cm}\bl{$(b \cdot c) + (\ZERO + \ONE)$} $\mapsto$ -\bl{$(b \cdot c) + \epsilon$} +\bl{$(b \cdot c) + \ONE$} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -193,13 +193,13 @@ \bl{$\only<1>{(b \cdot c)}% \only<2-3>{(\underline{b \cdot c})}% \only<1-3>{+}% - \only<1>{(\varnothing + \epsilon)}% - \only<2-3>{(\underline{\varnothing + \epsilon})}$}% + \only<1>{(\ZERO + \ONE)}% + \only<2-3>{(\underline{\ZERO + \ONE})}$}% \only<4->{% -\bl{$\underline{(b \cdot c) + (\varnothing + \epsilon)}$}% +\bl{$\underline{(b \cdot c) + (\ZERO + \ONE)}$}% } $\mapsto$ -\bl{$(b \cdot c) + \epsilon$} +\bl{$(b \cdot c) + \ONE$} \end{center}\bigskip \onslide<3->{% diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 3056a4c071b0 -r e7d0157f0471 slides/slides06.tex --- a/slides/slides06.tex Fri Oct 07 22:08:03 2016 +0100 +++ b/slides/slides06.tex Sat Oct 08 13:45:30 2016 +0100 @@ -6,7 +6,9 @@ % beamer stuff -\renewcommand{\slidecaption}{AFL 06, King's College London} +\renewcommand{\slidecaption}{CFL 06, King's College London} + + \newcommand{\bl}[1]{\textcolor{blue}{#1}} %\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions \newcommand{\qq}{\mbox{\texttt{"}}} @@ -18,7 +20,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-2mm] \LARGE Formal Languages (6)\\[3mm] \end{tabular}}