# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1384296881 0
# Node ID 9471a03257732906e1b50282a8e125e5d6fbd2d0
# Parent  fab34204d08e2d1d172d33d7284d5980633d6d79
added slides

diff -r fab34204d08e -r 9471a0325773 slides/slides07.pdf
Binary file slides/slides07.pdf has changed
diff -r fab34204d08e -r 9471a0325773 slides/slides07.tex
--- a/slides/slides07.tex	Tue Nov 12 21:51:57 2013 +0000
+++ b/slides/slides07.tex	Tue Nov 12 22:54:41 2013 +0000
@@ -71,6 +71,8 @@
 	showspaces=false,
 	showstringspaces=false}
 
+\setmonofont{Consolas}
+
 % beamer stuff 
 \renewcommand{\slidecaption}{AFL 07, King's College London, 13.~November 2013}
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}       
@@ -164,7 +166,7 @@
 \end{tabular}}
 \end{center}
 
-Unfortunately left-recursive (and ambiguous).\medskip\\
+Unfortunately it is left-recursive (and ambiguous).\medskip\\
 A problem for \alert{recursive descent parsers} (e.g.~parser combinators).
 \bigskip\pause
 
@@ -185,7 +187,7 @@
 \end{tabular}}
 \end{center}
 
-A non-left-recursive, non-ambiguous grammar for numbers
+A non-left-recursive, non-ambiguous grammar for numbers:
 
 \begin{center}
 \bl{\begin{tabular}{lcl}
@@ -211,7 +213,7 @@
 \end{tabular}}
 \end{center}
 
-Decide how many precedence levels, say\medskip\\
+Decide on how many precedence levels, say\medskip\\
 \hspace{5mm}highest for \bl{$()$}, medium for \bl{*}, lowest for \bl{+}
 
 \begin{center}
@@ -308,16 +310,31 @@
 \begin{tabular}{ccc}
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$ 
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;\epsilon$\\
+\\ 
+\\
+\\
+\\
+\\
 \end{tabular}} &
 \bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+\\
 $N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
-$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$ 
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N\;|\;\epsilon$\\
+\\
+$N$ & $\rightarrow$ & $0 \cdot N' \;|\; 1\cdot N'\;|\;0\;|\;1$\\
+$N'$ & $\rightarrow$ & $N \cdot N'\;|\;N$\\
 \end{tabular}}
 \end{tabular}
 \end{center}
 
+\pause\normalsize
+\begin{center}
+\bl{\begin{tabular}{l@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$N$ & $\rightarrow$ & $0 \cdot N\;|\; 1\cdot N\;|\;0\;|\;1$\\
+\end{tabular}}
 
+\end{center}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -328,9 +345,10 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
 
+If grammar is in Chomsky normalform \ldots
 
 \begin{center}
-\bl{\begin{tabular}{@ {}lcl}
+\bl{\begin{tabular}{@ {}lcl@ {}}
 $S$ & $\rightarrow$ &  $N\cdot P$ \\
 $P$ & $\rightarrow$ &  $V\cdot N$ \\
 $N$ & $\rightarrow$ &  $N\cdot N$ \\
@@ -350,6 +368,7 @@
 
 
 \begin{itemize}
+\item fastest possible algorithm for recognition problem
 \item runtime is \bl{$O(n^3)$}\bigskip
 \item grammars need to be transferred into CNF
 \end{itemize}
@@ -361,6 +380,74 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Hierarchy of Languages\end{tabular}}
+
+Recall that languages are sets of strings.
+
+\begin{center}
+\begin{tikzpicture}
+[rect/.style={draw=black!50, top color=white,bottom color=black!20, rectangle, very thick, rounded corners}]
+
+\draw (0,0) node [rect, text depth=39mm, text width=68mm] {all languages};
+\draw (0,-0.4) node [rect, text depth=28.5mm, text width=64mm] {decidable languages};
+\draw (0,-0.85) node [rect, text depth=17mm] {context sensitive languages};
+\draw (0,-1.14) node [rect, text depth=9mm, text width=50mm] {context-free languages};
+\draw (0,-1.4) node [rect] {regular languages};
+\end{tikzpicture}
+
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Context Sensitive Grms\end{tabular}}
+
+
+\begin{center}
+\bl{\begin{tabular}{lcl}
+$S$ & $\Rightarrow$ &  $bSAA\;|\; \epsilon$\\
+$A$ & $\Rightarrow$ & $a$\\
+$bA$ & $\Rightarrow$ & $Ab$\\
+\end{tabular}}
+\end{center}\pause
+
+\begin{center}
+\bl{$S \Rightarrow\ldots\Rightarrow^? "ababaa"$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
+\begin{center}
+\begin{tabular}{@{}lcl@{}}
+\textit{Stmt} & $\rightarrow$ &  $\texttt{skip}$\\
+              & $|$ & \textit{Id}\;\texttt{:=}\;\textit{AExp}\\
+              & $|$ & \texttt{if}\; \textit{BExp} \;\texttt{then}\; \textit{Block} \;\texttt{else}\; \textit{Block}\\
+              & $|$ & \texttt{while}\; \textit{BExp} \;\texttt{do}\; \textit{Block}\\
+              & $|$ & \texttt{read}\;\textit{Id}\\
+              & $|$ & \texttt{write}\;\textit{Id}\\
+              & $|$ & \texttt{write}\;\textit{String}\medskip\\
+\textit{Stmts} & $\rightarrow$ &  \textit{Stmt} \;\texttt{;}\; \textit{Stmts}\\
+              & $|$ & \textit{Stmt}\medskip\\
+\textit{Block} & $\rightarrow$ &  \texttt{\{}\,\textit{Stmts}\,\texttt{\}}\\
+                & $|$ & \textit{Stmt}\medskip\\
+\textit{AExp} & $\rightarrow$ & \ldots\\
+\textit{BExp} & $\rightarrow$ & \ldots\\
+\end{tabular}
+\end{center}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}
 
 \begin{center}