diff -r 06cbaaad3ba8 -r 7dac4492b0e6 slides/slides03.tex --- a/slides/slides03.tex Mon Oct 19 14:17:18 2020 +0100 +++ b/slides/slides03.tex Mon Oct 19 17:50:11 2020 +0100 @@ -1492,111 +1492,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] - \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} - \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} - \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; - \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) - (q1) edge[bend left] node[above] {\alert{$b$}} (q0) - (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) - (q1) edge node[above] {\alert{$a$}} (q2) - (q2) edge [loop right] node {\alert{$a$}} () - (q0) edge [loop below] node {\alert{$b$}} () - ; -\end{tikzpicture} -\end{center}\bigskip - -\begin{center} -\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ -\end{tabular} -\end{center} - - -Arden's Lemma: -\begin{center} -If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -\end{center} - -\only<2-6>{\small -\begin{textblock}{6}(1,0.8) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<3-6>{\small -\begin{textblock}{6}(2,4.15) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<4-6>{\small -\begin{textblock}{6}(3,7.55) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<5-6>{\small -\begin{textblock}{6}(4,10.9) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\only<6>{\small -\begin{textblock}{6}(5,13.4) -\begin{bubble}[7.5cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} - \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - - -\only<7->{\small -\begin{textblock}{6}(6,11.5) -\begin{bubble}[6.7cm] -\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} -\multicolumn{3}{@{}l}{Finally:}\\ -\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ -\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ -\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ -\end{tabular} -\end{bubble} -\end{textblock}} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{Regexps and Automata}