--- a/slides/slides03.tex Fri Oct 11 14:51:11 2013 +0100
+++ b/slides/slides03.tex Sat Oct 12 09:13:42 2013 +0100
@@ -458,9 +458,9 @@
\begin{itemize}
-\item start can be an accepting state
+\item the start state 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)
+\item all states might be accepting (but this does not necessarily mean all strings are accepted)
\end{itemize}
\end{frame}}
@@ -614,7 +614,7 @@
\mbox{}\bigskip
\onslide<1>{By recursion we are given two automata:\bigskip}
-\begin{tikzpicture}[node distance=3mm,
+{\centering\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (q_0) {$\mbox{}$};
\node (r_1) [right=of q_0] {$\ldots$};
@@ -645,7 +645,7 @@
\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
\only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};}
\end{pgfonlayer}
-\end{tikzpicture}\bigskip\bigskip
+\end{tikzpicture}}\bigskip\bigskip
\small
We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them
@@ -661,7 +661,7 @@
\onslide<1>{By recursion we are given two automata:\smallskip}
-\begin{tikzpicture}[node distance=3mm,
+\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
\onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};}
@@ -707,22 +707,22 @@
\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
-\begin{tikzpicture}[node distance=3mm,
+\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
-\onslide<2>{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};}
+\onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};}
\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};}
-\only<2>{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
+\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
\node (a) [right=of 2] {$\ldots$};
\only<1>{
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};}
-\only<2>{
+\only<2->{
\node[state] (a1) [right=of a] {$\mbox{}$};
\node[state] (a2) [above=of a1] {$\mbox{}$};
\node[state] (a3) [below=of a1] {$\mbox{}$};}
-\only<2>{
+\only<2->{
\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
\path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1);
\path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1);
@@ -731,14 +731,14 @@
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
-\only<2>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
+\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
-\only<2>{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
+\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
\end{pgfonlayer}
-\end{tikzpicture}
+\end{tikzpicture}\bigskip
-
-Why can't we just have an epsilon transition from the accepting states to the starting state?
+\onslide<3->{
+Why can't we just have an epsilon transition from the accepting states to the starting state?}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -764,16 +764,16 @@
\begin{textblock}{11}(6.5,4.5)
\begin{tabular}{r|cl}
-& a & b\\
+nodes \textcolor{white}{*} & $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\}$\\
+$\varnothing$ \textcolor{white}{*} & \onslide<2->{$\varnothing$} & \onslide<2->{$\varnothing$}\\
+$\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0,1,2\}$} & \onslide<3->{$\{2\}$}\\
+$\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\varnothing$}\\
+$\{2\}$ \onslide<5->{*} & \onslide<3->{$\varnothing$} & \onslide<3->{$\{2\}$}\\
+$\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
+$\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
+$\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{1\}$} & \onslide<4->{$\{2\}$}\\
+\onslide<5->{s:} $\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
\end{tabular}
\end{textblock}
@@ -790,10 +790,10 @@
A language is \alert{regular} iff there exists
a regular expression that recognises all its strings.\bigskip\medskip
-or equivalently\bigskip\medskip
+or {\bf equivalently}\bigskip\medskip
A language is \alert{regular} iff there exists
-a deterministic finite automaton that recognises all its strings.\bigskip\pause
+a deterministic finite automaton that recognises all its strings.\bigskip\medskip\pause
Why is every finite set of strings a regular language?
\end{frame}}
@@ -803,42 +803,46 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
-\begin{frame}[c]
+\begin{frame}<1-2>[c]
\begin{center}
-\includegraphics[scale=0.5]{pics/ch3.jpg}
+\begin{tikzpicture}[>=stealth',very thick,auto,
+ every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (q_0) {$q_0$};
\node[state] (q_1) [right=of q_0] {$q_1$};
+\node[state] (q_2) [below right=of q_0] {$q_2$};
+\node[state] (q_3) [right=of q_2] {$q_3$};
+\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\path[->] (q_0) edge node [above] {\alert{$a$}} (q_1);
+\path[->] (q_1) edge node [above] {\alert{$a$}} (q_4);
+\path[->] (q_4) edge [loop right] node {\alert{$a, b$}} ();
+\path[->] (q_3) edge node [right] {\alert{$a$}} (q_4);
+\path[->] (q_2) edge node [above] {\alert{$a$}} (q_3);
+\path[->] (q_1) edge node [right] {\alert{$b$}} (q_2);
+\path[->] (q_0) edge node [above] {\alert{$b$}} (q_2);
+\path[->] (q_2) edge [loop left] node {\alert{$b$}} ();
+\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0);
+\end{tikzpicture}
\end{center}
+\mbox{}\\[-20mm]\mbox{}
+
\begin{center}
-\includegraphics[scale=0.5]{pics/ch4.jpg}\\
+\begin{tikzpicture}[>=stealth',very thick,auto,
+ every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
+\node[state,initial] (q_02) {$q_{0, 2}$};
\node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
+\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};
+\path[->] (q_02) edge [bend left] node [above] {\alert{$a$}} (q_13);
+\path[->] (q_13) edge [bend left] node [below] {\alert{$b$}} (q_02);
+\path[->] (q_02) edge [loop below] node {\alert{$b$}} ();
+\path[->] (q_13) edge node [above] {\alert{$a$}} (q_4);
+\path[->] (q_4) edge [loop above] node {\alert{$a, b$}} ();
+\end{tikzpicture}\\
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 are 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]