ZUSAMMENFASSUNG-FSK-8VL-11-06-2024

Ausführliche Zusammenfassung der Einführung in Turing-Maschinen und kontextsensitive Sprachen

Einführung in Turing-Maschinen

Verwendung

• Turing-Maschinen werden eingeführt, um die Typ 1 und Typ 0 Sprachen der Chomsky-Hierarchie zu erkennen.

Funktionsweise

• Typ 1 Sprachen (Kontextsensitive Sprachen): Produktionsregeln dürfen die Länge der Wörter nicht verkürzen (|A| ≤ |α|).
• Typ 0 Sprachen (Rekursiv Aufzählbare Sprachen): Keine Einschränkungen für Produktionsregeln.

Turing-Maschinen

Allgemeine Turing-Maschinen

• Beschreiben Typ 0 Sprachen.
• Besitzen ein unendlich großes Band und können darauf lesen, schreiben und den Kopf bewegen.

Linear platzbeschränkte Turing-Maschinen (LBAs)

• Beschreiben Typ 1 Sprachen.
• Der Schreib-Lesekopf darf den Bereich der Eingabe nicht verlassen.

Unterschiede zwischen Kellerautomaten und Turing-Maschinen

Kellerautomaten

• Eingeschränkter Speicher: Stack, auf den nur von oben zugegriffen werden kann.
• Beispiel: Die Sprache $a^i{b}^i{c}^i$ kann nicht erkannt werden, da beim Lesen der dritten Gruppe (c’s) die Anzahl der Zeichen im Speicher nicht mehr vorhanden ist.

Turing-Maschinen

• Unendliches Band: Das Band kann nach links und rechts unendlich erweitert werden.
• Schreiblesekopf: Kann sowohl lesen als auch schreiben und sich in beide Richtungen bewegen.
• Vergleich: Eine Turing-Maschine kann komplexere Aufgaben lösen, die mit einem Kellerautomaten nicht möglich sind.

Formale Definition einer Turing-Maschine

Sieben-Tupel

Eine Turing-Maschine (TM) wird formal als ein Siebentupel $(Z,\Sigma ,\Gamma ,\delta ,Z_0,\text{Blank},E)$ definiert:

• $Z$: Eine endliche Menge von Zuständen.
• $\Sigma$: Ein endliches Eingabealphabet.
• $\Gamma$: Ein endliches Bandalphabet, das eine Obermenge von $\Sigma$ ist.
• $\delta$: Die Zustandsüberführungsfunktion.
• $Z_0$: Der Startzustand.
• Blank: Das Blanksymbol, das leere Felder auf dem Band markiert.
• $E$: Die Menge der Endzustände.

Zustandsüberführungsfunktion

Deterministische Turing-Maschine (DTM)

• Die Zustandsüberführungsfunktion $\delta$ ist definiert als: $$\delta :Z\times \Gamma \to Z\times \Gamma \times \{L,R,N\}$$
• Die Funktion nimmt einen Zustand und ein Symbol und liefert ein Tripel aus einem neuen Zustand, einem neuen Band-Symbol und einer Richtung (links, rechts oder neutral).

Nicht-deterministische Turing-Maschine (NTM)

• Die Zustandsüberführungsfunktion $\delta$ ist definiert als: $$\delta :Z\times \Gamma \to \mathcal{P}(Z\times \Gamma \times \{L,R,N\})$$
• Die Funktion liefert eine Menge möglicher Tripel, was bedeutet, dass die Maschine mehrere mögliche Übergänge hat.

Konfigurationen und Transitionsrelationen

Konfiguration

• Eine Konfiguration einer Turing-Maschine beschreibt den aktuellen Zustand, den Inhalt des Bandes und die Position des Schreib-Lesekopfes.
• Sie wird als ein Wort aus ${\Gamma }^{\ast }\times Z\times {\Gamma }^{\ast }$ geschrieben.

Transitionsrelation

