afl-material: comparison slides/slides03.tex

equal deleted inserted replaced

-:09efdf5cf07c
+:e3a8cf96f570
 %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
 %\end{center}
 \normalsize
 \begin{center}
-\begin{tabular}{ll}
+\begin{tabular}{lp{8cm}}
 Email:  & christian.urban at kcl.ac.uk\\
 Office: & S1.27 (1st floor Strand Building)\\
-Slides: & KEATS (also home work is there)\\
+Slides: & KEATS (also home work and coursework is there)\\
 \end{tabular}
 \end{center}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
-They are often used to recognise:\medskip
+In programming languages they are often used to recognise:\medskip
 \begin{itemize}
 \item symbols, digits
 \item identifiers
 \item numbers (non-leading zeros)
 \mode<presentation>{
 \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.
+which works provably correctly in all cases.
 \begin{center}
 \bl{$matcher\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}
 \end{center}\bigskip\bigskip
 \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.
+The matching algorithm works similarly, just over regular expression instead of sets.
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{enumerate}
 \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
+\item finally check whether the last regular expression can match the empty string
 \end{enumerate}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{center}
 \bl{$nullable(r)$} \;if and only if\;  \bl{$"" \in L(r)$}
 \end{center}
-by induction on the regular expression.
+by induction on the regular expression.\bigskip\pause
+\begin{center}
+\huge\bf \alert{Any Questions?}
+\end{center}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{center}
 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
 \end{center}
 by induction on the regular expression.
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 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
-\textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.}
+\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \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{$r$} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
-& \bl{$\mid$} & \bl{$\epsilon$}        & empty string / "" / []\\
+& \bl{$\mid$} & \bl{$\epsilon$}        & empty string / "" / $[]$\\
-& \bl{$\mid$} & \bl{c}                         & character\\
+& \bl{$\mid$} & \bl{$c$}                         & character\\
-& \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
+& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
-& \bl{$\mid$} & \bl{r$_1$ + r$_2$}  & alternative / choice\\
+& \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
-& \bl{$\mid$} & \bl{r$^*$}                   & star (zero or more)\\
+& \bl{$\mid$} & \bl{$r^*$}                   & star (zero or more)\\
-\end{tabular}\bigskip
+\end{tabular}
 \end{center}
-How about ranges \bl{[a-z]}, \bl{r$^\text{+}$} and \bl{!r}?
+How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the
+set of languages we can recognise?
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}}
 \begin{itemize}
-\item \bl{!r}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
+\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
-\item \bl{$L$(!r) $\dn$ UNIV - $L$(r)}\medskip
+\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
-\item \bl{nullable (!r) $\dn$ not (nullable(r))}\medskip
+\item \bl{$nullable (r) \dn not (nullable(r))$}\medskip
-\item \bl{der\,c\,(!r) $\dn$ !(der\,c\,r)}
+\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
-\end{itemize}
+\end{itemize}\bigskip\pause
-\end{frame}}
+Used often for comments:
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\[
+\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
+\]
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
+\end{frame}}
-\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<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}

changeset 134	e3a8cf96f570
parent 133	09efdf5cf07c
child 135	72b686e1c974