diff -r 955d5b3b0619 -r 2849c305b12d slides/slides04.tex --- a/slides/slides04.tex Sun Oct 15 20:47:14 2017 +0100 +++ b/slides/slides04.tex Tue Oct 17 13:49:45 2017 +0100 @@ -86,141 +86,141 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{DFA to Rexp} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA to Rexp} -\begin{center} -\begin{tikzpicture}[scale=2,>=stealth',very thick, - every state/.style={minimum size=0pt, - draw=blue!50,very thick,fill=blue!20},] - \node[state, initial] (q0) at ( 0,1) {$q_0$}; - \node[state] (q1) at ( 1,1) {$q_1$}; - \node[state, accepting] (q2) at ( 2,1) {$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{tikzpicture}[scale=2,>=stealth',very thick, +% every state/.style={minimum size=0pt, +% draw=blue!50,very thick,fill=blue!20},] +% \node[state, initial] (q0) at ( 0,1) {$q_0$}; +% \node[state] (q1) at ( 1,1) {$q_1$}; +% \node[state, accepting] (q2) at ( 2,1) {$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@{\hspace{7mm}}l} -\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ -\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ -\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ +% \begin{center} +% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} +% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ +% \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ +% \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ -\end{tabular} -\end{center} +% \end{tabular} +% \end{center} -Arden's Lemma: -\begin{center} -If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} -\end{center} +% Arden's Lemma: +% \begin{center} +% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} +% \end{center} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{DFA Minimisation} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] +% \frametitle{DFA Minimisation} -\begin{enumerate} -\item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} -\item Mark all pairs that accepting and non-accepting states -\item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether -\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 change. -\item All unmarked pairs can be merged. -\end{enumerate} +% \begin{enumerate} +% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} +% \item Mark all pairs that accepting and non-accepting states +% \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether +% \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 change. +% \item All unmarked pairs can be merged. +% \end{enumerate} -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \begin{frame}[c] -\begin{center} -\begin{tabular}{@{\hspace{-8mm}}cc@{}} -\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} -& -\raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] -\draw (0,0) -- (4,0); -\draw (0,1) -- (4,1); -\draw (0,2) -- (3,2); -\draw (0,3) -- (2,3); -\draw (0,4) -- (1,4); +% \begin{center} +% \begin{tabular}{@{\hspace{-8mm}}cc@{}} +% \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} +% & +% \raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm] +% \draw (0,0) -- (4,0); +% \draw (0,1) -- (4,1); +% \draw (0,2) -- (3,2); +% \draw (0,3) -- (2,3); +% \draw (0,4) -- (1,4); -\draw (0,0) -- (0, 4); -\draw (1,0) -- (1, 4); -\draw (2,0) -- (2, 3); -\draw (3,0) -- (3, 2); -\draw (4,0) -- (4, 1); +% \draw (0,0) -- (0, 4); +% \draw (1,0) -- (1, 4); +% \draw (2,0) -- (2, 3); +% \draw (3,0) -- (3, 2); +% \draw (4,0) -- (4, 1); -\draw (0.5,-0.5) node {$q_0$}; -\draw (1.5,-0.5) node {$q_1$}; -\draw (2.5,-0.5) node {$q_2$}; -\draw (3.5,-0.5) node {$q_3$}; +% \draw (0.5,-0.5) node {$q_0$}; +% \draw (1.5,-0.5) node {$q_1$}; +% \draw (2.5,-0.5) node {$q_2$}; +% \draw (3.5,-0.5) node {$q_3$}; -\draw (-0.5, 3.5) node {$q_1$}; -\draw (-0.5, 2.5) node {$q_2$}; -\draw (-0.5, 1.5) node {$q_3$}; -\draw (-0.5, 0.5) node {$q_4$}; +% \draw (-0.5, 3.5) node {$q_1$}; +% \draw (-0.5, 2.5) node {$q_2$}; +% \draw (-0.5, 1.5) node {$q_3$}; +% \draw (-0.5, 0.5) node {$q_4$}; -\draw (0.5,0.5) node {\large$\star$}; -\draw (1.5,0.5) node {\large$\star$}; -\draw (2.5,0.5) node {\large$\star$}; -\draw (3.5,0.5) node {\large$\star$}; -\draw (0.5,1.5) node {\large$\star$}; -\draw (2.5,1.5) node {\large$\star$}; -\draw (0.5,3.5) node {\large$\star$}; -\draw (1.5,2.5) node {\large$\star$}; -\end{tikzpicture}} -\end{tabular} -\end{center} +% \draw (0.5,0.5) node {\large$\star$}; +% \draw (1.5,0.5) node {\large$\star$}; +% \draw (2.5,0.5) node {\large$\star$}; +% \draw (3.5,0.5) node {\large$\star$}; +% \draw (0.5,1.5) node {\large$\star$}; +% \draw (2.5,1.5) node {\large$\star$}; +% \draw (0.5,3.5) node {\large$\star$}; +% \draw (1.5,2.5) node {\large$\star$}; +% \end{tikzpicture}} +% \end{tabular} +% \end{center} -\mbox{}\\[-20mm]\mbox{} +% \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} +% \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} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% \end{frame} +% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] @@ -319,18 +319,18 @@ \frametitle{Survey: Thanks!} \small -\begin{itemize} -\item {\bf My Voice} ``lecturer speaks in a low voice and - is hard to hear him'' ``please use mic'' ``please use mic - \& lecture recording'' -\item {\bf Pace} ``faster pace'' ``a bit quick for me -personally'' -\item {\bf Recording} ``please use recording class'' -\item {\bf Module Name} ``misleading'' -\item {\bf Examples} ``more examples'' -\item {\bf Assessment} ``really appreciate extension of - first coursework'' -\end{itemize} +% \begin{itemize} +% \item {\bf My Voice} ``lecturer speaks in a low voice and +% is hard to hear him'' ``please use mic'' ``please use mic +% \& lecture recording'' +% \item {\bf Pace} ``faster pace'' ``a bit quick for me +% personally'' +% \item {\bf Recording} ``please use recording class'' +% \item {\bf Module Name} ``misleading'' +% \item {\bf Examples} ``more examples'' +% \item {\bf Assessment} ``really appreciate extension of +% first coursework'' +% \end{itemize} \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%