• Bestimmt die Übergänge zwischen den Konfigurationen.

Beispiel für Übergänge:

1. Neutraler Übergang (N):

   • Vorher: Band enthält $B_1{B}_2\dots B_M{A}_1{A}_2\dots A_N$.
   • Nachher: Band enthält $B_1{B}_2\dots B_{M}C{A}_2\dots A_N$.
   • Zustandsänderung: Von Zustand $Z$ zu $Z^{\prime }$.
   • Schreiblesekopf bleibt auf dem Symbol $C$.

2. Übergang nach links (L):

   • Vorher: Band enthält $B_1{B}_2\dots B_M{A}_1{A}_2\dots A_N$.
   • Nachher: Band enthält $B_1{B}_2\dots Z^{\prime }{B}_{M}C{A}_2\dots A_N$.
   • Zustandsänderung: Von Zustand $Z$ zu $Z^{\prime }$.
   • Schreiblesekopf bewegt sich nach links auf das Symbol $B_M$.

3. Übergang nach rechts (R):

   • Vorher: Band enthält $B_1{B}_2\dots B_M{A}_1{A}_2\dots A_N$.
   • Nachher: Band enthält $B_1{B}_2\dots B_{M}C{Z}^{\prime }{A}_2\dots A_N$.
   • Zustandsänderung: Von Zustand $Z$ zu $Z^{\prime }$.
   • Schreiblesekopf bewegt sich nach rechts auf das Symbol $A_2$.

Akzeptierte Sprache einer Turing-Maschine

• Eine Turing-Maschine akzeptiert ein Wort $W\in {\Sigma }^{\ast }$, wenn es eine Konfiguration $UZV$ gibt, wobei $Z\in E$ ein Endzustand ist und $U$ und $V$ Worte über dem Bandalphabet sind, sodass die Startkonfiguration $Z_{0}W$ durch eine beliebige Anzahl von Schritten zu $UZV$ übergehen kann.

Triviale Beispiele

1. Akzeptiert alle Eingaben:

   • Definition: $M=(Z,\Sigma ,\Gamma ,\delta ,Z_0,\text{Blank},E)$, wobei $Z_0\in E$.
   • Erklärung: Die Turing-Maschine akzeptiert jede Eingabe sofort, ohne Berechnung durchzuführen.

2. Akzeptiert keine Eingaben:

   • Definition: $M=(Z,\Sigma ,\Gamma ,\delta ,Z_0,\text{Blank},\varnothing )$.
   • Erklärung: Die Turing-Maschine akzeptiert keine Eingabe, da es keine Endzustände gibt.

Linear beschränkte Turing-Maschinen (LBAs)

Definition

• LBAs sind eine Variante der Turing-Maschinen, bei denen der Schreib-Lesekopf den Bereich der Eingabe auf dem Band nicht verlassen darf.
• Die Turing-Maschine bleibt innerhalb des Bereichs, der durch die Eingabe definiert ist.

Eigenschaften

• Platzbeschränkung: Der Kopf darf den Bereich der Eingabe nicht verlassen.
• Markierung des Endes: Das Ende der Eingabe wird durch ein markiertes Symbol gekennzeichnet.
• Markierung des Anfangs: Der linke Rand ist am Anfang nicht markiert, kann aber von der Maschine markiert werden.
• Notationsweise: Wenn $\Sigma$ das Eingabealphabet ist, enthält die markierte Kopie $\hat{\Sigma }$ die gleichen Symbole, jedoch mit einem Hütchen.

Beispiel für eine LBA

• Ein LBA verarbeitet die Eingabe $A_1{A}_2\dots A_{m-1}{\hat{A}}_m$ und bleibt innerhalb dieser Grenzen. Der Zustand und die Übergänge sind so definiert, dass der Kopf niemals außerhalb des Bereichs wandert.

Akzeptierte Sprache

