Mercurial > 14ss.theoinf
diff notes/tex/automata.tex @ 27:f7bcd68a0c12
eigth sheet and notes; add hierarchy slides
author | Markus Kaiser <markus.kaiser@in.tum.de> |
---|---|
date | Fri, 06 Jun 2014 17:13:58 +0200 |
parents | 0f7daeda8363 |
children | 112bd0d1fa86 |
line wrap: on
line diff
--- a/notes/tex/automata.tex Sun Jun 01 00:30:12 2014 +0200 +++ b/notes/tex/automata.tex Fri Jun 06 17:13:58 2014 +0200 @@ -671,13 +671,14 @@ \begin{tikzpicture}[node distance=2cm] \node (nfa) {NFA}; \node (dfa) [left of=nfa] {DFA}; + \node (lg) [left of=dfa] {RLG}; \node (enfa) [right of=nfa] {$\epsilon$-NFA}; \node (re) [below of=nfa] {RE}; + \draw [every edge, <->] (lg) -- (dfa); \draw [every edge] (nfa) -- (dfa); \draw [every edge] (enfa) -- (nfa); \draw [every edge] (dfa) -- (re); - \draw [every edge] (nfa) -- (re); \draw [every edge] (re) -- (enfa); \end{tikzpicture} \end{center} @@ -687,7 +688,7 @@ \begin{theorem} Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}: \vspace{1em} - \begin{description} + \begin{description}[Endlichkeitsproblem\quad] \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? \item[Leerheitsproblem] Ist $L(D) = \emptyset$? \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?