# HG changeset patch # User Markus Kaiser # Date 1398527408 -7200 # Node ID e1b3b7b99d28cd87af934245529363c169502789 # Parent f96446e678c89e6c5f407523744eaae999b89f68 second notes and sheet diff -r f96446e678c8 -r e1b3b7b99d28 notes/tex/automatons.tex --- a/notes/tex/automatons.tex Thu Apr 24 09:04:24 2014 +0200 +++ b/notes/tex/automatons.tex Sat Apr 26 17:50:08 2014 +0200 @@ -27,18 +27,17 @@ \frametitle{DFA} \begin{definition}[Deterministischer endlicher Automat] - Ein \alert{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem + Ein \structure{DFA} ist ein Tupel $M = (Q, \Sigma, \delta, q_0, F)$ aus einer/einem \begin{itemize} - \item endlichen Menge von \alert{Zuständen} $Q$ - \item endlichen \alert{Eingabealphabet} $\Sigma$ - \item totalen \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ - \item \alert{Startzustand} $q_0 \in Q$ - \item Menge von \alert{Endzuständen} $F \subseteq Q$ + \item endlichen Menge von \structure{Zuständen} $Q$ + \item endlichen \structure{Eingabealphabet} $\Sigma$ + \item totalen \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to Q$ + \item \structure{Startzustand} $q_0 \in Q$ + \item Menge von \structure{Endzuständen} $F \subseteq Q$ \end{itemize} \end{definition} \vfill - \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] @@ -61,15 +60,14 @@ \begin{frame} \frametitle{NFA} \begin{definition}[Nicht-Deterministischer endlicher Automat] - Ein \alert{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + Ein \structure{NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA - \item \alert{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ \end{itemize} \end{definition} \vfill - \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=20, initial text=] @@ -82,15 +80,14 @@ \begin{frame} \frametitle{$\epsilon$-NFA} \begin{definition}[NFA mit $\epsilon$-Übergängen] - Ein \alert{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit + Ein \structure{$\epsilon$-NFA} ist ein Tupel $N = (Q, \Sigma, \delta, q_0, F)$ mit \begin{itemize} \item $Q, \Sigma, q_0, F$ wie ein DFA - \item \alert{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ \end{itemize} \end{definition} \vfill - \pause \begin{center} \begin{tikzpicture}[shorten >=1pt, node distance = 3cm, auto, bend angle=30, initial text=] @@ -329,17 +326,23 @@ \frametitle{NFA $\rightarrow$ DFA} \setbeamercovered{dynamic} - \begin{block}{Idee (Potenzmengenkonstruktion)} - Konstruiere aus einem NFA $N = (Q, \Sigma, \delta, q_0, F)$ einen DFA $D = (P(Q), \Sigma, \overline{\delta}, \{q_0\}, F_M)$ mit Zuständen aus \alert{$P(Q)$}. + \begin{block}{Potenzmengenkonstruktion} + Konstruiere einen Automaten, der \structure{alle möglichen Pfade} gleichzeitig berücksichtigt. + Gegeben ein NFA $(Q, \Sigma, \delta, q_0, F)$, konstruiere einen DFA mit Zuständen aus \alert{$\powerset{Q}$}. \begin{itemize} - \item $\overline{\delta}: \alert{P(Q)} \times \Sigma \to P(Q)$ \\ - \[\overline{\delta}(S, a) := \bigcup_{q \in S} \delta(q, a)\] - \item $F_M := \left\{S \subseteq Q \mid \alert{S \cap F} \neq \emptyset\right\}$ + \item Starte in $\left\{ q_0 \right\}$ + \item Die Übergangsfunktion speichert \structure{alle möglichen Schritte} + \begin{align} + \overline{\delta}: \alert{\powerset{Q}} \times \Sigma &\to \powerset{Q} \\ + (S, a) &\mapsto \bigcup_{q \in S} \delta(q, a) + \end{align} + \item $S$ ist Endzustand wenn $F \cap S \neq \emptyset$ \end{itemize} \end{block} \begin{tikzpicture}[automaton, bend angle=20, node distance=2.1cm] + \tikzstyle{every state}=[minimum width=1cm, pretty] \useasboundingbox (-1.4,2) rectangle (9, -2); \node[state, initial] (q0) {$q_0$}; diff -r f96446e678c8 -r e1b3b7b99d28 notes/tex/grammars.tex --- a/notes/tex/grammars.tex Thu Apr 24 09:04:24 2014 +0200 +++ b/notes/tex/grammars.tex Sat Apr 26 17:50:08 2014 +0200 @@ -131,6 +131,29 @@ \end{frame} } +\defineUnit{eindeutigkeit}{% +\begin{frame} + \frametitle{Eindeutigkeit} + + \begin{definition}[Linksableitung] + Eine Ableitung + \begin{align} + S \to^* x\alert{\alpha}z \to x\alert{\beta}z \to^* w + \end{align} + heißt \structure{Linksableitung}, wenn für jede Anwendung jeder Produktion $\alert{\alpha \to \beta}$ gilt, dass sich keine Regel in einem echten Präfix von $\structure{x\alpha}$ anwenden lässt. + \end{definition} + + \vfill + + \begin{definition}[Eindeutigkeit] + \begin{itemize} + \item Eine Grammatik heißt \structure{eindeutig}, wenn es für jedes Wort genau eine Linksableitung gibt. + \item Eine Sprache heißt \structure{eindeutig}, wenn es für sie eine eindeutige Grammatik gibt. + \end{itemize} + \end{definition} +\end{frame} +} + \defineUnit{cnf}{% \begin{frame} \frametitle{CNF} diff -r f96446e678c8 -r e1b3b7b99d28 notes/tex/ue02_notes.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/notes/tex/ue02_notes.tex Sat Apr 26 17:50:08 2014 +0200 @@ -0,0 +1,16 @@ +\input{preamble.tex} +\input{frames.tex} + +\title{Übung 2: Eindeutigkeit und Automaten} +\subtitle{Theoretische Informatik Sommersemester 2014} +\author{\href{mailto:markus.kaiser@in.tum.de}{Markus Kaiser}} + +\begin{document} +\showUnit{titel} +\showUnit{eindeutigkeit} +\showUnit{dfa} +\showUnit{nfa} +\showUnit{enfa} +\showUnit{endlicheautomaten} +\showUnit{nfazudfa} +\end{document} diff -r f96446e678c8 -r e1b3b7b99d28 notes/ue02_notes.pdf Binary file notes/ue02_notes.pdf has changed diff -r f96446e678c8 -r e1b3b7b99d28 ue02.pdf Binary file ue02.pdf has changed