\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{../slides}
\usepackage{../graphics}
\usepackage{../langs}
\usepackage{../data}
\hfuzz=220pt
\pgfplotsset{compat=1.11}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
\renewcommand{\slidecaption}{AFL 03, King's College London}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Automata and \\[-2mm]
\LARGE Formal Languages (3)\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{lp{8cm}}
Email: & christian.urban at kcl.ac.uk\\
Office: & S1.27 (1st floor Strand Building)\\
Slides: & KEATS (also home work and coursework is there)\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
In programming languages they are often used to recognise:\medskip
\begin{itemize}
\item symbols, digits
\item identifiers
\item numbers (non-leading zeros)
\item keywords
\item comments
\end{itemize}\bigskip
\mbox{}\hfill\bl{\url{http://www.regexper.com}}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Last Week}
Last week I showed you a regular expression matcher
which works provably correct in all cases (we did not
do the proving part though)
\begin{center}
\bl{$matches\,r\,s$} \;\;if and only if \;\; \bl{$s \in L(r)$}
\end{center}\bigskip\bigskip
\small
\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\, (\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^*)$} &\medskip\\
\bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
\bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
To see what is going on, define
\begin{center}
\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
\end{center}\bigskip\bigskip
For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
\begin{center}
\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$\\
\end{tabular}}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Idea of the Algorithm}
If we want to recognise the string \bl{$abc$} with regular expression \bl{$r$}
then\medskip
\begin{enumerate}
\item \bl{$Der\,a\,(L(r))$}\pause
\item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause
\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\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 expressions instead of sets.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
Input: string \bl{$abc$} and regular expression \bl{$r$}
\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 last regular expression can match the empty string
\end{enumerate}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
We proved already
\begin{center}
\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$}
\end{center}
by induction on the regular expression.\bigskip\pause
\begin{center}
{\huge\bf\alert{Any Questions?}}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
We need to prove
\begin{center}
\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
\end{center}
by induction on the regular expression.
\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{$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
holds for \bl{$r$}.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
\begin{itemize}
\item \bl{$P$} holds for \bl{$0$} and
\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already
holds for \bl{$n$}
\end{itemize}\bigskip
\begin{itemize}
\item \bl{$P$} holds for \bl{$[]$} and
\item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
holds for \bl{$s$}
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Languages}
A \alert{language} is a set of strings.\bigskip
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^nb^n$} is not}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Regular Expressions}
\begin{center}
\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{center}
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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Negation of Regular Expr's}
\begin{itemize}
\item \bl{$\sim{}r$} \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip
\item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
\item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip
\item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
\end{itemize}\bigskip\pause
Used often for recognising comments:
\[
\bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
\]
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Negation}
Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.
Find a (basic!) regular expression that matches all strings \emph{\alert{except}}
\bl{$ab$} and \bl{$ac$}!
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\mode<presentation>{
%\begin{frame}[c]
%\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
%
%Lexing separates strings into ``words'' / components.
%
%\begin{itemize}
%\item Identifiers (non-empty strings of letters or digits, starting with a letter)
%\item Numbers (non-empty sequences of digits omitting leading zeros)
%\item Keywords (else, if, while, \ldots)
%\item White space (a non-empty sequence of blanks, newlines and tabs)
%\item Comments
%\end{itemize}
%
%\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Automata}
A \alert{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 be everywhere defined
\end{itemize}
\begin{center}
\bl{$A(Q, q_0, F, \delta)$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (q_0) {$q_0$};
\node[state] (q_1) [right=of q_0] {$q_1$};
\node[state] (q_2) [below right=of q_0] {$q_2$};
\node[state] (q_3) [right=of q_2] {$q_3$};
\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1);
\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4);
\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} ();
\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4);
\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3);
\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2);
\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2);
\path[->] (q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);
\end{tikzpicture}
\end{center}\pause
\begin{itemize}
\item the start state can be an accepting state
\item it is possible that there is no accepting state
\item all states might be accepting (but this does not necessarily mean all strings are accepted)
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (q_0) {$q_0$};
\node[state] (q_1) [right=of q_0] {$q_1$};
\node[state] (q_2) [below right=of q_0] {$q_2$};
\node[state] (q_3) [right=of q_2] {$q_3$};
\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1);
\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4);
\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} ();
\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4);
\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3);
\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2);
\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2);
\path[->] (q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);
\end{tikzpicture}
\end{center}
for this automaton \bl{$\delta$} is the function\\
\begin{center}
\begin{tabular}{lll}
\bl{$(q_0, a) \rightarrow q_1$} & \bl{$(q_1, a) \rightarrow q_4$} & \bl{$(q_4, a) \rightarrow q_4$}\\
\bl{$(q_0, b) \rightarrow q_2$} & \bl{$(q_1, b) \rightarrow q_2$} & \bl{$(q_4, b) \rightarrow q_4$}\\
\end{tabular}\ldots
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Accepting a String}
Given
\begin{center}
\bl{$A(Q, q_0, F, \delta)$}
\end{center}
you can define
\begin{center}
\begin{tabular}{l}
\bl{$\hat{\delta}(q, []) \dn q$}\\
\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\
\end{tabular}
\end{center}\pause
Whether a string \bl{$s$} is accepted by \bl{$A$}?
\begin{center}
\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}
A non-deterministic finite automaton consists again of:
\begin{itemize}
\item a finite set of states
\item one of these states is the start state
\item some states are accepting states, and
\item there is transition \alert{relation}\medskip
\end{itemize}
\begin{center}
\begin{tabular}{c}
\bl{$(q_1, a) \rightarrow q_2$}\\
\bl{$(q_1, a) \rightarrow q_3$}\\
\end{tabular}
\hspace{10mm}
\begin{tabular}{c}
\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Two NFA Examples}
\begin{center}
\begin{tabular}[t]{c@{\hspace{9mm}}c}
\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] (q_0) {$q_0$};
\node[state] (q_1) [above=of q_0] {$q_1$};
\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture} &
\raisebox{20mm}{
\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] (r_1) {$r_1$};
\node[state] (r_2) [above=of r_1] {$r_2$};
\node[state, accepting] (r_3) [right=of r_1] {$r_3$};
\path[->] (r_1) edge node [below] {\alert{$b$}} (r_3);
\path[->] (r_2) edge [bend left] node [above] {\alert{$a$}} (r_3);
\path[->] (r_1) edge [bend left] node [left] {\alert{$\epsilon$}} (r_2);
\path[->] (r_2) edge [bend left] node [right] {\alert{$a$}} (r_1);
\end{tikzpicture}}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Rexp to NFA}
\begin{center}
\begin{tabular}[t]{l@{\hspace{10mm}}l}
\raisebox{1mm}{\bl{$\varnothing$}} &
\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$}} &
\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},]
\node[state, initial] (q_0) {$\mbox{}$};
\node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$};
\path[->] (q_0) edge node [below] {\alert{$c$}} (q_1);
\end{tikzpicture}\\\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Case $r_1\cdot r_2$}
\mbox{}\bigskip
\onslide<1>{By recursion we are given two automata:\bigskip}
{\centering\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (q_0) {$\mbox{}$};
\node (r_1) [right=of q_0] {$\ldots$};
\only<1>{
\node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$};
\node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$};
\node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};}
\only<2>{
\node[state] (t_1) [right=of r_1] {$\mbox{}$};
\node[state] (t_2) [above=of t_1] {$\mbox{}$};
\node[state] (t_3) [below=of t_1] {$\mbox{}$};}
\only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
\only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
\node (b_1) [right=of a_0] {$\ldots$};
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
\only<2>{
\path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0);
\path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0);
\path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0);
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};}
\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};}
\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};}
\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}
\end{pgfonlayer}
\end{tikzpicture}}\bigskip\bigskip
\small
We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them
via $\epsilon$-transitions to the starting state of the second automaton.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Case $r_1+ r_2$}
\mbox{}\\[-10mm]
\onslide<1>{By recursion we are given two automata:\smallskip}
\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
\onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};}
\only<1>{
\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};
\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};}
\only<2>{
\node[state] (2) [above right=16mm of 1] {$\mbox{}$};
\node[state] (3) [below right=16mm of 1] {$\mbox{}$};}
\node (a) [right=of 2] {$\ldots$};
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
\node (b) [right=of 3] {$\ldots$};
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
\only<2>{
\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
\path[->] (1) edge node [below] {\alert{$\epsilon$}} (3);
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}
\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}
\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}
\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}
\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}
\end{pgfonlayer}
\end{tikzpicture}
\small
We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Case $r^*$}
\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
\onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};}
\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};}
\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
\node (a) [right=of 2] {$\ldots$};
\only<1>{
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};}
\only<2->{
\node[state] (a1) [right=of a] {$\mbox{}$};
\node[state] (a2) [above=of a1] {$\mbox{}$};
\node[state] (a3) [below=of a1] {$\mbox{}$};}
\only<2->{
\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
\path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1);
\path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1);
\path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1);
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
\end{pgfonlayer}
\end{tikzpicture}\bigskip
\onslide<3->{
Why can't we just have an epsilon transition from the accepting states to the starting state?}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
\begin{textblock}{5}(1,1)
\begin{center}
\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] (q_0) {$q_0$};
\node[state] (q_1) [above=of q_0] {$q_1$};
\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{center}
\end{textblock}
\begin{textblock}{11}(6.5,4.5)
\begin{tabular}{r|cl}
nodes \textcolor{white}{*} & $a$ & $b$\\
\hline
$\varnothing$ \textcolor{white}{*} & \onslide<2->{$\varnothing$} & \onslide<2->{$\varnothing$}\\
$\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0,1,2\}$} & \onslide<3->{$\{2\}$}\\
$\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\varnothing$}\\
$\{2\}$ \onslide<5->{*} & \onslide<3->{$\varnothing$} & \onslide<3->{$\{2\}$}\\
$\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
$\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
$\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{1\}$} & \onslide<4->{$\{2\}$}\\
\onslide<5->{s:} $\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
\end{tabular}
\end{textblock}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regexps and Automata}
\begin{center}
\begin{tikzpicture}
\node (rexp) {\bl{\bf Regexps}};
\node (nfa) [right=of rexp] {\bl{\bf NFAs}};
\node (dfa) [right=of nfa] {\bl{\bf DFAs}};
\onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}
\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
\onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}
\onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);}
\end{tikzpicture}\\
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
A language is \alert{regular} iff there exists
a regular expression that recognises all its strings.\bigskip\medskip
or {\bf equivalently}\bigskip\medskip
A language is \alert{regular} iff there exists
a deterministic finite automaton that recognises all its strings.\bigskip\medskip\pause
Why is every finite set of strings a regular language?
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<2>[c]
\frametitle{DFA to Rexp}
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};}
\only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
\only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
\only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
(q1) edge[bend left] node[above] {\alert{$b$}} (q0)
(q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
(q1) edge node[above] {\alert{$a$}} (q2)
(q2) edge [loop right] node {\alert{$a$}} ()
(q0) edge [loop below] node {\alert{$b$}} ()
;
\end{tikzpicture}
\end{center}
\onslide<3>{How to get from a DFA to a regular expression?}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
(q1) edge[bend left] node[above] {\alert{$b$}} (q0)
(q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
(q1) edge node[above] {\alert{$a$}} (q2)
(q2) edge [loop right] node {\alert{$a$}} ()
(q0) edge [loop below] node {\alert{$b$}} ()
;
\end{tikzpicture}
\end{center}\pause\bigskip
\onslide<2->{
\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{tabular}
\end{center}
}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
(q1) edge[bend left] node[above] {\alert{$b$}} (q0)
(q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
(q1) edge node[above] {\alert{$a$}} (q2)
(q2) edge [loop right] node {\alert{$a$}} ()
(q0) edge [loop below] node {\alert{$b$}} ()
;
\end{tikzpicture}
\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_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
\end{tabular}
\end{center}
}
\onslide<3->{
Arden's Lemma:
\begin{center}
If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
\end{center}
}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
Given the function
\begin{center}
\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
$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}}
\end{center}
and the set
\begin{center}
\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}
\end{center}
prove whether
\begin{center}
\bl{$L(rev(r)) = Rev (L(r))$}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: