Binary file slides04.pdf has changed

--- a/slides04.tex	Wed Oct 17 00:58:06 2012 +0100
+++ b/slides04.tex	Wed Oct 17 07:02:43 2012 +0100
@@ -143,6 +143,33 @@
 
 \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>{
@@ -195,16 +222,24 @@
 \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}Automata\end{tabular}}
+\frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}}
 
 A deterministic finite automaton consists of:
 
@@ -232,6 +267,91 @@
 
 \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}}
@@ -239,23 +359,53 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}}
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch5.jpg}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 
 \begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
-\end{center}\bigskip
+\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}{l}
-\bl{$\hat{\delta}(\texttt{""}, q) = q$}\\
-\bl{$\hat{\delta}(c::s, q) = \hat{\delta}(s, \delta(c, q))$}\\
+\begin{tabular}[t]{ll}
+\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\
 \end{tabular}
-\end{center}\bigskip\pause
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 
 \begin{center}
-Accepting? \hspace{5mm}\bl{$\hat{\delta}(s, q_0) \in F$}
+\begin{tabular}[t]{ll}
+\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\
+\end{tabular}
 \end{center}
+
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -264,6 +414,34 @@
 \begin{frame}[c]
 
 \begin{center}
+\begin{tabular}[b]{ll}
+\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.5]{pics/ch5.jpg}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
 \includegraphics[scale=0.7]{pics/ch4.jpg}
 \end{center}
 
@@ -288,8 +466,6 @@
 \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}.