# HG changeset patch # User Christian Urban # Date 1381565622 -3600 # Node ID 6e7c3db9023d2a70ca219a963f817df46770d4d5 # Parent b98a0a49c4327dcf2d85b5024cba10548784b977 added diff -r b98a0a49c432 -r 6e7c3db9023d slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r b98a0a49c432 -r 6e7c3db9023d slides/slides03.tex --- 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{ -\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{ -\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{ \begin{frame}[c] diff -r b98a0a49c432 -r 6e7c3db9023d slides/slides04.tex --- a/slides/slides04.tex Fri Oct 11 14:51:11 2013 +0100 +++ b/slides/slides04.tex Sat Oct 12 09:13:42 2013 +0100 @@ -100,6 +100,74 @@ \end{frame}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\mode{ +\begin{frame}<1-2>[c] + +\begin{center} +\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} +\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{ +\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{ \begin{frame}[c]