# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1349226895 -3600
# Node ID 4d81b2dc827188ae4221e93a20c886fa76600bbe
# Parent  32d56fef14a7a45a01de7f7feed999b6255a0ac9
tuned

diff -r 32d56fef14a7 -r 4d81b2dc8271 slides02.pdf
Binary file slides02.pdf has changed
diff -r 32d56fef14a7 -r 4d81b2dc8271 slides02.tex
--- a/slides02.tex	Wed Oct 03 01:41:08 2012 +0100
+++ b/slides02.tex	Wed Oct 03 02:14:55 2012 +0100
@@ -360,6 +360,109 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}
+
+Remember their inductive definition:\\[5cm]
+
+\begin{textblock}{6}(5,5)
+  \begin{tabular}{@ {}rrl}
+  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}\\
+         & \bl{$\mid$} & \bl{$\epsilon$}       \\
+         & \bl{$\mid$} & \bl{c}                        \\
+         & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\
+         & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  \\
+         & \bl{$\mid$} & \bl{r$^*$}                  \\
+  \end{tabular}
+  \end{textblock}
+
+If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (2)\end{tabular}}
+
+\begin{itemize}
+\item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
+\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already
+holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip
+\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already
+holds for \bl{r$_1$} and \bl{r$_2$}.
+\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
+holds for \bl{r}.
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}}
+
+Assume \bl{$P(r)$} is the property:
+
+\begin{center}
+\bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}}
+
+If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip
+
+\begin{itemize}
+\item \bl{$P$} holds for the empty string, and\medskip
+\item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$}
+already holds for \bl{s}
+\end{itemize}
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+
+A language (set of strings) is \alert{regular} iff there exists
+a regular expression that recognises all its strings.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Automata\end{tabular}}
+
+A deterministic finite automaton consists of:
+
+\begin{itemize}
+\item a 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 as argument and a character and produces a new state\smallskip\\
+this function might not always be defined
+\end{itemize}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 \end{document}