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

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

\usetikzlibrary{plotmarks}

\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

\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

% 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}{re1.data}

1 0.00179

2 0.00011

3 0.00014

4 0.00026

5 0.00050

6 0.00095

7 0.00190

8 0.00287

9 0.00779

10 0.01399

11 0.01894

12 0.03666

13 0.07994

14 0.08944

15 0.02377

16 0.07392

17 0.22798

18 0.65310

19 2.11360

20 6.31606

21 21.46013

\end{filecontents}

\begin{filecontents}{re2.data}

1  0.00240

2  0.00013

3  0.00020

4  0.00030

5  0.00049

6  0.00083

7  0.00146

8  0.00228

9  0.00351

10  0.00640

11  0.01217

12  0.02565

13  0.01382

14  0.02423

15  0.05065 

16  0.06522

17  0.02140

18  0.05176

19  0.18254

20  0.51898

21  1.39631

22  2.69501

23  8.07952

\end{filecontents}

\begin{filecontents}{re-internal.data}

1 0.00069

301 0.00700

601 0.00297

901 0.00470

1201 0.01301

1501 0.01175

1801 0.01761

2101 0.01787

2401 0.02717

2701 0.03932

3001 0.03470

3301 0.04349

3601 0.05411

3901 0.06181

4201 0.07119

4501 0.08578

\end{filecontents}

\begin{filecontents}{re3.data}

1 0.001605

501 0.131066

1001 0.057885

1501 0.136875

2001 0.176238

2501 0.254363

3001 0.37262

3501 0.500946

4001 0.638384

4501 0.816605

5001 1.00491

5501 1.232505

6001 1.525672

6501 1.757502

7001 2.092784

7501 2.429224

8001 2.803037

8501 3.463045

9001 3.609

9501 4.081504

10001 4.54569

\end{filecontents}

\begin{document}

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

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (6)\\[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}}

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

\newcommand{\qq}{\mbox{\texttt{"}}}

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Grammars\end{tabular}}

A (context-free) grammar \bl{$G$} consists of

\begin{itemize}

\item a finite set of nonterminal symbols (upper case)

\item a finite terminal symbols or tokens (lower case)

\item a start symbol (which must be a nonterminal)

\item a set of rules

\begin{center}

\bl{$A \rightarrow \text{rhs}$}

\end{center}

where \bl{rhs} are sequences involving terminals and nonterminals.\medskip\pause

We can also allow rules

\begin{center}

\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}

\end{center}

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Palindromes\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon$ \\

$S$ & $\rightarrow$ &  $a\cdot S\cdot a$ \\

$S$ & $\rightarrow$ &  $b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}\pause

or

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Arithmetic Expressions\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}\pause

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F$\\

$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\

$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\

\end{tabular}}

\end{center}

\begin{center}

\begin{tikzpicture}[level distance=8mm, blue]

  \node {$E$}

    child {node {$F$} 

     child {node {$T$} 

                 child {node {(\,$E$\,)}

                            child {node{$F$ *{} $F$}

                                  child {node {$T$} child {node {2}}}

                                  child {node {$T$} child {node {3}}} 

                               }

                          }

              }

     child {node {+}}

     child {node {$T$}

       child {node {(\,$E$\,)} 

       child {node {$F$}

       child {node {$T$ +{} $T$}

                    child {node {3}}

                    child {node {4}} 

                 }

                 }}

    }};

\end{tikzpicture}

\end{center}

\begin{textblock}{5}(1, 6.5)

\bl{\texttt{(2*3)+(3+4)}}

\end{textblock}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}

A grammar is \alert{ambiguous} if there is a string that has at least parse trees.

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}

All rules must be of the form

\begin{center}

\bl{$A \rightarrow a$}

\end{center}

or

\begin{center}

\bl{$A \rightarrow B\cdot C$}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

\begin{center}

\bl{\begin{tabular}{@ {}lcl}

$S$ & $\rightarrow$ &  $N\cdot P$ \\

$P$ & $\rightarrow$ &  $V\cdot N$ \\

$N$ & $\rightarrow$ &  $N\cdot N$ \\

$N$ & $\rightarrow$ &  $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\

$V$ & $\rightarrow$ &  $\texttt{trains}$ 

\end{tabular}}

\end{center}

\bl{\texttt{Jeff trains geometry students}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}

\begin{itemize}

\item runtime is \bl{$O(n^3)$}\bigskip

\item grammars need to be transferred into CNF

\end{itemize}

\end{frame}}

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

\end{document}

%%% Local Variables:  

%%% mode: latex

%%% TeX-master: t

%%% End: