# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1350460021 -3600
# Node ID e5fb17c02508da9c519a4b88848ad25c9a6067c3
# Parent  cad34315db1b8a1372bb0c527340df9d76980296
tuned

diff -r cad34315db1b -r e5fb17c02508 regexp3.scala
--- a/regexp3.scala	Wed Oct 17 08:24:00 2012 +0100
+++ b/regexp3.scala	Wed Oct 17 08:47:01 2012 +0100
@@ -48,8 +48,7 @@
 // derivative of a regular expression w.r.t. a character
 def der (c: Char, r: Rexp) : Rexp = r match {
   case NULL => NULL
-  case EMPTY => NULL
-  case CHAR(d) => if (c == d) EMPTY else NULL
+  case EMPTY => NULL  case CHAR(d) => if (c == d) EMPTY else NULL
   case ALT(r1, r2) => ALT(der(c, r1), der(c, r2))
   case SEQ(r1, r2) => 
     if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
diff -r cad34315db1b -r e5fb17c02508 slides04.pdf
Binary file slides04.pdf has changed
diff -r cad34315db1b -r e5fb17c02508 slides04.tex
--- a/slides04.tex	Wed Oct 17 08:24:00 2012 +0100
+++ b/slides04.tex	Wed Oct 17 08:47:01 2012 +0100
@@ -283,8 +283,8 @@
 
 \begin{itemize}
 \item start can be an accepting state
-\item there is no accepting state
-\item all states are accepting
+\item it is possible that there is no accepting state
+\item all states might be accepting (but does not necessarily mean all strings are accepted)
 \end{itemize}
 
 \end{frame}}
@@ -503,6 +503,28 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+
+\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} tests wether
+\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 chance.
+\item All unmarked pairs can be merged.
+\end{enumerate}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
@@ -569,20 +591,7 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
 
-Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.
-(a) Find a regular expression that recognises the two strings \bl{$ab$} and \bl{$ac$}. (b)
-Find a regular expression that matches all strings \emph{except} these two strings.
-Note, you can only use regular expressions of the form 
-\begin{center}
-\bl{$r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 \end{document}