From cde3febf76396e200e1cf8d922329af5cb5f0b32 Mon Sep 17 00:00:00 2001
From: Patrick Simianer <p@simianer.de>
Date: Thu, 10 Jun 2010 02:05:49 +0200
Subject: presentation

---
 presentation/J00-1005.pdf          | Bin 925842 -> 0 bytes
 presentation/simianer-regexvis.pdf | Bin 683793 -> 716276 bytes
 presentation/simianer-regexvis.tex |  60 +++++++++++++++++++++++++++++--------
 3 files changed, 47 insertions(+), 13 deletions(-)
 delete mode 100644 presentation/J00-1005.pdf

(limited to 'presentation')

diff --git a/presentation/J00-1005.pdf b/presentation/J00-1005.pdf
deleted file mode 100644
index 90f4704..0000000
Binary files a/presentation/J00-1005.pdf and /dev/null differ
diff --git a/presentation/simianer-regexvis.pdf b/presentation/simianer-regexvis.pdf
index f0e1a0d..346039c 100644
Binary files a/presentation/simianer-regexvis.pdf and b/presentation/simianer-regexvis.pdf differ
diff --git a/presentation/simianer-regexvis.tex b/presentation/simianer-regexvis.tex
index ceff30e..a232673 100644
--- a/presentation/simianer-regexvis.tex
+++ b/presentation/simianer-regexvis.tex
@@ -68,7 +68,7 @@
 
 \subsection{"Uberlegungen}
 \begin{frame}
-    \frametitle{Visualisierung regul"arer Ausdr"ucke /1}
+    \frametitle{Visualisierung regul"arer Ausdr"ucke}
 	
 	\begin{itemize}
         \item[] Wie soll die Visualisierung aussehen?
@@ -79,7 +79,7 @@
         \item[]
 	\end{itemize}
     \begin{enumerate}
-        \item Zu Hauf zu vorhanden, \\ basierend auf RE-Implementierung der jeweiligen Sprache\\ $\rightarrow$ keine ``\textit{step by step}''-Visualisierung m"oglich
+        \item Es existieren bereits viele Implementierungen, \\ basierend auf RE-Implementierung der jeweiligen Sprache\\ $\rightarrow$ keine ``\textit{step by step}''-Visualisierung m"oglich
         \item Grafische Umsetzung schwierig,\\ eigene RE-Implementierung n"otig\\ $\rightarrow$ jeder Schritt nachvollziehbar
     \end{enumerate}
 \end{frame}
@@ -115,7 +115,7 @@
 	\begin{enumerate}
 		\item \textbf{Parsen} des Ausdrucks
 		\item Umsetzung in einen \textbf{nichtdeterministischen endlichen Automaten}
-		\item Übersetzung des NDEA in einen \textbf{deterministischen} endlichen Automaten
+		\item Übersetzung eine NDEA in einen \textbf{deterministischen} endlichen Automaten
 		\item Grafische \textbf{Darstellung} des Automaten und dessen \textbf{Simulation}
 		\item[]
 		\item[] Umsetzung im \textbf{Browser}: \textit{JavaScript} (\textit{Rapha\"el} f"ur \textit{SVG}, \textit{jQuery}), \textit{HTML}+\textit{CSS}
@@ -184,6 +184,7 @@ RegexParser.prototype.expr = function() {
     \item Nahezu direktes "Ubersetzen einer Grammatik\footnote{keine Links-Rekursionen, sonst: Endlosschleife} in den Quelltext des Parsers (LL(1))
     \item $\forall$ Nichtterminale $\exists$ Funktion, welche die rechte Seite der jeweiligen Regel behandelt
     \item Direkte Erzeugung des NDEA, mittels Konstruktion nach Thompson
+    \item Max. $2m$ Zust"ande, $4m$ Transitionen ($m$ L"ange des Alphabets)
     %\item Schnell, einfach und effizient
 \end{itemize}
 
@@ -254,23 +255,49 @@ RegexParser.prototype.expr = function() {
         \textbf{Pseudo-Code} 
         \hrule
         \begin{columns}
-        \column{5cm}
-\lstset{language=C++, emph={epsclosure,move}}
+        \column{4.5cm}
+\lstset{language=C++, emph={epsclosure,add,move,pop,push,stack,foreach}}
 \begin{lstlisting}
-epsclosure(NFAState) {
-
+epsclosure(dState): stack s
+foreach nState in dState {
+ s.push(nState)
+}
+while s not empty { 
+ nState1 = s.pop()
+ foreach nState1 e> nState2 {
+  if nState2 not in dState {
+   dState.add(nState2)
+   s.push(nState2)
+  }
+ }
 }
+return dState
 \end{lstlisting}
 
-        \column{5cm}
-\lstset{language=C++, emph={move}}        
+        \column{4.3cm}
+\lstset{language=C++, emph={nfa2dfa,add,DFA,NFA,stack,epsclosure,move,pop,push,foreach}}        
 \begin{lstlisting}
-nfa2dfa(NFA) {
-
+nfa2dfa(NFA): stack s, DFA d
+s.push(epsclosure(nfa.start))
+d.add(epsclosure(nfa.start))
+while s not empty {
+ dState1 = s.pop()
+ foreach ch in ALPHA {
+  dState2 = move(dState1, ch)
+  next = epsclosure(dState2)
+  if next not in DFA {
+   d.add(dState ch> next)
+  }
+ }
 }
+return d
 \end{lstlisting}
 
         \end{columns}
+\begin{itemize}
+    \item $\forall p \in Q : E(\{p\}) = \{ q \in Q : p \rightarrow_\epsilon q \}$
+    \item \textbf{Laufzeit:} $O(nm^2)$ (bei Vorberechung aller $\epsilon$-Abschl"usse: $O(m)$)  
+\end{itemize}
 \end{frame}
 
 
@@ -289,6 +316,8 @@ nfa2dfa(NFA) {
 \begin{frame}[plain]
 
 \begin{center}
+    \frametitle{NDEA $\rightarrow$ DEA Beispiel /2}
+    
     \begin{tabular}{c|c|c}
         Dfa ID & Symbol & $\rightarrow$Dfa ID\\
         \hline
@@ -320,7 +349,7 @@ nfa2dfa(NFA) {
 \end{frame}
 
 \begin{frame}
-    \frametitle{Resourcen}
+    \frametitle{Ressourcen}
 
     \begin{itemize}
         \item \textit{Rapha\"el} JavaScript SVG Library (\url{http://raphaeljs.com/})
@@ -345,7 +374,12 @@ nfa2dfa(NFA) {
     \frametitle{Weiterentwicklung}
 
     \begin{itemize}
-        \item Vorhanden: * | ()
+        \item Vorhanden: $*$, \texttt{|}, \texttt{()}
+        \item[]
+        \item Zeichenklassen: \texttt{.}, \texttt{\textbackslash w}, \texttt{\textbackslash d},  \lbrack\ \rbrack, $\hdots$ $\rightarrow$ Einfach implementierbar, Vorverarbeitung der Eingabe
+        \item Operatoren: $+$, ?, \{$m$, $n$\}, $\hdots$ $\rightarrow$ Ebenfalls durch Vorverarbeitung l"osbar, beziehungsweise durch Anpassung des Automaten
+        \item[]
+        \item \textit{Lookahead} oder \textit{lookbehind} sind leider nicht mit endlichen Automaten zu implementieren, da die zugrunde liegenden Grammatiken nicht mehr regul"ar w"aren.
     \end{itemize}
 \end{frame}
 
-- 
cgit v1.2.3