\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{beamerthemeplaincu}
%%\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{mathpartir}
\usepackage[absolute,overlay]{textpos}
\usepackage{ifthen}
\usepackage{tikz}
\usepackage{pgf}
\usepackage{calc} 
\usepackage{ulem}
\usepackage{courier}
\usepackage{listings}
\renewcommand{\uline}[1]{#1}
\usetikzlibrary{arrows}
\usetikzlibrary{automata}
\usetikzlibrary{shapes}
\usetikzlibrary{shadows}
\usetikzlibrary{positioning}
\usetikzlibrary{plotmarks}
\usetikzlibrary{calc}
\usepackage{graphicx} 

\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc

\makeatletter
\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
\@empty\z@\@empty
\makeatother

\lstset{language=Java,
	basicstyle=\consolas,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javagreen},
	commentstyle=\color{javagreen},
	morecomment=[s][\color{javadocblue}]{/**}{*/},
	numbers=left,
	numberstyle=\tiny\color{black},
	stepnumber=1,
	numbersep=10pt,
	tabsize=2,
	showspaces=false,
	showstringspaces=false}

\lstdefinelanguage{scala}{
  morekeywords={abstract,case,catch,class,def,%
    do,else,extends,false,final,finally,%
    for,if,implicit,import,match,mixin,%
    new,null,object,override,package,%
    private,protected,requires,return,sealed,%
    super,this,throw,trait,true,try,%
    type,val,var,while,with,yield},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@,->},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}

\lstset{language=Scala,
	basicstyle=\consolas,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javagreen},
	commentstyle=\color{javagreen},
	morecomment=[s][\color{javadocblue}]{/**}{*/},
	numbers=left,
	numberstyle=\tiny\color{black},
	stepnumber=1,
	numbersep=10pt,
	tabsize=2,
	showspaces=false,
	showstringspaces=false}

% beamer stuff 
\renewcommand{\slidecaption}{AFL 02, King's College London, 2.~October 2013}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

% The data files, written on the first run.
\begin{filecontents}{re-python.data}
1 0.029
5 0.029
10 0.029
15 0.032
16 0.042
17 0.042
18 0.055
19 0.084
20 0.136
21 0.248
22 0.464
23 0.899
24 1.773
25 3.505
26 6.993
27 14.503
28 29.307
#29 58.886
\end{filecontents}

\begin{filecontents}{re-ruby.data}
1 0.00006
2 0.00003
3 0.00001
4 0.00001
5 0.00001
6 0.00002
7 0.00002
8 0.00004
9 0.00007
10 0.00013
11 0.00026
12 0.00055
13 0.00106
14 0.00196
15 0.00378
16 0.00764
17 0.01606
18 0.03094
19 0.06508
20 0.12420
21 0.25393
22 0.51449
23 1.02174
24 2.05998
25 4.22514
26 8.42479
27 16.88678
28 34.79653
\end{filecontents}


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<1>[t]
\frametitle{%
  \begin{tabular}{@ {}c@ {}}
  \\[-3mm]
  \LARGE Automata and \\[-2mm] 
  \LARGE Formal Languages (2)\\[3mm] 
  \end{tabular}}

  %\begin{center}
  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\
  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
  %\end{center}

\normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Office: & S1.27 (1st floor Strand Building)\\
  Slides: & KEATS 
  \end{tabular}
  \end{center}


\end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Languages\end{tabular}}

A \alert{language} is a set of strings.\bigskip

A \alert{regular expression} specifies a set of strings, or language.
  
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Strings\end{tabular}}

Different ways of writing strings:

\begin{center}
\begin{tabular}{ccc}
\bl{\consolas"$hello$"}\quad{} &  \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\
\bl{\consolas ""}       &       \bl{$[]$}                & \bl{$N$\!$il$}
\end{tabular}
\end{center}\pause

The concatenation operation on strings and sets of strings:

\begin{center}
\begin{tabular}{l}
\bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\
\bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$}
\end{tabular}
\end{center}
  
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}

Their inductive definition:


\begin{textblock}{6}(2,6.5)
  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / {\consolas""} / $[]$\\
         & \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{textblock}
  
  
\only<2->{
\begin{textblock}{9}(4,0.5)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
{\normalsize\color{darkgray}
\begin{minipage}{9cm}
\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
\texttt{\lstinputlisting{../progs/app51.scala}}}}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}
  
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}

\begin{textblock}{15}(1,4)
 \begin{tabular}{@ {}rcl}
 \bl{$L(\varnothing)$}     & \bl{$\dn$} & \bl{$\varnothing$}\\
 \bl{$L(\epsilon)$}          & \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)$}\\
 \bl{$L(r^*)$}                   & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\
  \end{tabular}\bigskip
  
\only<2->{  
\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\
\textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}}  
\end{textblock}



\only<1->{
\begin{textblock}{6}(9,12)\small
\bl{$L$} is a function from regular expressions to sets of strings\\
\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
\end{textblock}}


