Mercurial > 14ss.theoinf
changeset 11:de844d67518b
fix powersets; wording
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Sat, 26 Apr 2014 21:10:36 +0200 |
parents | e1b3b7b99d28 |
children | 11723d02ee58 |
files | notes/tex/automatons.tex notes/tex/grammars.tex notes/ue02_notes.pdf |
diffstat | 3 files changed, 8 insertions(+), 8 deletions(-) [+] |
line wrap: on
line diff
--- a/notes/tex/automatons.tex Sat Apr 26 17:50:08 2014 +0200 +++ b/notes/tex/automatons.tex Sat Apr 26 21:10:36 2014 +0200 @@ -63,7 +63,7 @@ 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 \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to P(Q)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \Sigma \to \powerset{Q}$ \end{itemize} \end{definition} @@ -83,7 +83,7 @@ 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 \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to P(Q)$ + \item \structure{Übergangsfunktion} $\delta : Q \times \left( \Sigma \cup \{\epsilon\} \right) \to \powerset{Q}$ \end{itemize} \end{definition} @@ -105,8 +105,8 @@ \begin{description} \item[DFA] $\delta : Q \times \Sigma \to Q$ - \item[NFA] $\delta : Q \times \Sigma \to \alert{P(Q)}$ - \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{P(Q)}$ + \item[NFA] $\delta : Q \times \Sigma \to \alert{\powerset{Q}}$ + \item[$\epsilon$-NFA] $\delta : Q \times \alert{\left( \Sigma \cup \{\epsilon\} \right)} \to \alert{\powerset{Q}}$ \end{description} \end{block} @@ -334,7 +334,7 @@ \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} \\ + \overline{\delta}: \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$
--- a/notes/tex/grammars.tex Sat Apr 26 17:50:08 2014 +0200 +++ b/notes/tex/grammars.tex Sat Apr 26 21:10:36 2014 +0200 @@ -135,12 +135,12 @@ \begin{frame} \frametitle{Eindeutigkeit} - \begin{definition}[Linksableitung] + \begin{definition}[kontextfreie Linksableitung] Eine Ableitung \begin{align} - S \to^* x\alert{\alpha}z \to x\alert{\beta}z \to^* w + S \to^* \structure{x}\alert{A}z \to \structure{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. + heißt (kontextfreie) \structure{Linksableitung}, wenn für jede Anwendung jeder Produktion $\alert{A \to \beta}$ gilt, dass in \structure{$x$} kein Nichtterminal vorkommt. \end{definition} \vfill