Mercurial > 14ss.theoinf

comparison notes/tex/grammars.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 44fd483bde00
children
comparison
equal deleted inserted replaced
26:c7069de7eb0f 27:f7bcd68a0c12
761 761
762 \begin{center} 762 \begin{center}
763 \begin{tikzpicture}[node distance=3cm] 763 \begin{tikzpicture}[node distance=3cm]
764 \node (CFG) {CFG}; 764 \node (CFG) {CFG};
765 \node (CNF) [right of = CFG] {CNF}; 765 \node (CNF) [right of = CFG] {CNF};
766 \node (PDAe) [right of = CNF] {PDA$_\epsilon$}; 766 \node (GNF) [right of = CNF] {GNF};
767 \node (PDAf) [right of = PDAe] {PDA$_F$}; 767 \node (PDAf) [below = 1.5cm of GNF] {PDA$_F$};
768 \node (PDAe) [below = 1.5cm of CNF] {PDA$_\epsilon$};
768 769
769 \draw [every edge, <->] (CFG) -- (CNF); 770 \draw [every edge, <->] (CFG) -- (CNF);
770 \draw [every edge, <->] (CNF) -- (PDAe); 771 \draw [every edge, ->] (CNF) -- (GNF);
772 \draw [every edge, ->] (GNF) -- (PDAe);
771 \draw [every edge, <->] (PDAe) -- (PDAf); 773 \draw [every edge, <->] (PDAe) -- (PDAf);
774 \draw [every edge, ->] (PDAe) -- (CFG);
772 \end{tikzpicture} 775 \end{tikzpicture}
773 \end{center} 776 \end{center}
774 777
775 \vfill 778 \vfill
776 779
777 \begin{itemize} 780 \begin{itemize}
778 \item \alert{Abschlusseigenschaften} 781 \item Abschlusseigenschaften
779 \end{itemize} 782 \end{itemize}
780 \begin{table} 783 \begin{table}
781 \begin{tabu}to \textwidth{X[c]|ccccc} 784 \begin{tabu}to \textwidth{X[c]|ccccc}
782 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} 785 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
783 REG & ja & ja & ja & ja & ja\\ 786 REG & ja & ja & ja & ja & ja\\
784 CFL & nein & ja & nein & ja & ja 787 CFL & nein & ja & nein & ja & ja
785 \end{tabu} 788 \end{tabu}
786 \end{table} 789 \end{table}
787 790
788 \begin{itemize} 791 \begin{itemize}
789 \item \alert{Entscheidbarkeit} 792 \item Entscheidbarkeit
790 \end{itemize} 793 \end{itemize}
791 \begin{table} 794 \begin{table}
792 \begin{tabu}to \textwidth{X[c]|cccc} 795 \begin{tabu}to \textwidth{X[c]|cccc}
793 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} 796 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
794 DFA & $\Oh(n)$ & ja & ja & ja \\ 797 DFA & $\Oh(n)$ & ja & ja & ja \\