# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1381265971 -3600
# Node ID 72b686e1c974081079f9ae18342060cfe05a10ba
# Parent  e3a8cf96f570ed4a69d266d8a6b55b1923209ab7
added slides

diff -r e3a8cf96f570 -r 72b686e1c974 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r e3a8cf96f570 -r 72b686e1c974 slides/slides03.tex
--- a/slides/slides03.tex	Tue Oct 08 21:37:13 2013 +0100
+++ b/slides/slides03.tex	Tue Oct 08 21:59:31 2013 +0100
@@ -374,6 +374,17 @@
 \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}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -432,6 +443,296 @@
 this function might not always be defined
 \end{itemize}
 
+\begin{center}
+\bl{$A(Q, q_0, F, \delta)$}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch3.jpg}
+\end{center}\pause
+
+\begin{itemize}
+\item start can be an accepting state
+\item it is possible that there is no accepting state
+\item all states might be accepting (but does not necessarily mean all strings are accepted)
+\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}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\includegraphics[scale=0.7]{pics/ch5.jpg}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\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}[t]{ll}
+\bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[t]{ll}
+\bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\
+\end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\begin{tabular}[b]{ll}
+\bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\
+\end{tabular}
+\end{center}\pause\bigskip
+
+Why can't we just have an epsilon transition from the accepting states to the starting state?
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Subset Construction\end{tabular}}
+
+
+\begin{textblock}{5}(1,2.5)
+\includegraphics[scale=0.5]{pics/ch5.jpg}
+\end{textblock}
+
+\begin{textblock}{11}(6.5,4.5)
+\begin{tabular}{r|cl}
+& a & b\\
+\hline
+$\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\
+$\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\
+$\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\
+$\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\
+$\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\
+$\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
+$\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\
+\onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\
+\end{tabular}
+\end{textblock}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\begin{center}
+\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]
+
+\begin{enumerate}
+\item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p}
+\item Mark all pairs that accepting and non-accepting states
+\item For  all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether
+\begin{center}
+\bl{($\delta$(q,c), $\delta$(p,c))}
+\end{center} 
+are marked. If yes, then also mark \bl{(q, p)} 
+\item Repeat last step until no chance.
+\item All unmarked pairs can be merged.
+\end{enumerate}
+
+\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}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%