Formale Sprachen und Komplexität

Relationen

  • Transitive Hülle
    $R^+$
  • Reflexiv-transitive Hülle
    $R^*$
  • Aquivalenzrelation
    • reflexiv
    • symmetrisch
    • transitiv
  • Äquivalenzklasse von Element x
    Menge aller Elemente die in Äquivalenzrelation zu x stehen.
  • Index
    Anzahl der Äquivalenzklassen. 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), \ldots\}$ 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“

users/skruppy/ext/uni/4/fsk/start.txt · Zuletzt geändert: 2013/07/26 22:14 von skruppy