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