Mercurial > 14ss.theoinf

comparison notes/tex/automata.tex @ 27:f7bcd68a0c12

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
26:c7069de7eb0f 27:f7bcd68a0c12
669 669
670 \begin{center} 670 \begin{center}
671 \begin{tikzpicture}[node distance=2cm] 671 \begin{tikzpicture}[node distance=2cm]
672 \node (nfa) {NFA}; 672 \node (nfa) {NFA};
673 \node (dfa) [left of=nfa] {DFA}; 673 \node (dfa) [left of=nfa] {DFA};
674 \node (lg) [left of=dfa] {RLG};
674 \node (enfa) [right of=nfa] {$\epsilon$-NFA}; 675 \node (enfa) [right of=nfa] {$\epsilon$-NFA};
675 \node (re) [below of=nfa] {RE}; 676 \node (re) [below of=nfa] {RE};
676 677
678 \draw [every edge, <->] (lg) -- (dfa);
677 \draw [every edge] (nfa) -- (dfa); 679 \draw [every edge] (nfa) -- (dfa);
678 \draw [every edge] (enfa) -- (nfa); 680 \draw [every edge] (enfa) -- (nfa);
679 \draw [every edge] (dfa) -- (re); 681 \draw [every edge] (dfa) -- (re);
680 \draw [every edge] (nfa) -- (re);
681 \draw [every edge] (re) -- (enfa); 682 \draw [every edge] (re) -- (enfa);
682 \end{tikzpicture} 683 \end{tikzpicture}
683 \end{center} 684 \end{center}
684 685
685 \vfill 686 \vfill
686 687
687 \begin{theorem} 688 \begin{theorem}
688 Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}: 689 Für eine Darstellung $D$ einer regulären Sprache ist \alert{entscheidbar}:
689 \vspace{1em} 690 \vspace{1em}
690 \begin{description} 691 \begin{description}[Endlichkeitsproblem\quad]
691 \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$? 692 \item[Wortproblem] Gegeben $w$, gilt $w \in L(D)$?
692 \item[Leerheitsproblem] Ist $L(D) = \emptyset$? 693 \item[Leerheitsproblem] Ist $L(D) = \emptyset$?
693 \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$? 694 \item[Endlichkeitsproblem] Ist $|L(D)| < \infty$?
694 \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$? 695 \item[Äquivalenzproblem] Gilt $L(D_1) = L(D_2)$?
695 \end{description} 696 \end{description}