# HG changeset patch # User Christian Urban # Date 1474702668 -3600 # Node ID 7e71c947ec69af94936d328fbe30748f8da902cc # Parent a47c4227a0c6715cff85d0b494b137d3066161ee updated diff -r a47c4227a0c6 -r 7e71c947ec69 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r a47c4227a0c6 -r 7e71c947ec69 slides/slides02.tex --- a/slides/slides02.tex Sat Sep 24 08:31:04 2016 +0100 +++ b/slides/slides02.tex Sat Sep 24 08:37:48 2016 +0100 @@ -17,7 +17,7 @@ \newcommand{\bl}[1]{\textcolor{blue}{#1}} % beamer stuff -\renewcommand{\slidecaption}{AFL 02, King's College London} +\renewcommand{\slidecaption}{CFL 02, King's College London} \begin{document} @@ -27,7 +27,7 @@ \frametitle{% \begin{tabular}{@ {}c@ {}} \\[-3mm] - \LARGE Automata and \\[-2mm] + \LARGE Compilers and \\[-1mm] \LARGE Formal Languages (2)\\[3mm] \end{tabular}} @@ -236,7 +236,7 @@ \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ $Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ -$Der\,a\,A$ & $=$ & $\varnothing$\\\pause +$Der\,a\,A$ & $=$ & $\{\}$\\\pause \end{tabular}} \end{center} @@ -260,8 +260,8 @@ \begin{textblock}{6}(2,7.5) \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} - \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ - & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\ + \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\ + & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ & \bl{$\mid$} & \bl{$c$} & character\\ & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ @@ -286,8 +286,8 @@ \begin{textblock}{15}(1,4) \begin{tabular}{@ {}rcl} - \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ - \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \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)$}\\ @@ -353,11 +353,11 @@ \begin{center} \bl{\begin{tabular}{rcl} -$a \cdot \varnothing$ & $\not\equiv$ & $a$\\ -$a + \epsilon$ & $\not\equiv$ & $a$\\ -$\epsilon$ & $\equiv$ & $\varnothing^*$\\ -$\epsilon^*$ & $\equiv$ & $\epsilon$\\ -$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\ +$a \cdot \ZERO$ & $\not\equiv$ & $a$\\ +$a + \ONE$ & $\not\equiv$ & $a$\\ +$\ONE$ & $\equiv$ & $\ZERO^*$\\ +$\ONE^*$ & $\equiv$ & $\ONE$\\ +$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\ \end{tabular}} \end{center} @@ -370,12 +370,12 @@ \begin{center} \bl{\begin{tabular}{rcl} -$r + \varnothing$ & $\equiv$ & $r$\\ -$\varnothing + r$ & $\equiv$ & $r$\\ -$r \cdot \epsilon$ & $\equiv$ & $r$\\ -$\epsilon \cdot r$ & $\equiv$ & $r$\\ -$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\ -$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\ +$r + \ZERO$ & $\equiv$ & $r$\\ +$\ZERO + r$ & $\equiv$ & $r$\\ +$r \cdot \ONE$ & $\equiv$ & $r$\\ +$\ONE \cdot r$ & $\equiv$ & $r$\\ +$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\ +$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\ $r + r$ & $\equiv$ & $r$ \end{tabular}} \end{center} @@ -403,7 +403,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -442,7 +442,7 @@ \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip \item Evil regular expressions\medskip \begin{itemize} -\item \bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$} +\item \bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$} \item \bl{$(a^+)^+$} \item \bl{$([a$\,-\,$z]^+)^*$} \item \bl{$(a + a \cdot a)^+$} @@ -461,8 +461,8 @@ \ldots{}whether a regular expression can match the empty string: \begin{center} \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} -\bl{$nullable(\varnothing)$} & \bl{$\dn$} & \bl{\textit{false}}\\ -\bl{$nullable(\epsilon)$} & \bl{$\dn$} & \bl{\textit{true}}\\ +\bl{$nullable(\ZERO)$} & \bl{$\dn$} & \bl{\textit{false}}\\ +\bl{$nullable(\ONE)$} & \bl{$\dn$} & \bl{\textit{true}}\\ \bl{$nullable (c)$} & \bl{$\dn$} & \bl{\textit{false}}\\ \bl{$nullable (r_1 + r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \vee nullable(r_2)$} \\ \bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$} \\ @@ -493,9 +493,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$}\\ @@ -572,7 +572,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] -\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -624,7 +624,7 @@ \end{center} This problem is aggravated with \bl{$a^?$} being represented -as \bl{$\epsilon + a$}. +as \bl{$\ONE + a$}. \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -649,7 +649,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -692,9 +692,9 @@ \begin{center} \begin{tabular}{l} -\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\ -\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\ -\bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$} +\bl{$der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\ +\bl{$der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\ +\bl{$der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$} \end{tabular} \end{center} @@ -707,7 +707,7 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] -\frametitle{\bl{$(a^?^{\{n\}}) \cdot a^{\{n\}}$}} +\frametitle{\bl{$({a^?}^{\{n\}}) \cdot a^{\{n\}}$}} \begin{center} \begin{tikzpicture} @@ -760,8 +760,8 @@ \begin{textblock}{6}(5,5) \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$} \\ @@ -779,7 +779,7 @@ \frametitle{Proofs about Rexp (2)} \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 @@ -810,8 +810,8 @@ \begin{center} \bl{\begin{tabular}{r@{\hspace{2mm}}c@{\hspace{2mm}}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)$\\