Berechenbarkeit und Formale Sprachen - Cheatsheet

Berechenbarkeitsbegriff und Turingmaschinen: Funktionsweise und Aufbau von Turingmaschinen

Definition:

Grundprinzip der Berechenbarkeit und die Rolle der Turingmaschine.

Details:

• Turingmaschine: 7-Tupel \(Q, \Sigma, \Gamma, \delta, q_0, \square, F\) definiert.
• Zustände \(Q\), Eingabealphabet \(\Sigma\), Bandalphabet \(\Gamma\).
• Übergangsfunktion \(\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R, N\}\).
• Startzustand \(q_0\), Leerzeichen \(\square\), Endzustände \(F\).
• Band fungiert als unendlich langer Speicher, Kopf liest/schreibt abhängig von \(\delta\).

Turingmaschinen: Unlösbare Probleme und das Halteproblem

Definition:

Einführung in unentscheidbare Probleme anhand der Turingmaschine, insbesondere das Halteproblem.

Details:

• Eine Turingmaschine ist ein mathematisches Modell für die Berechnung.
• Unlösbare Probleme: Probleme, für die keine Turingmaschine existiert, die sie für alle Eingaben lösen kann.
• Das Halteproblem: Entscheidung, ob eine gegebene Turingmaschine bei einer bestimmten Eingabe hält oder nicht.
• Von Alan Turing bewiesen, dass das Halteproblem unentscheidbar ist.
• Formal: Es gibt keine Turingmaschine H, die für jede Turingmaschine T und Eingabe w entscheidet, ob T auf w hält.
• Reduktionsbeweis: Annahme einer Entscheidungsmaschine für das Halteproblem führt zu einem Widerspruch.

Komplexitätsklassen: NP-Vollständigkeit und Beispiele von NP-vollständigen Problemen

Definition:

NP-Vollständigkeit: Eine Problemklasse in NP, deren Lösung jedes Problem in NP polynomial reduzieren kann.

Details:

• NP (nichtdeterministisch polynomial): Klasse von Problemen, die in polynomieller Zeit von einem nichtdeterministischen Turing-Maschine gelöst werden können.
• Reduktion: Jedes Problem in NP kann in polynomieller Zeit auf ein NP-vollständiges Problem reduziert werden.
• Beispiele von NP-vollständigen Problemen:

• K-SAT (K-Satisfiability)
• Hamiltonkreisproblem
• Handlungsreisendenproblem (Traveling Salesman Problem, TSP)
• Knotenüberdeckungsproblem (Vertex Cover)
• Unabhängiges Mengenproblem (Independent Set)

Reduktionen zwischen Problemen und ihre Rolle in der Komplexitätstheorie

Definition:

Reduktionen zwischen Problemen helfen, die Komplexität von Problemen zu vergleichen, indem man zeigt, dass die Lösung eines Problems auf die Lösung eines anderen zurückgeführt werden kann.

Details:

• Formelle Definition: Eine Reduktion von Problem A auf Problem B bedeutet, dass man eine Transformation \textit{f} findet, so dass für jede Instanz \textit{x} von A die Lösung von \textit{x} berechnet werden kann durch die Lösung von \textit{f(x)} in B.
• Zeichenweise: A \textleadsfrom B bedeutet, dass A auf B reduziert werden kann.
• Wichtige Reduktionen: Polynomielle Reduktion (Karp-Reduktion), log-space Reduktion.
• Rolle in der Komplexitätstheorie: Hilft bei der Klassifizierung von Problemen, z.B. NP-Vollständigkeit beweisen.
• Typische Vorgehensweise: Zeigen, dass ein bekannt schweres Problem auf das zu untersuchende Problem reduziert werden kann.

Chomsky-Hierarchie: Typ-2 (kontextfreie) und Typ-3 (reguläre) Grammatiken

Definition:

Typ-2: Grammatiken mit kontextfreien Produktionen (N -> (N U T)*); Typ-3: reguläre Grammatiken mit restriktiven Produktionen (N -> T N / N -> T)

Details:

• Typ-2 (Kontextfreie Grammatiken): Regel-Form: A → α, wobei A ein einzelnes Nichtterminal und α eine beliebige Folge von Terminal- und Nichtterminalsymbolen ist.
• Akzeptiert durch: Kellerautomaten
• Beispiele: Klammerausdrücke, arithmetische Ausdrücke
• Typ-3 (Reguläre Grammatiken): Regel-Form: A → aB oder A → a, wobei A und B Nichtterminalsymbole und a ein Terminalsymbol sind.
• Akzeptiert durch: endliche Automaten
• Beispiele: einfache Mustererkennung, reguläre Ausdrücke

Endliche Automaten: Definition und Beispiele endlicher Automaten

Definition:

Endlicher Automat ist ein theoretisches Modell in der Informatik zur Darstellung von Berechnungen mit endlichen Zuständen.

Details:

• Ein endlicher Automat wird definiert als \(M = (Q, \Sigma, \delta, q_0, F)\)
• \(Q\) ist eine endliche Menge von Zuständen
• \(\Sigma\) ist das Eingabealphabet
• \(\delta: Q \times \Sigma \rightarrow Q\) ist die Übergangsfunktion
• \(q_0\) ist der Startzustand
• \(F\) ist die Menge der akzeptierenden Zustände
• Endliche Automaten können deterministisch (DFA) oder nichtdeterministisch (NFA) sein
• Beispiel eines Deterministischen Endlichen Automaten (DFA):
  • \t\( Q = \{q_0, q_1\}\)
  • \t\( \Sigma = \{a, b\}\)
  • \( \delta(q_0, a) = q_1 \)
  • \t\( \delta(q_0, b) = q_0 \)
  • \t\( \delta(q_1, a) = q_0 \)
  • \t\( \delta(q_1, b) = q_1 \)
  • \t\( q_0 \) ist der Startzustand
  • \t\( F = \{q_1\}\)

Reguläre Ausdrücke: Umwandlung zwischen regulären Ausdrücken und endlichen Automaten

Definition:

Prozess der Transformation von regulären Ausdrücken in äquivalente endliche Automaten (DFA/NFA) und umgekehrt.

Details:

• Reguläre Ausdrücke: Beschreiben Sprachen durch Muster.
• Endliche Automaten (DFA/NFA): Akzeptieren Sprachen durch Zustandsübergänge.
• Transformation Regex → NFA: Thompson's Konstruktion.
• Transformation NFA → DFA: Subset-Konstruktion (Powerset-Konstruktion).
• Transformation DFA → Regex: Rückwärtsinduktion oder State Elimination Methode.

Pumping Lemma: Beweise der Nicht-Regularität mit dem Pumping Lemma

Definition:

Die Menge aller regulären Sprachen erfüllt das Pumping Lemma. Es kann genutzt werden, um zu zeigen, dass eine Sprache nicht regulär ist, indem es bewiesen wird, dass das Lemma für sie nicht gilt.

Details:

• Zerlege ein Wort der Sprache in drei Teile: \(w = xyz\), wobei \(|xy| \leq n\) und \(|y| > 0\).
• Für alle \(i \geq 0\) muss \(xy^iz\) auch in der Sprache liegen.
• Falls eine Sprache das Pumping Lemma nicht erfüllt, ist sie nicht regulär.
• Anwendung: Wähle ein Wort, finde geeignete Zerlegung, zeige für ein \(i\), dass \(xy^iz\) nicht in der Sprache liegt.