89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    89 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    90 \begin{frame}[c]

    90 % \begin{frame}[c]

    91 \frametitle{DFA to Rexp}

    91 % \frametitle{DFA to Rexp}

    92 

    92 

    93 \begin{center}

    93 % \begin{center}

    94 \begin{tikzpicture}[scale=2,>=stealth',very thick,

    94 % \begin{tikzpicture}[scale=2,>=stealth',very thick,

    95                     every state/.style={minimum size=0pt,

    95 %                     every state/.style={minimum size=0pt,

    96                     draw=blue!50,very thick,fill=blue!20},]

    96 %                     draw=blue!50,very thick,fill=blue!20},]

    97   \node[state, initial]        (q0) at ( 0,1) {$q_0$};

    97 %   \node[state, initial]        (q0) at ( 0,1) {$q_0$};

    98   \node[state]                    (q1) at ( 1,1) {$q_1$};

    98 %   \node[state]                    (q1) at ( 1,1) {$q_1$};

    99   \node[state, accepting] (q2) at ( 2,1) {$q_2$};

    99 %   \node[state, accepting] (q2) at ( 2,1) {$q_2$};

   100   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)

   100 %   \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)

   101             (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

   101 %             (q1) edge[bend left] node[above] {\alert{$b$}} (q0)

   102             (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

   102 %             (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)

   103             (q1) edge node[above] {\alert{$a$}} (q2)

   103 %             (q1) edge node[above] {\alert{$a$}} (q2)

   104             (q2) edge [loop right] node {\alert{$a$}} ()

   104 %             (q2) edge [loop right] node {\alert{$a$}} ()

   105             (q0) edge [loop below] node {\alert{$b$}} ();

   105 %             (q0) edge [loop below] node {\alert{$b$}} ();

   106 \end{tikzpicture}

   106 % \end{tikzpicture}

   107 \end{center}\bigskip

   107 % \end{center}\bigskip

   108 

   108 

   109 \begin{center}

   109 % \begin{center}

   110 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}

   110 % \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}

   111 \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\

   111 % \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\

   112 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\

   112 % \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\

   113 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\

   113 % \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\

   114 

   114 

   115 \end{tabular}

   115 % \end{tabular}

   116 \end{center}

   116 % \end{center}

   117 

   117 

   118 Arden's Lemma:

   118 % Arden's Lemma:

   119 \begin{center}

   119 % \begin{center}

   120 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}

   120 % If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}

   121 \end{center}

   121 % \end{center}

   122 

   122 

   123 

   123 

   124 \end{frame}

   124 % \end{frame}

   125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   125 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   126 

   126 

   127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   127 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   128 \begin{frame}[c]

   128 % \begin{frame}[c]

   129 \frametitle{DFA Minimisation}

   129 % \frametitle{DFA Minimisation}

   130 

   130 

   131 \begin{enumerate}

   131 % \begin{enumerate}

   132 \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}

   132 % \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}

   133 \item Mark all pairs that accepting and non-accepting states

   133 % \item Mark all pairs that accepting and non-accepting states

   134 \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether

   134 % \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether

   135 \begin{center}

   135 % \begin{center}

   136 \bl{$(\delta(q, c), \delta(p,c))$}

   136 % \bl{$(\delta(q, c), \delta(p,c))$}

   137 \end{center} 

   137 % \end{center} 

   138 are marked. If yes, then also mark \bl{$(q, p)$}.

   138 % are marked. If yes, then also mark \bl{$(q, p)$}.

   139 \item Repeat last step until no change.

   139 % \item Repeat last step until no change.

   140 \item All unmarked pairs can be merged.

   140 % \item All unmarked pairs can be merged.

   141 \end{enumerate}

   141 % \end{enumerate}

   142 

   142 

   143 \end{frame}

   143 % \end{frame}

   144 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   144 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   145 

   145 

   146 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   146 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

   147 \begin{frame}[c]

   147 % \begin{frame}[c]

   148 

   148 

   149 \begin{center}

   149 % \begin{center}

   150 \begin{tabular}{@{\hspace{-8mm}}cc@{}}

   150 % \begin{tabular}{@{\hspace{-8mm}}cc@{}}

   151 \begin{tikzpicture}[>=stealth',very thick,auto,

   151 % \begin{tikzpicture}[>=stealth',very thick,auto,

   152                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   152 %                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   153 \node[state,initial]  (q_0)  {$q_0$};

   153 % \node[state,initial]  (q_0)  {$q_0$};

   154 \node[state] (q_1) [right=of q_0] {$q_1$};

   154 % \node[state] (q_1) [right=of q_0] {$q_1$};

   155 \node[state] (q_2) [below right=of q_0] {$q_2$};

   155 % \node[state] (q_2) [below right=of q_0] {$q_2$};

   156 \node[state] (q_3) [right=of q_2] {$q_3$};

   156 % \node[state] (q_3) [right=of q_2] {$q_3$};

   157 \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   157 % \node[state, accepting] (q_4) [right=of q_1] {$q_4$};

   158 \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   158 % \path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);

   159 \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   159 % \path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);

   160 \path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();

   160 % \path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();

   161 \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   161 % \path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);

   162 \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   162 % \path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);

   163 \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   163 % \path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);

   164 \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   164 % \path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);

   165 \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   165 % \path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();

   166 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);

   166 % \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);

   167 \end{tikzpicture}

   167 % \end{tikzpicture}

   168 &

   168 % &

   169 \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]

   169 % \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]

   170 \draw (0,0) -- (4,0);

   170 % \draw (0,0) -- (4,0);

   171 \draw (0,1) -- (4,1);

   171 % \draw (0,1) -- (4,1);

   172 \draw (0,2) -- (3,2);

   172 % \draw (0,2) -- (3,2);

   173 \draw (0,3) -- (2,3);

   173 % \draw (0,3) -- (2,3);

   174 \draw (0,4) -- (1,4);

   174 % \draw (0,4) -- (1,4);

   175 

   175 

   176 \draw (0,0) -- (0, 4);

   176 % \draw (0,0) -- (0, 4);

   177 \draw (1,0) -- (1, 4);

   177 % \draw (1,0) -- (1, 4);

   178 \draw (2,0) -- (2, 3);

   178 % \draw (2,0) -- (2, 3);

   179 \draw (3,0) -- (3, 2);

   179 % \draw (3,0) -- (3, 2);

   180 \draw (4,0) -- (4, 1);

   180 % \draw (4,0) -- (4, 1);

   181 

   181 

   182 \draw (0.5,-0.5) node {$q_0$}; 

   182 % \draw (0.5,-0.5) node {$q_0$}; 

   183 \draw (1.5,-0.5) node {$q_1$}; 

   183 % \draw (1.5,-0.5) node {$q_1$}; 

   184 \draw (2.5,-0.5) node {$q_2$}; 

   184 % \draw (2.5,-0.5) node {$q_2$}; 

   185 \draw (3.5,-0.5) node {$q_3$};

   185 % \draw (3.5,-0.5) node {$q_3$};

   187 \draw (-0.5, 3.5) node {$q_1$}; 

   187 % \draw (-0.5, 3.5) node {$q_1$}; 

   188 \draw (-0.5, 2.5) node {$q_2$}; 

   188 % \draw (-0.5, 2.5) node {$q_2$}; 

   189 \draw (-0.5, 1.5) node {$q_3$}; 

   189 % \draw (-0.5, 1.5) node {$q_3$}; 

   190 \draw (-0.5, 0.5) node {$q_4$}; 

   190 % \draw (-0.5, 0.5) node {$q_4$}; 

   191 

   191 

   192 \draw (0.5,0.5) node {\large$\star$}; 

   192 % \draw (0.5,0.5) node {\large$\star$}; 

   193 \draw (1.5,0.5) node {\large$\star$}; 

   193 % \draw (1.5,0.5) node {\large$\star$}; 

   194 \draw (2.5,0.5) node {\large$\star$}; 

   194 % \draw (2.5,0.5) node {\large$\star$}; 

   195 \draw (3.5,0.5) node {\large$\star$};

   195 % \draw (3.5,0.5) node {\large$\star$};

   196 \draw (0.5,1.5) node {\large$\star$}; 

   196 % \draw (0.5,1.5) node {\large$\star$}; 

   197 \draw (2.5,1.5) node {\large$\star$}; 

   197 % \draw (2.5,1.5) node {\large$\star$}; 

   198 \draw (0.5,3.5) node {\large$\star$}; 

   198 % \draw (0.5,3.5) node {\large$\star$}; 

   199 \draw (1.5,2.5) node {\large$\star$}; 

   199 % \draw (1.5,2.5) node {\large$\star$}; 

   200 \end{tikzpicture}}

   200 % \end{tikzpicture}}

   201 \end{tabular}

   201 % \end{tabular}

   202 \end{center}

   202 % \end{center}

   203 

   203 

   204 

   204 

   205 \mbox{}\\[-20mm]\mbox{}

   205 % \mbox{}\\[-20mm]\mbox{}

   206 

   206 

   207 \begin{center}

   207 % \begin{center}

   208 \begin{tikzpicture}[>=stealth',very thick,auto,

   208 % \begin{tikzpicture}[>=stealth',very thick,auto,

   209                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   209 %                              every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]

   210 \node[state,initial]  (q_02)  {$q_{0, 2}$};

   210 % \node[state,initial]  (q_02)  {$q_{0, 2}$};

   211 \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

   211 % \node[state] (q_13) [right=of q_02] {$q_{1, 3}$};

   212 \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

   212 % \node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};

   213 \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

   213 % \path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);

   214 \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

   214 % \path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);

   215 \path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

   215 % \path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();

   216 \path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

   216 % \path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);

   217 \path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

   217 % \path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();

   218 \end{tikzpicture}\\

   218 % \end{tikzpicture}\\

   219 minimal automaton

   219 % minimal automaton

   220 \end{center}

   220 % \end{center}

   221 

   221 

   222 \end{frame}

   222 % \end{frame}

   223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   223 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

   322 \begin{itemize}

   322 % \begin{itemize}

   323 \item {\bf My Voice} ``lecturer speaks in a low voice and 

   323 % \item {\bf My Voice} ``lecturer speaks in a low voice and 

   324   is hard to hear him'' ``please use mic'' ``please use mic 

   324 %   is hard to hear him'' ``please use mic'' ``please use mic 

   325   \& lecture recording''

   325 %   \& lecture recording''

   326 \item {\bf Pace} ``faster pace'' ``a bit quick for me 

   326 % \item {\bf Pace} ``faster pace'' ``a bit quick for me 

   327 personally''

   327 % personally''

   328 \item {\bf Recording} ``please use recording class''

   328 % \item {\bf Recording} ``please use recording class''

   329 \item {\bf Module Name} ``misleading''

   329 % \item {\bf Module Name} ``misleading''

   330 \item {\bf Examples} ``more examples''

   330 % \item {\bf Examples} ``more examples''

   331 \item {\bf Assessment} ``really appreciate extension of 

   331 % \item {\bf Assessment} ``really appreciate extension of 

   332   first coursework'' 

   332 %   first coursework'' 

   333 \end{itemize}

   333 % \end{itemize}