# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1539069385 -3600
# Node ID bd4f144326c776d40d117b03378514617b3a0e85
# Parent  711bbc480998c31c876d4cc8cfa99e90498397d2
updated

diff -r 711bbc480998 -r bd4f144326c7 slides/slides03.pdf
Binary file slides/slides03.pdf has changed
diff -r 711bbc480998 -r bd4f144326c7 slides/slides03.tex
--- a/slides/slides03.tex	Mon Oct 08 11:35:04 2018 +0100
+++ b/slides/slides03.tex	Tue Oct 09 08:16:25 2018 +0100
@@ -50,23 +50,6 @@
 \end{frame}
 %%%%%%%%%%%
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Regular Expressions}
-
-In programming languages they are often used to recognise:\medskip
-
-\begin{itemize}
-\item symbols, digits
-\item identifiers
-\item numbers (non-leading zeros)
-\item keywords
-\item comments
-\end{itemize}\bigskip
-
-\mbox{}\hfill\bl{\url{http://www.regexper.com}}
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -150,10 +133,10 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
+\begin{frame}[t]
 \frametitle{Simplification}
 
-Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
+Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
 
 \begin{center}
 \def\arraystretch{2}  
@@ -297,7 +280,7 @@
 
 \begin{itemize}
 \item an alphabet \bl{$\varSigma$}  
-\item a set of states \bl{$\mbox{Q}$}
+\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 
@@ -308,7 +291,7 @@
 \end{itemize}
 
 \begin{center}
-\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
 \end{center}
 
 \end{frame}
@@ -370,7 +353,7 @@
 Given
 
 \begin{center}
-\bl{$A(\varSigma, \mbox{Q}, \mbox{Q}_0, F, \delta)$}
+\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
 \end{center}
 
 you can define
@@ -477,6 +460,45 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{Another Example}
+
+For the regular expression \bl{$(.^*)a\,(.^{\{n\}})bc$}\bigskip\bigskip
+
+% \begin{center}
+\mbox{}\hspace{-11mm}
+	\begin{tikzpicture}[>=stealth',very thick, auto,
+	every state/.style={minimum size=5pt,inner sep=1pt,
+		draw=blue!50,very thick,fill=blue!20},scale=1, node distance=5mm,
+	decoration={brace,mirror,amplitude=7}]
+	\node[state,initial]  (Q_0)  {$\;0\;$};
+	\node[state] (Q_1) [right=of Q_0] {$\;1\;$};
+	\node[state] (Q_2) [right=of Q_1] {$\;2\;$};
+	\node (Q_3) [right=of Q_2] {$\hspace{-1mm}\ldots\hspace{-3mm}$};
+	\node[state] (Q_4) [right=of Q_3] {$\;\phantom{1}\;$};
+	\node (Q_5) [right=of Q_4] {$\hspace{-1mm}\ldots\hspace{-3mm}$};
+	\node[state] (Q_6) [right=of Q_5] {\tiny$n+1$};
+	\node[state] (Q_7) [right=of Q_6] {\tiny$n+2$};
+	\node[state,accepting] (Q_8) [right=of Q_7] {\tiny$n+3$};
+	
+	\path[->] (Q_0) edge [loop above] node {$*$} ();
+	\path[->] (Q_0) edge node [above] {$a$} (Q_1);
+	\path[->] (Q_1) edge node [above] {$*$} (Q_2);
+	\path[->] (Q_2) edge node [above] {$*$} (Q_3);
+	\path[->] (Q_4) edge node [above] {$*$} (Q_5);
+	\path[->] (Q_5) edge node [above] {$*$} (Q_6);
+	\path[->] (Q_6) edge node [above] {$b$} (Q_7);
+	\path[->] (Q_7) edge node [above] {$c$} (Q_8);
+	
+	\draw [decorate] ([yshift=-5mm]Q_1.east) --node[below=3mm]{$n$} ([yshift=-5mm]Q_6.west);
+	\end{tikzpicture}\bigskip
+
+
+{\small Note the star-transitions: accept any character.}
+        
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 \frametitle{Two Epsilon NFA Examples}
 
 \small
diff -r 711bbc480998 -r bd4f144326c7 slides/slides04.tex
--- a/slides/slides04.tex	Mon Oct 08 11:35:04 2018 +0100
+++ b/slides/slides04.tex	Tue Oct 09 08:16:25 2018 +0100
@@ -32,7 +32,26 @@
   \end{tabular}
   \end{center}
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regular Expressions}
+
+In programming languages they are often used to recognise:\medskip
+
+\begin{itemize}
+\item symbols, digits
+\item identifiers
+\item numbers (non-leading zeros)
+\item keywords
+\item comments
+\end{itemize}\bigskip
+
+\mbox{}\hfill\bl{\url{http://www.regexper.com}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]