Grundlagen Der Theoretischen Informatik an der Universität Koblenz-Landau | Karteikarten & Zusammenfassungen

Lernmaterialien für Grundlagen der Theoretischen Informatik an der Universität Koblenz-Landau

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Grundlagen der Theoretischen Informatik Kurs an der Universität Koblenz-Landau zu.

TESTE DEIN WISSEN

Wie sind Gödelnummern von DTMs definiert?

Lösung anzeigen
TESTE DEIN WISSEN

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.
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Kettenproduktion?

Lösung anzeigen
TESTE DEIN WISSEN

Eine Regel der Form

A → B mit A, B ∈ V

Lösung ausblenden
TESTE DEIN WISSEN

Was ist Reduktion von Problemen?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein determinierter endlicher Automat?

Lösung anzeigen
TESTE DEIN WISSEN

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.
Lösung ausblenden
TESTE DEIN WISSEN

Wie ist die Chomsky-Hierarchie?

Lösung anzeigen
TESTE DEIN WISSEN

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⊆ Σ^∗}

Lösung ausblenden
TESTE DEIN WISSEN

Welchen Regeln folgt eine rechtslineare Grammatik?

Lösung anzeigen
TESTE DEIN WISSEN

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
Lösung ausblenden
TESTE DEIN WISSEN

Was sind reguläre Ausdrücke?

Lösung anzeigen
TESTE DEIN WISSEN

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 +
Lösung ausblenden
TESTE DEIN WISSEN

Welchen Regeln folgt eine beschränkte Grammatik?

Lösung anzeigen
TESTE DEIN WISSEN

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
Lösung ausblenden
TESTE DEIN WISSEN

Was ist eine Dycksprache?

Lösung anzeigen
TESTE DEIN WISSEN

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.

Lösung ausblenden
TESTE DEIN WISSEN

Welchen Regeln folgt eine kontextsensitive Grammatik?

Lösung anzeigen
TESTE DEIN WISSEN

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
Lösung ausblenden
TESTE DEIN WISSEN

Was ist ein indeterminierter endlicher Automat?

Lösung anzeigen
TESTE DEIN WISSEN

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.
Lösung ausblenden
TESTE DEIN WISSEN

Welchen Regeln folgt eine kontextfreie Grammatik?

Lösung anzeigen
TESTE DEIN WISSEN

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
Lösung ausblenden
  • 99723 Karteikarten
  • 1523 Studierende
  • 99 Lernmaterialien

Beispielhafte Karteikarten für deinen Grundlagen der Theoretischen Informatik Kurs an der Universität Koblenz-Landau - von Kommilitonen auf StudySmarter erstellt!

Q:

Wie sind Gödelnummern von DTMs definiert?

A:

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.
Q:

Was ist eine Kettenproduktion?

A:

Eine Regel der Form

A → B mit A, B ∈ V

Q:

Was ist Reduktion von Problemen?

A:

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.

Q:

Was ist ein determinierter endlicher Automat?

A:

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.
Q:

Wie ist die Chomsky-Hierarchie?

A:

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⊆ Σ^∗}

Mehr Karteikarten anzeigen
Q:

Welchen Regeln folgt eine rechtslineare Grammatik?

A:

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
Q:

Was sind reguläre Ausdrücke?

A:

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 +
Q:

Welchen Regeln folgt eine beschränkte Grammatik?

A:

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
Q:

Was ist eine Dycksprache?

A:

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.

Q:

Welchen Regeln folgt eine kontextsensitive Grammatik?

A:

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
Q:

Was ist ein indeterminierter endlicher Automat?

A:

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.
Q:

Welchen Regeln folgt eine kontextfreie Grammatik?

A:

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
Grundlagen der Theoretischen Informatik

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Grundlagen der Theoretischen Informatik an der Universität Koblenz-Landau

Für deinen Studiengang Grundlagen der Theoretischen Informatik an der Universität Koblenz-Landau gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Grundlagen der Theoretischen Informatik Kurse im gesamten StudySmarter Universum

Grundlagen der Technischen Informatik

Universität Oldenburg

Zum Kurs
Grundlagen der Informatik

Hochschule Ansbach

Zum Kurs
Mathematische Grundlagen der Informatik

Hochschule Fulda

Zum Kurs
theoretische Grundlagen der Informatik

Hochschule für Wirtschaft und Recht Berlin

Zum Kurs
Grundlagen der technischen Informatik

Universität Jena

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Grundlagen der Theoretischen Informatik
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Grundlagen der Theoretischen Informatik