Mercurial > 14ss.theoinf

comparison notes/tex/computation.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 efd13093bd47
children b56fe50e0132
comparison
equal deleted inserted replaced
26:c7069de7eb0f 27:f7bcd68a0c12
2 \begin{frame} 2 \begin{frame}
3 \frametitle{Turingmaschinen} 3 \frametitle{Turingmaschinen}
4 \setbeamercovered{dynamic} 4 \setbeamercovered{dynamic}
5 5
6 \begin{definition}[Turingmaschine] 6 \begin{definition}[Turingmaschine]
7 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 7 Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
8 \begin{itemize} 8 \begin{itemize}
9 \item endlichen Menge von \alert{Zuständen} $Q$ 9 \item endlichen Menge von \structure{Zuständen} $Q$
10 \item endlichen \alert{Eingabealphabet} $\Sigma$ 10 \item endlichen \structure{Eingabealphabet} $\Sigma$
11 \item endlichen \alert{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$ 11 \item endlichen \structure{Bandalphabet} $\Gamma$ mit $\Sigma \subset \Gamma$
12 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ 12 \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
13 \item \alert{Startzustand} $q_0 \in Q$ 13 \item \structure{Startzustand} $q_0 \in Q$
14 \item \alert{Leerzeichen} $\square \in \Gamma \setminus \Sigma$ 14 \item \structure{Leerzeichen} $\square \in \Gamma \setminus \Sigma$
15 \item Menge von \alert{Endzuständen} $F \subseteq Q$ 15 \item Menge von \structure{Endzuständen} $F \subseteq Q$
16 \end{itemize} 16 \end{itemize}
17 \end{definition} 17 \end{definition}
18 \end{frame} 18 \end{frame}
19 } 19 }
20 20
22 \begin{frame} 22 \begin{frame}
23 \frametitle{Turingmaschinen} 23 \frametitle{Turingmaschinen}
24 \setbeamercovered{dynamic} 24 \setbeamercovered{dynamic}
25 25
26 \begin{definition}[Turingmaschine] 26 \begin{definition}[Turingmaschine]
27 Eine deterministische \alert{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 27 Eine deterministische \structure{Turingmaschine (TM)} ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
28 \begin{itemize} 28 \begin{itemize}
29 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$ 29 \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to Q \times \Gamma \times \left\{ L, R, N \right\}$
30 \end{itemize} 30 \end{itemize}
31 \end{definition} 31 \end{definition}
32 32
33 \vfill 33 \vfill
34 34
68 \begin{frame} 68 \begin{frame}
69 \frametitle{Turingmaschinen} 69 \frametitle{Turingmaschinen}
70 \setbeamercovered{dynamic} 70 \setbeamercovered{dynamic}
71 71
72 \begin{definition}[Konfiguration] 72 \begin{definition}[Konfiguration]
73 Eine \alert{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\ 73 Eine \structure{Konfiguration} ist ein Tripel $(\alpha, q, \beta) \in \Gamma^* \times Q \times \Gamma^*$. \\
74 Dies modelliert eine TM mit: 74 Dies modelliert eine TM mit:
75 \begin{itemize} 75 \begin{itemize}
76 \item \alert{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$ 76 \item \structure{Bandinhalt} $\ldots\square\alpha\beta\square\ldots$
77 \item \alert{Zustand} $q$ 77 \item \structure{Zustand} $q$
78 \item Kopf auf dem \alert{ersten Zeichen} von $\beta\square$ 78 \item Kopf auf dem \structure{ersten Zeichen} von $\beta\square$
79 \end{itemize} 79 \end{itemize}
80 Die \alert{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$. 80 Die \structure{Startkonfiguration} bei Eingabe $w \in \Sigma^*$ ist $(\epsilon, q_0, w)$.
81 \end{definition} 81 \end{definition}
82 82
83 \vfill 83 \vfill
84 84
85 \only<1> { 85 \only<1> {
111 \end{center} 111 \end{center}
112 } 112 }
113 113
114 \only<2> { 114 \only<2> {
115 \begin{definition}[Akzeptanz] 115 \begin{definition}[Akzeptanz]
116 Eine TM $M$ \alert{akzeptiert} die Sprache 116 Eine TM $M$ \structure{akzeptiert} die Sprache
117 \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \] 117 \[ L(M) = \left\{ w \in \Sigma^* \mid \exists \alert{f \in F}, \alpha, \beta \in \Gamma^* . (\epsilon, q_0, w) \rightarrow_M^* (\alpha, \alert{f}, \beta) \right\} \]
118 \end{definition} 118 \end{definition}
119 } 119 }
120 \end{frame} 120 \end{frame}
121 } 121 }
124 \begin{frame} 124 \begin{frame}
125 \frametitle{Nichtdeterministische TM} 125 \frametitle{Nichtdeterministische TM}
126 \setbeamercovered{dynamic} 126 \setbeamercovered{dynamic}
127 127
128 \begin{definition}[Nichtdeterministische Turingmaschine] 128 \begin{definition}[Nichtdeterministische Turingmaschine]
129 Eine \alert{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem 129 Eine \structure{nichtdeterministische} Turingmaschine (TM) ist ein Tupel $M = (Q, \Sigma, \Gamma, \delta, q_0, \square, F)$ aus einer/einem
130 \begin{itemize} 130 \begin{itemize}
131 \item \ldots 131 \item \ldots
132 \item \alert{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$ 132 \item \structure{Übergangsfunktion} $\delta : Q \times \Gamma \to \mathcal{P} \left( Q \times \Gamma \times \left\{ L, R, N \right\} \right)$
133 \item \ldots 133 \item \ldots
134 \end{itemize} 134 \end{itemize}
135 \end{definition} 135 \end{definition}
136 136
137 \vfill 137 \vfill
138 138
139 \begin{theorem} 139 \begin{theorem}
140 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}. 140 Zu jeder nichtdeterministischen TM $N$ gibt es eine deterministische TM $M$ mit \alert{$L(N) = L(M)$}.
141 \end{theorem}
142 \end{frame}
143 }
144
145 \defineUnit{lba}{%
146 \begin{frame}
147 \frametitle{Linear Beschränkte Automaten}
148
149 \begin{definition}[Linear Beschränkte Automaten]
150 Eine TM heißt \structure{linear beschränkt (LBA)}, wenn sie den Bereich des Bandes, auf dem das Eingabewort steht, niemals verlässt.
151 \end{definition}
152
153 \vfill
154
155 \begin{theorem}[]
156 Die \structure{linear beschränkten NDTMs} akzeptieren genau die Klasse der \alert{kontextsensitiven Sprachen (Typ 1)}.
141 \end{theorem} 157 \end{theorem}
142 \end{frame} 158 \end{frame}
143 } 159 }
144 160
145 \defineUnit{chomsky}{% 161 \defineUnit{chomsky}{%
151 \begin{tikzpicture}[auto] 167 \begin{tikzpicture}[auto]
152 \tikzstyle{rect} = [thick]; 168 \tikzstyle{rect} = [thick];
153 \tikzstyle{caption} = [align=left, anchor=north west]; 169 \tikzstyle{caption} = [align=left, anchor=north west];
154 170
155 \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen}; 171 \chomsky{tumlightblue}{}{0}{Alle formalen Sprachen};
156 \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik}; 172 \chomsky{tumred}{}{1}{Typ 0 - Rekursiv aufzählbar\\Grammatik\\Turingmaschine, WHILE-Programm, $\mu$-rekursive Funktion};
157 \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik}; 173 \chomsky{tumblue}{}{2}{Typ 1 - Kontextsensitiv\\Längenmonotone Grammatik\\Linear Beschränkter Automat (LBA)};
158 \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal}; 174 \chomsky{tumorange}{}{3}{Typ 2 - Kontextfrei\\Links nur ein Nichtterminal\\Kellerautomat (PDA)};
159 \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik}; 175 \chomsky{tumgreen}{}{4}{Typ 3 - Regulär\\Links- / Rechtsreguläre Grammatik\\DFA, NFA, RE};
160 \end{tikzpicture} 176 \end{tikzpicture}
161 \end{center} 177 \end{center}
162 \end{frame} 178 \end{frame}
163 } 179 }
164 180
952 \end{center} 968 \end{center}
953 969
954 \vfill 970 \vfill
955 971
956 \begin{theorem}[] 972 \begin{theorem}[]
957 Sei $A$ formale Sprache, dann ist äuqivalent: 973 Sei $A$ formale Sprache, dann ist äquivalent:
958 \vspace{1em} 974 \vspace{1em}
959 \begin{itemize} 975 \begin{itemize}
960 \item $A$ ist \alert{Typ 0 Sprache} 976 \item $A$ ist \structure{Typ 0 Sprache}
961 \item $A$ \alert{rekursiv aufzählbar} 977 \item $A$ \structure{rekursiv aufzählbar}
962 \item $A$ \alert{semi-entscheidbar}, also $\chi'_A$ berechenbar 978 \item $A$ \structure{semi-entscheidbar}, also $\chi'_A$ berechenbar
963 \item $A=L(M)$ für eine \alert{TM $M$} 979 \item $A=L(M)$ für eine \structure{TM $M$}
964 \item $A$ ist \alert{Bild oder Urbild} einer berechenbaren Funktion 980 \item $A$ ist \structure{Bild oder Urbild} einer berechenbaren Funktion
965 \end{itemize} 981 \end{itemize}
966 \end{theorem} 982 \end{theorem}
967 \end{frame} 983 \end{frame}
968 } 984 }
969 985
971 \begin{frame} 987 \begin{frame}
972 \frametitle{Spracheigenschaften} 988 \frametitle{Spracheigenschaften}
973 \setbeamercovered{dynamic} 989 \setbeamercovered{dynamic}
974 990
975 \begin{itemize} 991 \begin{itemize}
976 \item \alert{Abschlusseigenschaften} 992 \item Abschlusseigenschaften
977 \end{itemize} 993 \end{itemize}
978 \begin{table} 994 \begin{table}
979 \begin{tabu}to \textwidth{X[c]|ccccc} 995 \begin{tabu}to \textwidth{X[c]|ccccc}
980 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{} 996 & Schnitt & Vereinigung & Komplement & Produkt & Stern \\ \tabucline{}
981 REG & ja & ja & ja & ja & ja\\ 997 REG & ja & ja & ja & ja & ja\\
982 CFL & nein & ja & nein & ja & ja\\ 998 CFL & nein & ja & nein & ja & ja\\
999 CSL & ja & ja & ja & ja & ja\\
983 TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja} 1000 TM & \structure{ja} & \structure{ja} & \structure{nein} & \structure{ja} & \structure{ja}
984 \end{tabu} 1001 \end{tabu}
985 \end{table} 1002 \end{table}
986 1003
987 \vfill 1004 \vfill
988 1005
989 \begin{itemize} 1006 \begin{itemize}
990 \item \alert{Entscheidbarkeit} 1007 \item Entscheidbarkeit
991 \end{itemize} 1008 \end{itemize}
992 \begin{table} 1009 \begin{table}
993 \begin{tabu}to \textwidth{X[c]|cccc} 1010 \begin{tabu}to \textwidth{X[c]|cccc}
994 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{} 1011 & Wortproblem & Leerheit & Äquivalenz & Schnittproblem\\ \tabucline{}
995 DFA & $\Oh(n)$ & ja & ja & ja\\ 1012 DFA & $\Oh(n)$ & ja & ja & ja\\
996 CFG & $\Oh(n^3)$ & ja & nein & nein\\ 1013 CFG & $\Oh(n^3)$ & ja & nein & nein\\
1014 CSL & $\Oh(2^n)$ & nein & nein & nein\\
997 TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein} 1015 TM & \structure{nein} & \structure{nein} & \structure{nein} & \structure{nein}
998 \end{tabu} 1016 \end{tabu}
999 \end{table} 1017 \end{table}
1000 \end{frame} 1018 \end{frame}
1001 } 1019 }
1008 \begin{center} 1026 \begin{center}
1009 \begin{tikzpicture}[auto] 1027 \begin{tikzpicture}[auto]
1010 \tikzstyle{rect} = [thick]; 1028 \tikzstyle{rect} = [thick];
1011 \tikzstyle{caption} = [align=left, anchor=north west]; 1029 \tikzstyle{caption} = [align=left, anchor=north west];
1012 1030
1013 \langclass{brown}{}{0}{Formale Sprache - $\Sigma^*$}; 1031 \definecolor{hannahyellow}{HTML}{FFB81C}
1032 \langclass{brown}{}{0}{Formale Sprache $\subseteq \Sigma^*$};
1014 \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar}; 1033 \langclass{tumblue}{}{1}{Typ 0 - Semi-Entscheidbar};
1015 \langclass{tumgreen}{}{2}{Entscheidbar}; 1034 \langclass{tumgreen}{}{2}{Entscheidbar};
1016 \langclass{violet}{}{3}{LOOP, PR}; 1035 \langclass{violet}{}{3}{LOOP, PR};
1017 \langclass{tumred}{}{4}{NP}; 1036 \langclass{tumred}{}{4}{NP};
1018 \langclass{tumorange}{dashed}{5}{P}; 1037 \langclass{hannahyellow}{dashed}{5}{P};
1019 \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei}; 1038 \langclass{tumgreen!40!black}{}{6}{Typ 2 - Kontextfrei};
1020 \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär}; 1039 \langclass{tumlightblue!80!black}{}{7}{Typ 3 - Regulär};
1021 \langclass{tumblue!20!black}{}{8}{Endlich}; 1040 \langclass{tumblue!20!black}{}{8}{Endlich};
1022 \end{tikzpicture} 1041 \end{tikzpicture}
1023 \end{center} 1042 \end{center}