Grundlagen der Theoretischen Informatik at Universität Koblenz-Landau

DTMs werden als Gödelzahlen kodiert:

• DTMs können als Gödelwörter dargestellt werden.
  M 7→ a_i_1 . . . a_i_n
• Die Buchstaben der Gödelwörter können in Ziffern kodiert werden,
  um Gödelnummern zu bekommen.
  a_i_1 ... a_i_n → p^i_1_1 ... p^i_n_n ∈ N p_i: i-te Primzahl
• Notation: ˆg(M) für die Gödelnummer der DTM M.

Eine Regel der Form

A → B mit A, B ∈ V

Wir geben eine totale, berechenbare Funktion f an, die

• eine Instanz p1 von P1
• in eine Instanz p2 von P2 umwandelt,
• und zwar so, dass die Antwort zu p1 "ja“ ist gdw die Antwort zu p2 ”ja” ist.

Wenn P1 unentscheidbar ist, dann ist auch P2 unentscheidbar.

Ein endlicher Automat ist ein Tupel
A = (K, Σ, δ, s_0, F)

• K endliche Menge von Zuständen,
• Σ endliches Alphabet,
• δ : K ×Σ → K Übergangsfunktion,
• s_0 ∈ K Startzustand
• F ⊆ K Menge der finalen Zustände.

Klasse L_3, REG (regulär) = {L(G)|G ist rechtslinear}

Klasse L_2, CFL (kontextfrei) = {L(G)| G ist kontextfrei}

Klasse L_1, CSL (kontextsensitiv) = {L(G)|G ist kontextsensitiv}

Klasse L_1, CSL (beschränkt) = {L(G)|G ist beschränkt}

Klasse L_0, r.e. (aufzählbar) = {L(G)|G beliebig}

Klasse L (beliebige Sprache) = {L|L⊆ Σ^∗}

G = (V, T, R, S) rechtslinear <-> "füralle"(P → Q) ∈ R (P ∈ V und Q ∈ T∗ ∪ T^+ V) ==>

• Links eine einzelne Variable
• Rechts höchstens eine Variable
• Wenn rechts eine Variable steht, steht sie ganz rechts im Wort und das Wort enthält mindestens ein Terminalsymbol

Menge RegΣ der regulären Ausdrücke (über Σ) ist definiert durch:

1. 0 ist ein regulärer Ausdruck
2. Für jedes a ∈ Σ ist a ein regulärer Ausdruck
3. Sind r und s reguläre Ausdrücke, so auch
   • (r + s) (Vereinigung),
   • (rs) (Konkatenation),
   • (r∗) (Kleene Stern)

Klammern können weggelassen werden, dann

• ∗ hat Vorrang vor Konkatenation
• Konkatenation hat Vorrang vor +

G = (V, T, R, S) beschränkt <-> "füralle" (P → Q) ∈ R:

1. |P| ≤ |Q|, oder S → ε
2. S nicht in Q ==>

• Die Conclusio ist mindestens so lang wie die Prämisse, außer bei ε ∈ L.
• Das Wort wird nicht kürzer, außer bei ε ∈ L

Die Dycksprache Dk ist die kleinste Menge, die folgende Bedingungen erfüllt:
1. epsilon ∈ Dk,
2. Falls w ∈ Dk, so auch xiw(xi)^_ .
3. Falls u, v ∈ Dk, so auch uv.

G = (V, T, R, S) kontextsensitiv <-> "für alle"(P → Q) ∈ R:

1. "es gibt" u, v, α ∈ (V∪T)^∗ "es gibt"A ∈ V (P = uAv und Q = uαv mit |α| ≥ 1)  oder S → ε
2. S nicht in Q ==>

• Eine Variable A wird in einen String α mit |α| ≥ 1 überführt
• Die Ersetzung von A durch α findet nur statt, wenn der in der Regel geforderte Kontext (u und v) vorhanden ist
• Das Wort wird nicht kürzer, außer bei ε ∈ L

Ein indeterminierter endlicher Automat (NDEA) ist ein Tupel A = (K, Σ,∆, I, F)

• K endliche Menge von Zuständen,
• Σ endliches Alphabet,
• ∆ ⊆ (K × Σ) ×K Übergangsrelation,
• I ⊆ K  Menge von Startzuständen,
• F ⊆ K Menge von finalen Zuständen.

G = (V, T, R, S) kontextfrei <-> "für alle"(P → Q) ∈ R (P ∈ V und Q ∈ (V ∪ T)^∗)==>

• Links eine einzelne Variable
• Die Prämisse macht keine Aussage, was der Kontext dieser Variablen ist(”kontextfrei“)
• Rechts steht etwas beliebiges