--- a/slides/slides03.tex Tue Oct 03 23:35:16 2017 +0100
+++ b/slides/slides03.tex Tue Oct 10 18:52:10 2017 +0100
@@ -29,7 +29,7 @@
\begin{tabular}{lp{8cm}}
Email: & christian.urban at kcl.ac.uk\\
Office: & N7.07 (North Wing, Bush House)\\
- Slides: & KEATS (also home work and coursework is there)\\
+ Slides: & KEATS (also homework and coursework is there)\\
\end{tabular}
\end{center}
@@ -41,9 +41,10 @@
\frametitle{Scala Book, Exams}
\begin{itemize}
-\item www.inf.kcl.ac.uk/~urbanc/ProgInScala2ed.pdf
-\item homeworks (exam 80\%)
-\item coursework (20\%)
+\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
+\item homeworks (written exam 80\%)
+\item coursework (20\%)\bigskip
+\item short survey at KEATS; to be answered until Sunday
\end{itemize}
\end{frame}
@@ -111,6 +112,30 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{1.5}
+\begin{tabular}{@{}lcl}
+ \bl{$\der\,a\,((a \cdot b) + b)^*$}
+ & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+ & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
Input: string \bl{$abc$} and regular expression \bl{$r$}
@@ -122,12 +147,33 @@
\end{enumerate}
\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+
+\begin{center}
+\def\arraystretch{2}
+\begin{tabular}{@{}lcl}
+ \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+ & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+ & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+ & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-We proved already
+We proved partially
\begin{center}
\bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$}
@@ -197,7 +243,7 @@
\begin{center}
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
- \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\
+ \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
& \bl{$\mid$} & \bl{$\ONE$} & empty string / "" / $[]$\\
& \bl{$\mid$} & \bl{$c$} & character\\
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
@@ -243,25 +289,6 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%\mode<presentation>{
-%\begin{frame}[c]
-%\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
-%
-%Lexing separates strings into ``words'' / components.
-%
-%\begin{itemize}
-%\item Identifiers (non-empty strings of letters or digits, starting with a letter)
-%\item Numbers (non-empty sequences of digits omitting leading zeros)
-%\item Keywords (else, if, while, \ldots)
-%\item White space (a non-empty sequence of blanks, newlines and tabs)
-%\item Comments
-%\end{itemize}
-%
-%\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Automata}
@@ -269,18 +296,19 @@
A \alert{\bf deterministic finite automaton}, DFA, consists of:
\begin{itemize}
+\item an alphabet \bl{$\varSigma$}
\item a set of states \bl{$Q$}
-\item one of these states is the start state \bl{$q_0$}
+\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 as argument and a character and produces a
-new state; this function might not be everywhere defined
+new state; this function might not be everywhere defined $\Rightarrow$ partial function
\end{itemize}
\begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
\end{center}
\end{frame}
@@ -293,20 +321,20 @@
\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);
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (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}
@@ -326,20 +354,20 @@
\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);
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (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}
@@ -347,8 +375,10 @@
\begin{center}
\begin{tabular}{lll}
-\bl{$(q_0, a) \rightarrow q_1$} & \bl{$(q_1, a) \rightarrow q_4$} & \bl{$(q_4, a) \rightarrow q_4$}\\
-\bl{$(q_0, b) \rightarrow q_2$} & \bl{$(q_1, b) \rightarrow q_2$} & \bl{$(q_4, b) \rightarrow q_4$}\\
+ \bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$}
+ & \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\
+ \bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} &
+ \bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\
\end{tabular}\ldots
\end{center}
@@ -362,22 +392,22 @@
Given
\begin{center}
-\bl{$A(Q, q_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
\end{center}
you can define
\begin{center}
\begin{tabular}{l}
-\bl{$\hat{\delta}(q, []) \dn q$}\\
-\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\
+\bl{$\widehat{\delta}(q, []) \dn q$}\\
+\bl{$\widehat{\delta}(q, c::s) \dn \widehat{\delta}(\delta(q, c), s)$}\\
\end{tabular}
\end{center}\pause
Whether a string \bl{$s$} is accepted by \bl{$A$}?
\begin{center}
-\hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
+\hspace{5mm}\bl{$\hat{\delta}(\mbox{Q}_0, s) \in F$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -420,11 +450,11 @@
Non-Deterministic\\[-1mm]
Finite Automata\end{tabular}}
-A non-deterministic finite automaton consists again of:
+A non-deterministic finite automaton (NFA) consists again of:
\begin{itemize}
\item a finite set of states
-\item one of these states is the start state
+\item \underline{some} these states are the start states
\item some states are accepting states, and
\item there is transition \alert{relation}\medskip
\end{itemize}
@@ -432,13 +462,12 @@
\begin{center}
\begin{tabular}{c}
-\bl{$(q_1, a) \rightarrow q_2$}\\
-\bl{$(q_1, a) \rightarrow q_3$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\
+\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\
\end{tabular}
-\hspace{10mm}
-\begin{tabular}{c}
-\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
-\end{tabular}
+\bl{\ldots}
+\hspace{10mm}\pause
+\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}
\end{center}
\end{frame}
@@ -446,7 +475,31 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Two NFA Examples}
+\frametitle{An NFA Example}
+
+% A NFA for (ab* + b)*a
+\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] 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}[c]
+\frametitle{Two Epsilon NFA Examples}
\small
\begin{center}
@@ -480,6 +533,7 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Rexp to NFA}
@@ -488,17 +542,17 @@
\begin{tabular}[t]{l@{\hspace{10mm}}l}
\raisebox{1mm}{\bl{$\ZERO$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state, initial] (q_0) {$\mbox{}$};
+\node[state, initial] (Q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
\raisebox{1mm}{\bl{$\ONE$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state, initial, accepting] (q_0) {$\mbox{}$};
+\node[state, initial, accepting] (Q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
\raisebox{2mm}{\bl{$c$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state, initial] (q_0) {$\mbox{}$};
-\node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$};
-\path[->] (q_0) edge node [below] {\alert{$c$}} (q_1);
+\node[state, initial] (Q_0) {$\mbox{}$};
+\node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$};
+\path[->] (Q_0) edge node [below] {\alert{$c$}} (Q_1);
\end{tikzpicture}\\\\
\end{tabular}
\end{center}
@@ -511,40 +565,73 @@
\frametitle{Case $r_1\cdot r_2$}
\mbox{}\bigskip
-\onslide<1>{By recursion we are given two automata:\bigskip}
+\onslide<1->{By recursion we are given two automata:\bigskip}
-{\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$};
-\only<1>{
-\node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$};
-\node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$};
-\node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};}
-\only<2>{
-\node[state] (t_1) [right=of r_1] {$\mbox{}$};
-\node[state] (t_2) [above=of t_1] {$\mbox{}$};
-\node[state] (t_3) [below=of t_1] {$\mbox{}$};}
-\only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
-\only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
-\node (b_1) [right=of a_0] {$\ldots$};
+{\centering%
+\only<1>{%
+\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[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
+\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
+\node (R_1) [right=of Q_0] {$\ldots$};
+\node[state, accepting] (T_1) [right=of R_1] {$\mbox{}$};
+\node[state, accepting] (T_2) [above=of T_1] {$\mbox{}$};
+\node[state, accepting] (T_3) [below=of T_1] {$\mbox{}$};
+
+\node (A_0) [right=2.5cm of T_1] {$\mbox{}$};
+\node[state, initial] (A_01) [above=1mm of A_0] {$\mbox{}$};
+\node[state, initial] (A_02) [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1) [right=of A_0] {$\ldots$};
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
-\only<2>{
-\path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0);
-\path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0);
-\path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0);
-}
\begin{pgfonlayer}{background}
-\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};}
-\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};}
-\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};}
-\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
-\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$}};}
+ \node (1) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_3)] {};
+ \node (2) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
+\node [yshift=2mm] at (1.north) {$r_1$};
+\node [yshift=2mm] at (2.north) {$r_2$};
\end{pgfonlayer}
-\end{tikzpicture}}\bigskip\bigskip
+\end{tikzpicture}}
+\only<2>{%
+\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[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
+\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
+\node (r_1) [right=of Q_0] {$\ldots$};
+\node[state] (t_1) [right=of r_1] {$\mbox{}$};
+\node[state] (t_2) [above=of t_1] {$\mbox{}$};
+\node[state] (t_3) [below=of t_1] {$\mbox{}$};
+
+\node (A_0) [right=2.5cm of t_1] {$\mbox{}$};
+\node[state] (A_01) [above=1mm of A_0] {$\mbox{}$};
+\node[state] (A_02) [below=1mm of A_0] {$\mbox{}$};
+
+\node (b_1) [right=of A_0] {$\ldots$};
+\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
+\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
+\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
+\path[->] (t_1) edge (A_01);
+\path[->] (t_2) edge node [above] {$\epsilon$s} (A_01);
+\path[->] (t_3) edge (A_01);
+\path[->] (t_1) edge (A_02);
+\path[->] (t_2) edge (A_02);
+\path[->] (t_3) edge node [below] {$\epsilon$s} (A_02);
+
+\begin{pgfonlayer}{background}
+ \node (3) [rounded corners, inner sep=1mm, thick,
+ draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
+\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
+\end{pgfonlayer}
+\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
@@ -556,23 +643,24 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Case $r_1+ r_2$}
-\mbox{}\\[-10mm]
+\mbox{}\\[-8mm]
-\onslide<1>{By recursion we are given two automata:\smallskip}
+\onslide<1->{By recursion we are given two automata:\smallskip}
-\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{}$};}
-\only<1>{
-\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};
-\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};}
-\only<2>{
-\node[state] (2) [above right=16mm of 1] {$\mbox{}$};
-\node[state] (3) [below right=16mm of 1] {$\mbox{}$};}
+\hspace{2cm}
+\only<1>{%
+ \begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.center)]
+\node at (0,0) (1) {$\mbox{}$};
+\node (2) [above=14mm of 1] {};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
+\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
-\node (a) [right=of 2] {$\ldots$};
-\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots\,$};
+\node (a1) [right=of a] {$$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
@@ -580,21 +668,46 @@
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
-\only<2>{
-\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
-\path[->] (1) edge node [below] {\alert{$\epsilon$}} (3);
-}
\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<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}
-\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}
-\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}
-\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}
-\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};
+\node [yshift=3mm] at (1.north) {$r_1$};
+\node [yshift=3mm] at (2.north) {$r_2$};
\end{pgfonlayer}
-\end{tikzpicture}
+\end{tikzpicture}}
+\only<2>{%
+\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.center)]
+\node at (0,0) (1) {$\mbox{}$};
+\node (2) [above=14mm of 1] {$$};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
+\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
+
+\node (a) [right=of 2] {$\ldots\,$};
+\node (a1) [right=of a] {$$};
+\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
+\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
+
+\node (b) [right=of 3] {$\ldots$};
+\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
+\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
+\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
+
+%\path[->] (1) edge node [above] {$\epsilon$} (2);
+%\path[->] (1) edge node [below] {$\epsilon$} (3);
+
+\begin{pgfonlayer}{background}
+\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};
+\node [yshift=3mm] at (3.north) {$r_1+ r_2$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+%
\small
+\mbox{}\\\medskip
We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -603,37 +716,48 @@
\begin{frame}[c]
\frametitle{Case $r^*$}
-\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
+\onslide<1->{By recursion we are given an automaton for $r$:\smallskip}
-\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{}$};}
-\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};}
-\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
+\hspace{2cm}
+\only<1>{\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.north)]
+\node (2) {$\mbox{}$};
+\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state, initial] (5) [below=1mm of 2] {$\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->{
+\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
+\begin{pgfonlayer}{background}
+\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
+\node [yshift=3mm] at (1.north) {$r$};
+\end{pgfonlayer}
+\end{tikzpicture}}
+\only<2->{\begin{tikzpicture}[node distance=3mm,
+ >=stealth',very thick,
+ every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
+ baseline=(current bounding box.north)]
+\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
+\node (2) [right=16mm of 1] {$\mbox{}$};
+\node[state] (4) [above=1mm of 2] {$\mbox{}$};
+\node[state] (5) [below=1mm of 2] {$\mbox{}$};
+\node (a) [right=of 2] {$\ldots$};
\node[state] (a1) [right=of a] {$\mbox{}$};
\node[state] (a2) [above=of a1] {$\mbox{}$};
-\node[state] (a3) [below=of a1] {$\mbox{}$};}
-\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);
-\path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1);
-
-}
+\node[state] (a3) [below=of a1] {$\mbox{}$};
+\path[->] (1) edge node [below] {$\epsilon$} (4);
+\path[->] (1) edge node [below] {$\epsilon$} (5);
+\path[->] (a1) edge [bend left=45] node [below] {$\epsilon$} (1);
+\path[->] (a2) edge [bend right] node [below] {$\epsilon$} (1);
+\path[->] (a3) edge [bend left=45] node [below] {$\epsilon$} (1);
\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<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
-\only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};}
+\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
+\node [yshift=3mm] at (2.north) {$r^*$};
\end{pgfonlayer}
-\end{tikzpicture}\bigskip
+\end{tikzpicture}}
+\bigskip
\onslide<3->{
Why can't we just have an epsilon transition from the accepting states to the starting state?}
@@ -648,16 +772,16 @@
\begin{textblock}{5}(1,1)
\begin{center}
-\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
+\begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial] (q_0) {$q_0$};
-\node[state] (q_1) [above=of q_0] {$q_1$};
-\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
-\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
-\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
-\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
-\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
-\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{Q}_2$};
+\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_1);
+\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_2);
+\path[->] (Q_0) edge [loop right] node {\alert{$a$}} ();
+\path[->] (Q_1) edge [loop above] node {\alert{$a$}} ();
+\path[->] (Q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{center}
\end{textblock}
@@ -748,14 +872,14 @@
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial] (q_0) {$q_0$};
-\node[state] (q_1) [above=of q_0] {$q_1$};
-\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
-\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
-\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
-\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
-\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
-\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
+\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{Q}_2$};
+\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_1);
+\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_2);
+\path[->] (Q_0) edge [loop right] node {\alert{$a$}} ();
+\path[->] (Q_1) edge [loop above] node {\alert{$a$}} ();
+\path[->] (Q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{tabular}
\end{center}
@@ -809,20 +933,20 @@
\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);
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (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}
@@ -842,15 +966,15 @@
\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 {$\mbox{Q}_0$};
+\draw (1.5,-0.5) node {$\mbox{Q}_1$};
+\draw (2.5,-0.5) node {$\mbox{Q}_2$};
+\draw (3.5,-0.5) node {$\mbox{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 {$\mbox{Q}_1$};
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
+\draw (-0.5, 0.5) node {$\mbox{Q}_4$};
\draw (0.5,0.5) node {\large$\star$};
\draw (1.5,0.5) node {\large$\star$};
@@ -869,20 +993,20 @@
\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);
+\node[state,initial] (Q_0) {$\mbox{Q}_0$};
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\node[state, accepting] (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}
&
\raisebox{9mm}{\begin{tikzpicture}[scale=0.6,line width=0.8mm]
@@ -898,15 +1022,15 @@
\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 {$\mbox{Q}_0$};
+\draw (1.5,-0.5) node {$\mbox{Q}_1$};
+\draw (2.5,-0.5) node {$\mbox{Q}_2$};
+\draw (3.5,-0.5) node {$\mbox{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 {$\mbox{Q}_1$};
+\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
+\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
+\draw (-0.5, 0.5) node {$\mbox{Q}_4$};
\draw (0.5,0.5) node {\large$\star$};
\draw (1.5,0.5) node {\large$\star$};
@@ -926,14 +1050,14 @@
\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$}} ();
+\node[state,initial] (Q_02) {$\mbox{Q}_{0, 2}$};
+\node[state] (Q_13) [right=of Q_02] {$\mbox{Q}_{1, 3}$};
+\node[state, accepting] (Q_4) [right=of Q_13] {$\mbox{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}
@@ -951,33 +1075,33 @@
\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>{\node[state,initial] (q_0) {$q_0$};}
-\only<2->{\node[state,accepting] (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$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
-\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}
+\only<1>{\node[state,initial] (Q_0) {$\mbox{Q}_0$};}
+\only<2->{\node[state,accepting] (Q_0) {$\mbox{Q}_0$};}
+\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
+\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
+\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
+\only<1>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
+\only<2->{\node[state, initial right] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
\only<1-2>{
-\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 above] 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);}
+\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 above] 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);}
\only<3->{
-\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 above] 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);}
+\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 above] 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{}\\[-18mm]
@@ -1025,12 +1149,12 @@
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
- \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
- \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};}
- \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
- \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
- \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
- \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \only<1>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<1>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<2->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<1>{\node[state, accepting] (q2) at ( 2,1) {$\mbox{Q}_2$};}
+ \only<2->{\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)
@@ -1052,9 +1176,9 @@
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
- \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
- \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
- \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \only<1->{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<1->{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<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)
@@ -1069,9 +1193,9 @@
You know how to solve since school days, no?
\begin{center}
\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$2\, \mbox{Q}_0 + 3 \,\mbox{Q}_1 + 4\, \mbox{Q}_2$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$2 \,\mbox{Q}_0 + 3\, \mbox{Q}_1 + 1\, \mbox{Q}_2$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$1\, \mbox{Q}_0 + 5\, \mbox{Q}_1 + 2\, \mbox{Q}_2$}\\
\end{tabular}
\end{center}
@@ -1086,9 +1210,9 @@
\begin{center}
\begin{tikzpicture}[scale=2,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
- \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
- \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
- \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
+ \only<1->{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<1->{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<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)
@@ -1102,9 +1226,9 @@
\onslide<2->{
\begin{center}
\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
+\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}