\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]

\large
\begin{center}
What is \bl{$L(a^*)$}?
\end{center}  
  
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



\newcommand{\YES}{\textcolor{gray}{yes}}
\newcommand{\NO}{\textcolor{gray}{no}}
\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}}

\begin{center}
\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l}
&\bl{$(a + b)  + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\
&\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\
&\bl{$(a \cdot b)  \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\
&\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\
&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\
&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\
\FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\
\FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\
\FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\
\FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\
&\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\
&\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES}
\end{tabular}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Specification\\[-1mm] of Matching\end{tabular}}

\large
a regular expression \bl{r} matches a string \bl{s} is defined as

\begin{center}
\bl{s $\in$ $L$(r)}\\ 
\end{center}\bigskip\bigskip\pause

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}

\mbox{}\\[-13mm]

\begin{tikzpicture}[y=.2cm, x=.3cm]
 	%axis
	\draw (0,0) -- coordinate (x axis mid) (30,0);
    	\draw (0,0) -- coordinate (y axis mid) (0,30);
    	%ticks
    	\foreach \x in {0,5,...,30}
     		\draw (\x,1pt) -- (\x,-3pt)
			node[anchor=north] {\x};
    	\foreach \y in {0,5,...,30}
     		\draw (1pt,\y) -- (-3pt,\y) 
     			node[anchor=east] {\y}; 
	%labels      
	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};

	%plots
	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
		file {re-python.data};
	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
		file {re1.data};
         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
		file {re2.data};
         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
		file {re-ruby.data};
    
	%legend
	\begin{scope}[shift={(4,20)}] 
	\draw[color=blue] (0,0) -- 
		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
		node[right]{\small Python};
	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
		node[right]{\small Ruby};
	\end{scope}
\end{tikzpicture}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Evil Regular Expressions\end{tabular}}

\begin{itemize}
\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^+)^+$}
\item \bl{$([a$\,-\,$z]^+)^*$}
\item \bl{$(a + a \cdot a)^+$}
\item \bl{$(a + a?)^+$}
\end{itemize}
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}

\small
\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{$f\!\/alse$}\\
\bl{$nullable(\epsilon)$}           & \bl{$\dn$} &  \bl{$true$}\\
\bl{$nullable (c)$}                    & \bl{$\dn$} &  \bl{$f\!alse$}\\
\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)$} \\
\bl{$nullable (r^*)$}                 & \bl{$\dn$} & \bl{$true$} \\
\end{tabular}
\end{center}

\only<2->{
\begin{textblock}{9}(3.4,10)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
{\normalsize\color{darkgray}
\begin{minipage}{9cm}
\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
\texttt{\lstinputlisting{../progs/app5.scala}}}}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}
  
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}

\large
If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip

\small
\bl{$der\,c\,r$} gives the answer
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Derivative of a Rexp (2)\end{tabular}}

\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^*)$} &\smallskip\\\pause

  \bl{$der\!s\, [] r$}     & \bl{$\dn$} & \bl{$r$} & \\
  \bl{$der\!s\, (c\!::\!s) r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
  \end{tabular}
\end{center}

\only<3->{
\begin{textblock}{10.5}(2,5)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
{\normalsize\color{darkgray}
\begin{minipage}{10.5cm}
\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
\texttt{\lstinputlisting{../progs/app6.scala}}}}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}


{\lstset{language=Scala}\fontsize{8}{10}\selectfont
\texttt{\lstinputlisting{../progs/app7.scala}}}



\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}

Remember their inductive definition:\\[5cm]

\begin{textblock}{6}(5,5)
  \begin{tabular}{@ {}rrl}
  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}\\
         & \bl{$\mid$} & \bl{$\epsilon$}       \\
         & \bl{$\mid$} & \bl{c}                        \\
         & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\
         & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  \\
         & \bl{$\mid$} & \bl{r$^*$}                  \\
  \end{tabular}
  \end{textblock}

If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Rexp (2)\end{tabular}}

\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$}.
\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
holds for \bl{r}.
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}}

Assume \bl{$P(r)$} is the property:

\begin{center}
\bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)}
\end{center}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}}

If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip

\begin{itemize}
\item \bl{$P$} holds for the empty string, and\medskip
\item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$}
already holds for \bl{s}
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}}

Let \bl{Der c A} be the set defined as

\begin{center}
\bl{Der c A $\dn$ $\{$ s $|$  c::s $\in$ A$\}$ } 
\end{center}

Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that

\begin{center}
\bl{matcher(r, s)  if and only if  s $\in$ $L$(r)} 
\end{center}


\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}

A language (set of strings) is \alert{regular} iff there exists
a regular expression that recognises all its strings.

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Automata\end{tabular}}

A 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 always be defined
\end{itemize}

\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


\end{document}

%%% Local Variables:  
%%% mode: latex
%%% TeX-master: t
%%% End: 

