\documentclass[dvipsnames,14pt,t]{beamer}

\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 

\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\\

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \end{center}

\end{frame}}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}<1-2>[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}

\mbox{}\\[-20mm]\mbox{}

\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_02)  {$q_{0, 2}$};

\node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

\path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

\path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

\path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

\path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

\end{tikzpicture}\\

minimal automaton

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\begin{enumerate}

\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}

\item Mark all pairs that are accepting and non-accepting states

\item For  all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether

\begin{center}

\bl{($\delta$(q,c), $\delta$(p,c))}

\end{center} 

are marked. If yes, then also mark \bl{(q, p)} 

\item Repeat last step until no chance.

\item All unmarked pairs can be merged.

\end{enumerate}

\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 it is possible that there is no accepting state

\item all states might be accepting (but does not necessarily mean all strings are accepted)

\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}