• Kontextsensitiv: LBAs erkennen genau die kontextsensitiven Sprachen (Typ-1-Sprachen).
• Erreichbare Zustände: Für jede Eingabe $A_1{A}_2\dots A_m$ ist die Anzahl der Symbole auf dem Band stets begrenzt durch die Länge der Eingabe.

Entscheidungsprobleme und Komplexität

Wortproblem

• Typ 1 bis Typ 3: Entscheidbar.
• Typ 0: Nicht entscheidbar.

Leerheitsproblem

• Typ 2 und Typ 3: Entscheidbar.
• Typ 1 und Typ 0: Nicht entscheidbar.

Äquivalenzproblem

• Typ 3 und deterministisch kontextfrei: Entscheidbar.
• Typ 0, Typ 1, Typ 2: Nicht entscheidbar.

Schnittproblem

• Nicht entscheidbar für deterministisch kontextfreie Sprachen.

Abschlusseigenschaften

Reguläre Sprachen

• Abgeschlossen unter Schnitt, Vereinigung, Komplement, Produkt und klinischem Abschluss.

Deterministisch kontextfreie Sprachen

• Nur gegenüber Komplement abgeschlossen.

Kontextfreie Sprachen

• Abgeschlossen gegenüber Vereinigung, Produkt und klinischem Abschluss.

Kontext-sensitive Sprachen

• Abgeschlossen gegenüber Schnitt, Vereinigung, Komplement, Produkt und klinischem Abschluss.

Typ-0-Sprachen

• Abgeschlossen bezüglich Schnitt, Vereinigung, Produkt und klinischem Abschluss, aber nicht gegenüber Komplement.

Chomsky-Hierarchie

Typ-0-Sprachen

• Beliebige Turing-Maschinen.

Typ-1-Sp

rachen

• Linear beschränkte Turing-Maschinen.

Typ-2-Sprachen

• Nicht-deterministische Kellerautomaten.

Typ-3-Sprachen

• Endliche Automaten (deterministisch und nicht-deterministisch).

Komplexität des Wortproblems

Typ-3 (DFA)

• Lineare Komplexität.

Typ-2 (Chomsky-Normalform)

• Kubische Komplexität.

Typ-1

• Exponentielle Komplexität.

Typ-0

• Nicht lösbar.

Wichtige Sprachen und Beispiele

• $A^n{B}^n$: Typ-2, aber nicht Typ-3.
• Palindrome: Typ-2, aber nicht deterministisch kontextfrei.
• $A^n{B}^n{C}^n$: Typ-1, aber nicht Typ-2.
• Halteproblem: Typ-0, aber nicht Typ-1.

Simulation von nicht-deterministischen Turing-Maschinen

Deterministische Simulation

• Nicht-deterministische Turing-Maschinen (NTMs) können durch deterministische Turing-Maschinen (DTMs) simuliert werden.
• Der deterministische Algorithmus probiert systematisch alle möglichen Berechnungswege der nicht-deterministischen Maschine aus.

Berechnungsbaum

• Der Ablauf der Simulation kann als Berechnungsbaum dargestellt werden, in dem jeder Knoten einen Zustand der Turing-Maschine repräsentiert.
• Der Baum wird durchlaufen, um alle möglichen Berechnungen der nicht-deterministischen Maschine zu prüfen.

Unterschiede in der Laufzeit

• Die Simulation eines nicht-deterministischen Algorithmus durch einen deterministischen kann zu einer exponentiellen Laufzeit führen.

Zusammenfassung und Ausblick

• Turing-Maschinen sind ein grundlegendes Modell zur Untersuchung der Berechenbarkeit und Komplexität.
• Sie modellieren die Fähigkeiten moderner Computer und ermöglichen die Untersuchung der Grenzen dessen, was algorithmisch lösbar ist.
• In zukünftigen Vorlesungen wird die Rolle der Turing-Maschine in der Chomsky-Hierarchie und der theoretischen Informatik weiter untersucht.

---