-
Notifications
You must be signed in to change notification settings - Fork 0
/
ueberblick.tex
70 lines (55 loc) · 3.2 KB
/
ueberblick.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
\chapter{Überblick}
Ein kurzer Gesamtüberblick über den Zusammenhang von formalen Sprachen zur Komplexität und Berechenbarkeitstheorie:
\definecolor{entscheidbar}{rgb}{0.4, 0.9, 0.7}
\begin{center}
\begin{tikzpicture}
\tikzset{
grouplabel/.style={
draw,
fill = white,
rectangle,
inner sep = 4pt,
rounded corners=1pt
}
}
\draw [rounded corners=5pt, dotted, line width=0.2mm] (0,0) rectangle (14,16.5);
\draw node at (7,16.5) [grouplabel] {alle formalen Sprachen};
% CO-SEMI-ENTSCHEIDBAR
\draw [rounded corners=5pt, dotted, line width=0.5mm] (0.5,0.5) rectangle (12,12);%co-semi
\draw node at (6,0.5) [grouplabel] {co-semi-entscheidbare Sprachen};
\draw node at (0.5,1.3) [label={right:$\chi'_{\overline L}(w)$ ist Turing-berechenbar, Komplement ist semi-entscheidbar}] {};
% SEMI-ENTSCHEIDBAR
\draw [rounded corners=5pt, dotted, line width=0.5mm] (2,2) rectangle (13.5,15.5);%semi
\draw node at (8,15.5) [grouplabel] {\hyperref[sec:typ0]{$\operatorname{Typ-0}=\re$, semi-entscheidbare Sprachen}};
\draw node at (2,14.8) [label={right:$\operatorname{PCP, K, H, H_0, \ldots}$}] {};
\draw node at (2,14.3) [label={right:$\chi'_{L}(w)$ ist Turing-berechenbar}] {};
\draw node at (2,13.7) [label={right:$L=T(M) \rightsquigarrow$ wird durch eine TM akzeptiert}] {};
\draw node at (2,13.2) [label={right:$f:\N\rightarrow \Sigma^\star, f(\N)=L \rightsquigarrow$ rekursiv aufzählbar}] {};
\draw node at (2,12.7) [label={right:$f:\Sigma^\star\rightarrow\Sigma^\star, f(\Sigma^\star)=L \rightsquigarrow$ Wertebereich einer berechenbaren Funktion}] {};
%ENTSCHEIDBAR
\draw [draw, fill=accent!50, line width=0.5mm] (2,2) rectangle (12,12);%entscheidbar
\draw node at (7,12) [grouplabel] {\hyperref[sec:rec]{entscheidbare Sprachen}};
\draw node at (2,10.5) [label={right:$\chi_{L}(w)$ ist Turing-berechenbar}] {};
%% TYP1
\draw [rounded corners=2pt, line width=0.2mm] (2.2,2.2) rectangle (11.8,9.9);
\draw node at (7,9.9) [grouplabel] {\hyperref[sec:typ1]{$\operatorname{Typ-1}=\csl$}};
\draw node at (2.2,9.2) [label={right:$a^nb^nc^n, a^{2^n}, \ldots$}] {};
\draw node at (2.2,8.7) [label={right:LBA}] {};
%% TYP2
\draw [rounded corners=2pt, line width=0.2mm] (2.4,2.4) rectangle (11.6,8.1);
\draw node at (7,8.1) [grouplabel] {\hyperref[sec:typ2]{$\operatorname{Typ-2}=\cfl$}};
\draw node at (2.4,7.4) [label={right:$a^na^n, ww^R, \ldots$}] {};
\draw node at (2.4,6.9) [label={right:PDA}] {};
% DCFL
\draw [rounded corners=2pt, line width=0.2mm] (2.6,2.6) rectangle (11.4,6.3);%dcfl
\draw node at (7,6.3) [grouplabel] {\hyperref[sec:typ2]{$\dcfl$}};
\draw node at (2.6,5.6) [label={right:$a^nb^n, w\$w^R, \ldots$}] {};
\draw node at (2.6,5.1) [label={right:DPDA}] {};
% TYP3
\draw [rounded corners=2pt, line width=0.2mm] (2.8,2.8) rectangle (11.2,4.5);
\draw node at (7,4.5) [grouplabel] {\hyperref[sec:typ3]{$\operatorname{Typ-0}=\reg$}};
\draw node at (2.8,3.8) [label={right:$\Sigma^\star, \emptyset, a^\star,\ldots$}] {};
\draw node at (2.8,3.3) [label={right:DEA, NEA, reguläre Ausdrücke}] {};
\draw node at (14.1,0.2) [label={left:{\color{black!50!white}Simon König 2018}}] {};
\end{tikzpicture}
\end{center}