====== Formale Sprachen und Komplexität ======
  * [[sprachen]]
  * [[berechenbarkeit]]
  * [[komplexität]]

===== Relationen =====
  * **Transitive Hülle** \\ $R^+$
  * **Reflexiv-transitive Hülle** \\ $R^*$
  * **Aquivalenz//relation//**
    * reflexiv
    * symmetrisch
    * transitiv
  * **Äquivalenz//klasse//** von Element x \\ //Menge// aller Elemente die in Äquivalenz//relation// zu x stehen.
  * **Index** \\ //Anzahl// der Äquivalenz//klassen//. D.h. wo es //mindesten einen// Repräsentanten gibt.
  * $R'$ ist **Verfeinerung** von $R$ \\ $R' \subseteq R$

===== Mengen =====
==== Entscheidbarkeit ====
$\chi_A$ = Charakteristische Funktion der Menge $A \subseteq \Sigma^*$.

Wenn (semi-)entscheidbar => $\chi_A$ berechenbar

entscheidbar
\[
\chi_A = \begin{cases}
1 & \text{ wenn } w \in A \\
0 & \text{ wenn } w \not\in A
\end{cases}
\]

semi-entscheidbar
\[
\chi_A = \begin{cases}
1 & \text{ wenn } w \in A \\
\text{undefiniert} & \text{ wenn } w \not\in A
\end{cases}
\]

Der Algorithmus von $\chi_A$

^ Fall ^ Bedingung ^ Name ^
|    Ja | Terminiert | entscheidbar |
|  Nein | Terminiert | ::: |
|    Ja | Terminiert | semi-entscheidbar |
|  Nein | Terminiert nicht immer | ::: |
|    Ja | Terminiert nicht immer | nicht semi-entscheidbar |
|  Nein | Terminiert nicht immer | ::: |
==== Auf- und Abzählbar ====
Die Menge lässt sich mit natürlichen Zahlen aneinander reihen

$f$ ist total

$M = \{f(1), f(2), f(3), ...\}$ bzw. $M = \{x_i | P(x_i)\}$ (Nicht zwangsweise das gegenteil!)

P semi-entscheidbar => $M_P$ (rekursiv) aufzählbar
=== (Rekursiv) Aufzählbar ===
  * $f$ muss berechnbar sein
  * P muss entscheibar sein

"Ich kann die Elemente selbst aufzählen (errechnen)"

=== Abzählbar ===
  * $f$ muss nicht berechnbar sein
  * P muss nicht entscheibar sein

"Ich kann die Elemente zwar nicht //selbst// aufzählen, wenn ich sie bekommen, kann ich sie aber abzählen"