diff -r e5453add7df6 -r fb4cd144a9e6 slides/slides04.tex --- a/slides/slides04.tex Tue Dec 03 01:22:16 2019 +0000 +++ b/slides/slides04.tex Tue Dec 03 01:58:19 2019 +0000 @@ -347,99 +347,6 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{DFAs} - -\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},] - -\only<1,3->{\node[state,initial] (Q_0) {$\mbox{Q}_0$};} -\only<2>{\node[state,initial,fill=red] (Q_0) {$\mbox{Q}_0$};} -\only<1,2,4->{\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};} -\only<3>{\node[state,fill=red] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};} -\only<-3,5->{\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};} -\only<4>{\node[state,fill=red] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};} -\only<-4,6->{\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};} -\only<5>{\node[state,fill=red] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};} -\only<-5>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};} -\only<6->{\node[state, accepting,fill=red] (Q_4) [right=of Q_1] {$\mbox{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} - -\begin{textblock}{9}(4,12) -\LARGE{} -\only<3->{\boldmath\alert{$a$}}% -\only<4->{\boldmath\alert{$b$}}% -\only<5->{\boldmath\alert{$a$}}% -\only<6->{\boldmath\alert{$a$}}% -\only<7->{\boldmath\alert{$a\quad\Rightarrow \textbf{yes}$}}% -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[t] -\frametitle{DFAs} - -A \alert{\bf deterministic finite automaton}, DFA, consists of -5 things: - -\begin{itemize} -\item an alphabet \bl{$\varSigma$} -\item a set of states \bl{$\mbox{Qs}$} -\item one of these states is the start state \bl{$\mbox{Q}_0$} -\item some states are accepting states \bl{$F$}, and -\item there is transition function \bl{$\delta$}\bigskip - -\small -which takes a state and a character as arguments and produces a -new state; this function might not be everywhere defined -\end{itemize} - -\begin{center} -\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{NFAs} - -\begin{center} -\begin{tikzpicture}[>=stealth',very thick, auto, - every state/.style={minimum size=0pt,inner sep=3pt, - draw=blue!50,very thick,fill=blue!20},scale=2] -\node[state,initial] (Q_0) {$\mbox{Q}_0$}; -\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$}; -\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$}; -\path[->] (Q_0) edge [loop above] node {\alert{$b$}} (); -\path[<-] (Q_0) edge node [below] {\alert{$b$}} (Q_1); -\path[->] (Q_0) edge [bend left] node [above] {\alert{$a$}} (Q_1); -\path[->] (Q_0) edge [bend right=45,looseness=1.3] node [below] {\alert{$a$}} (Q_2); -\path[->] (Q_1) edge [loop above] node {\alert{$a,b$}} (); -\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_2); -\end{tikzpicture} -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - \begin{frame}[t]