afl-material: comparison slides/slides03.tex

equal deleted inserted replaced

-:3056a4c071b0
+:e7d0157f0471
 \pgfplotsset{compat=1.11}
 \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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{%
 \begin{tabular}{@ {}c@ {}}
 \\[-3mm]
-\LARGE Automata and \\[-2mm]
+\LARGE Compilers and \\[-2mm]
 \LARGE Formal Languages (3)\\[3mm]
 \end{tabular}}
 \normalsize
 \begin{center}
 Slides: & KEATS (also home work and coursework is there)\\
 \end{tabular}
 \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]
 \frametitle{Regular Expressions}
 \begin{frame}[c]
 \frametitle{The Derivative of a Rexp}
 \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\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\
-\bl{$der\, c\, (\epsilon)$}           & \bl{$\dn$} & \bl{$\varnothing$} & \\
+\bl{$der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\
-\bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\
+\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$}\\
 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
 \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
 \begin{center}
 \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?}}
 \end{center}
 \begin{center}
 \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}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \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
 holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
 \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
 \begin{frame}[t]
 \frametitle{Regular Expressions}
 \begin{center}
 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-\bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
+\bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & null\\
-& \bl{$\mid$} & \bl{$\epsilon$}        & empty string / "" / $[]$\\
+& \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\\
 & \bl{$\mid$} & \bl{$r^*$}                   & star (zero or more)\\
 \end{tabular}
 \begin{frame}[c]
 \frametitle{Rexp to NFA}
 \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}\\\\
 \raisebox{2mm}{\bl{$c$}} &
 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
 \frametitle{Removing Dead States}
 \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,
 draw=blue!50,very thick,fill=blue!20}]
 \node[state,initial,accepting]  (q012)  {$\{0,1,2\}$};
 ;
 \end{tikzpicture}
 \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$}\\
 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
 \end{center}\bigskip
 \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$}\\
 \end{tabular}
 \end{center}
 Given the function
 \begin{center}
 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
-$rev(\varnothing)$   & $\dn$ & $\varnothing$\\
+$rev(\ZERO)$   & $\dn$ & $\ZERO$\\
-$rev(\epsilon)$         & $\dn$ & $\epsilon$\\
+$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)$\\
 $rev(r^*)$                   & $\dn$ & $rev(r)^*$\\
 \end{tabular}}

changeset 445	e7d0157f0471
parent 348	31e89128ccd2
child 500	c502933be072