\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{beamerthemeplainculight}
\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{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

\lstset{language=Java,
	basicstyle=\ttfamily,
	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=\ttfamily,
	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 04, King's College London, 17.~October 2012}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

\begin{document}

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

  \normalsize
  \begin{center}
  \begin{tabular}{ll}
  Email:  & christian.urban at kcl.ac.uk\\
  Of$\!$fice: & S1.27 (1st floor Strand Building)\\
  Slides: & KEATS (also home work is there)\\
  \end{tabular}
  \end{center}


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

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

Last week I showed you\bigskip

\begin{itemize}
\item a tokenizer taking a list of regular expressions\bigskip

\item tokenization identifies lexeme in an input stream of characters (or string)
and cathegorizes  them into tokens

\end{itemize}

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

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

\begin{itemize}
\item Longest match rule (maximal munch rule): The 
longest initial substring matched by any regular expression is taken
as next token.\bigskip

\item Rule priority:
For a particular longest initial substring, the first regular
expression that can match determines the token.

\end{itemize}

%\url{http://www.technologyreview.com/tr10/?year=2011}
  
%finite deterministic automata/ nondeterministic automaton

%\item problem with infix operations, for example i-12


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

\mode<presentation>{
\begin{frame}[t]

\begin{center}
\texttt{"if true then then 42 else +"}
\end{center}


\begin{tabular}{@{}l}
KEYWORD: \\
\hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ 
WHITESPACE:\\
\hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ 
IDENT:\\
\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ 
NUM:\\
\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
OP:\\
\hspace{5mm}\texttt{"+"}\\
COMMENT:\\
\hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"}
\end{tabular}

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

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

\begin{center}
\texttt{"if true then then 42 else +"}
\end{center}

\only<1>{
\small\begin{tabular}{l}
KEYWORD(if),\\ 
WHITESPACE,\\ 
IDENT(true),\\ 
WHITESPACE,\\ 
KEYWORD(then),\\ 
WHITESPACE,\\ 
KEYWORD(then),\\ 
WHITESPACE,\\ 
NUM(42),\\ 
WHITESPACE,\\ 
KEYWORD(else),\\ 
WHITESPACE,\\ 
OP(+)
\end{tabular}}

\only<2>{
\small\begin{tabular}{l}
KEYWORD(if),\\ 
IDENT(true),\\ 
KEYWORD(then),\\ 
KEYWORD(then),\\ 
NUM(42),\\ 
KEYWORD(else),\\ 
OP(+)
\end{tabular}}

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

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


There is one small problem with the tokenizer. How should we 
tokenize:

\begin{center}
\texttt{"x - 3"}
\end{center}

\begin{tabular}{@{}l}
OP:\\
\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
NUM:\\
\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\
NUMBER:\\
\hspace{5mm}NUM +  (\texttt{"-"} $\cdot$ NUM)\\
\end{tabular}


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

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

Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.
Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}.

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



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

A deterministic finite automaton consists 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 function\medskip 

\small
which takes a state and a character as arguments and produces a new state\smallskip\\
this function might not always be defined everywhere
\end{itemize}

\begin{center}
\bl{$A(Q, q_0, F, \delta)$}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   


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

\begin{center}
\includegraphics[scale=0.7]{pics/ch3.jpg}
\end{center}\pause

\begin{itemize}
\item start can be an accepting state
\item there is no accepting state
\item all states are accepting
\end{itemize}

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

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

\begin{center}
\includegraphics[scale=0.7]{pics/ch3.jpg}
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



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

Given

\begin{center}
\bl{$A(Q, q_0, F, \delta)$}
\end{center}

you can define

\begin{center}
\begin{tabular}{l}
\bl{$\hat{\delta}(q, \texttt{""}) = q$}\\
\bl{$\hat{\delta}(q, c::s) = \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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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

\begin{center}
\includegraphics[scale=0.7]{pics/ch5.jpg}
\end{center}


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

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

\begin{center}
\begin{tabular}[b]{ll}
\bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\
\bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\
\bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\
\end{tabular}
\end{center}

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

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

\begin{center}
\begin{tabular}[t]{ll}
\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\
\end{tabular}
\end{center}

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

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

\begin{center}
\begin{tabular}[t]{ll}
\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\
\end{tabular}
\end{center}

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

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

\begin{center}
\begin{tabular}[b]{ll}
\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
\end{tabular}
\end{center}\pause\bigskip

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,2.5)
\includegraphics[scale=0.5]{pics/ch5.jpg}
\end{textblock}

\begin{textblock}{11}(6.5,4.5)
\begin{tabular}{r|cl}
& a & b\\
\hline
$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\
$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\
$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\
$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\
$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\
$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\
\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
\end{tabular}
\end{textblock}


\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 equivalently\bigskip\medskip

A language is \alert{regular} iff there exists
a deterministic finite automaton that recognises all its strings.\bigskip\pause

Why is every finite set of strings a regular language?
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   



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

\begin{center}
\includegraphics[scale=0.5]{pics/ch3.jpg}
\end{center}

\begin{center}
\includegraphics[scale=0.5]{pics/ch4.jpg}\\
minimal automaton
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

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

\begin{itemize}
\item The star-case in our proof about the matcher needs the following lemma
\begin{center}
\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}
\end{center}
\end{itemize}\bigskip\bigskip

\begin{itemize}
\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip
\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}

\end{itemize}

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


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

\begin{itemize}
\item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip
\item Give a regular expression that can recognise all strings that have at least one \bl{b}.
\end{itemize}

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

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

Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.
(a) Find a regular expression that recognises the two strings \bl{$ab$} and \bl{$ac$}. (b)
Find a regular expression that matches all strings \emph{except} these two strings.
Note, you can only use regular expressions of the form 
\begin{center}
\bl{$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$}
\end{center}

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


\end{document}

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