# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1350458640 -3600
# Node ID cad34315db1b8a1372bb0c527340df9d76980296
# Parent  a831432939433cf773df7847a06c2228721244e3
tuned

diff -r a83143293943 -r cad34315db1b slides04.pdf
Binary file slides04.pdf has changed
diff -r a83143293943 -r cad34315db1b slides04.tex
--- a/slides04.tex	Wed Oct 17 07:24:37 2012 +0100
+++ b/slides04.tex	Wed Oct 17 08:24:00 2012 +0100
@@ -235,6 +235,18 @@
 \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>{
@@ -418,7 +430,9 @@
 \begin{tabular}[b]{ll}
 \bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
 \end{tabular}
-\end{center}
+\end{center}\pause\bigskip
+
+Why can't we just have an epsilon transition from the accepting states to the starting state?
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -427,12 +441,14 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
 
-\begin{textblock}{5}(1,1)
+
+\begin{textblock}{5}(1,2.5)
 \includegraphics[scale=0.5]{pics/ch5.jpg}
 \end{textblock}
 
-\begin{textblock}{11}(6.5,3)
+\begin{textblock}{11}(6.5,4.5)
 \begin{tabular}{r|cl}
 & a & b\\
 \hline
@@ -452,6 +468,23 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Regular Languages\end{tabular}}
+
+A language is \alert{regular} iff there exists
+a regular expression that recognises all its strings.\bigskip\medskip
+
+or equivalently\bigskip\medskip
+
+A language is \alert{regular} iff there exists
+a deterministic finite automaton that recognises all its strings.\bigskip\pause
+
+Why is every finite set of strings a regular language?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -459,22 +492,67 @@
 \begin{frame}[c]
 
 \begin{center}
-\includegraphics[scale=0.7]{pics/ch4.jpg}
+\includegraphics[scale=0.5]{pics/ch3.jpg}
+\end{center}
+
+\begin{center}
+\includegraphics[scale=0.5]{pics/ch4.jpg}\\
+minimal automaton
 \end{center}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+Given the function 
+
+\begin{center}
+\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$rev(\varnothing)$   & $\dn$ & $\varnothing$\\
+$rev(\epsilon)$         & $\dn$ & $\epsilon$\\
+$rev(c)$                      & $\dn$ & $c$\\
+$rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\
+$rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+$rev(r^*)$                   & $\dn$ & $rev(r)^*$\\
+\end{tabular}}
+\end{center}
+
+
+and the set
+
+\begin{center}
+\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}
+\end{center}
+
+prove whether
+
+\begin{center}
+\bl{$L(rev(r)) = Rev (L(r))$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Languages\end{tabular}}
 
-A language is \alert{regular} iff there exists
-a regular expression that recognises all its strings.\bigskip\bigskip\pause
+\begin{itemize}
+\item The star-case in our proof about the matcher needs the following lemma
+\begin{center}
+\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}
+\end{center}
+\end{itemize}\bigskip\bigskip
 
-\textcolor{gray}{not all languages are regular, e.g.~\bl{a$^n$b$^n$}.}
+\begin{itemize}
+\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip
+\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}
+
+\end{itemize}
+
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -495,22 +573,13 @@
 \mode<presentation>{
 \begin{frame}[c]
 
-
-
-\begin{itemize}
-\item The star-case in our proof needs the following lemma
+Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.
+(a) Find a regular expression that recognises the two strings \bl{$ab$} and \bl{$ac$}. (b)
+Find a regular expression that matches all strings \emph{except} these two strings.
+Note, you can only use regular expressions of the form 
 \begin{center}
-\bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$}
+\bl{$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$}
 \end{center}
-\end{itemize}\bigskip\bigskip
-
-
-
-\begin{itemize}
-\item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip
-\item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B}
-
-\end{itemize}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%