presentation

3 files changed, 47 insertions, 13 deletions

diff --git a/presentation/J00-1005.pdf b/presentation/J00-1005.pdf
deleted file mode 100644
index 90f4704..0000000
--- a/presentation/J00-1005.pdf
+++ /dev/null
diff --git a/presentation/simianer-regexvis.pdf b/presentation/simianer-regexvis.pdf
index f0e1a0d..346039c 100644
--- a/presentation/simianer-regexvis.pdf
+++ b/presentation/simianer-regexvis.pdf
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}