FSK-8VL-11-06-2024

Diese Zusammenfassung basiert auf den VL Videos vom 14.06, diese ist jedoch nicht ganz übereinstimmend mit der VL 8

Zusammenfassung Vorabzusammenfassung

Einführung in Turing-Maschinen (Seite 1)

• Verwendung: Einführung und Erklärung der Turing-Maschinen, die die Typ 1 und Typ 0 Sprachen der Chomsky-Hierarchie erkennen.
• Funktionsweise:
  • Typ 1 Sprachen: Produktionsregeln dürfen die Worte nicht schrumpfen lassen.
  • Typ 0 Sprachen: Keine Einschränkungen für Produktionsregeln.
  • Turing-Maschinen: Allgemeine Turing-Maschinen für Typ 0 und linear platzbeschränkte Turing-Maschinen für Typ 1.
  • Vergleich zu Kellerautomaten: Turing-Maschinen haben ein unendlich großes Band und können darauf lesen und schreiben sowie den Kopf bewegen, während Kellerautomaten nur von oben in den Stack zugreifen können.

VL0-8a Einführung in Turing-Maschinen

Willkommen zur Vorlesung “Formale Sprachen und Komplexität” und “Theoretische Informatik für Medieninformatiker”. Nachdem wir die Typ 3 Sprachen, also die regulären Sprachen, und das entsprechende Maschinenmodell, die endlichen Automaten, behandelt haben, sowie die Typ 2 Sprachen, also die kontextfreien Sprachen, und das dazugehörige Automatenmodell, die Kellerautomaten, kommen wir nun zu den Typ 1 und Typ 0 Sprachen der Chomsky-Hierarchie.

Chomsky-Hierarchie und Turing-Maschinen

Typ 1 Sprachen (Kontextsensitive Sprachen)

• Regel: Produktionen dürfen die Worte nicht schrumpfen. Das bedeutet, dass die linke Seite einer Produktionsregel höchstens genauso lang sein muss wie die rechte Seite. Es ist also verboten, dass die rechte Seite der Produktion kürzer ist als die linke Seite.
• Monotone Grammatiken: In manchen Büchern werden die kontextsensitiven Grammatiken auch als monotone Grammatiken bezeichnet, weil sie diese Monotonie-Bedingung haben.

Typ 0 Sprachen (Rekursiv Aufzählbare Sprachen)

• Regel: Es gibt keine Einschränkungen für Produktionsregeln. Alle Produktionen sind erlaubt.

Turing-Maschinen

• Allgemeine Turing-Maschinen: Diese beschreiben die Typ 0 Sprachen.
• Linear platzbeschränkte Turing-Maschinen: Diese beschreiben die Typ 1 Sprachen.

Unterschiede zwischen Kellerautomaten und Turing-Maschinen

Kellerautomaten

• Eingeschränkter Speicher: Kellerautomaten haben einen Kellerspeicher, auf den man nur von oben zugreifen kann, um Daten hinzuzufügen oder zu entfernen.
• Beispiel: Eine Sprache wie $a^i{b}^i{c}^i$ kann nicht mit einem Kellerautomaten erkannt werden, weil man die Anzahl der Zeichen beim Lesen der dritten Gruppe (c’s) nicht mehr im Speicher hat. Beim Lesen der a’s kann man die Anzahl i im Keller speichern. Beim Lesen der b’s vergleicht man und entleert den Keller sukzessive. Beim Lesen der c’s hat man die Anzahl i im Speicher verloren, da der Keller beim Vergleich mit den b’s geleert wurde.

Turing-Maschinen

• Unendliches Band: Im Gegensatz zu den Kellerautomaten haben Turing-Maschinen ein Band, das nach links und rechts unendlich erweiterbar ist. Das Band dient als Speicher, auf den beliebig zugegriffen werden kann.
• Schreiblesekopf: Turing-Maschinen haben einen Schreiblesekopf, der sowohl lesen als auch schreiben kann und sich nach links oder rechts bewegen kann.
• Vergleich: Eine Turing-Maschine kann als eine Art Nähmaschine betrachtet werden, bei der das Band der Stoff ist, der beliebig groß ist. Der Schreiblesekopf kann vor- und zurückbewegt werden, um auf dem Band zu schreiben oder zu lesen. Damit kann die Turing-Maschine Aufgaben lösen, die mit einem Kellerautomaten nicht möglich sind.

Formale Definition einer Turing-Maschine

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

• $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.
• $\text{Blank}$: Das Blank-Symbol, das einen leeren Inhalt auf dem Band anzeigt.
• $E$: Die Menge der Endzustände.

Zustandsüberführungsfunktion

Deterministische Turing-Maschine (DTM)

Die Zustandsüberführungsfunktion $\delta$ einer deterministischen Turing-Maschine ist definiert als:

$$\delta :Z\times \Gamma \to Z\times \Gamma \times \{L,R,N\}$$

Das bedeutet, die Funktion nimmt einen Zustand und ein Symbol vom Bandalphabet und liefert ein Tripel aus einem neuen Zustand, einem neuen Band-Symbol und einer Richtung (links, rechts oder neutral).

Beispiel: $\delta (Z,A)=(Z^{\prime },B,X)$ bedeutet:

• Falls die Turing-Maschine im Zustand $Z$ ist und das Zeichen $A$ an der aktuellen Position des Schreiblesekopfes auf dem Band steht, dann:
  • Wechselt die Turing-Maschine in den Zustand $Z^{\prime }$.
  • Ersetzt das Zeichen $A$ auf dem Band durch $B$.
  • Bewegt den Schreiblesekopf in die Richtung $X$ (L = links, R = rechts, N = neutral, d.h. bleibt stehen).

Nicht-deterministische Turing-Maschine (NTM)

Die Zustandsüberführungsfunktion $\delta$ einer nicht-deterministischen Turing-Maschine ist definiert als:

$$\delta :Z\times \Gamma \to \mathcal{P}(Z\times \Gamma \times \{L,R,N\})$$

Das bedeutet, die Funktion liefert eine Menge von möglichen Tripeln. Die Maschine hat mehrere mögliche Nachfolgekonfigurationen.

Konfigurationen

Um den Ablauf einer Turing-Maschine zu beschreiben, verwenden wir Konfigurationen. Eine Konfiguration ist ein Wort aus ${\Gamma }^{\ast }\times Z\times {\Gamma }^{\ast }$. Das bedeutet, eine Konfiguration gibt den aktuellen Zustand der Turing-Maschine und den Inhalt des Bandes sowie die Position des Schreiblesekopfes an. Sie wird verwendet, um den aktuellen Stand der Berechnung zu beschreiben.

Beispiel einer Konfiguration

Eine Konfiguration der Form $WZ{W}^{\prime }$ bedeutet, dass die Turing-Maschine im Zustand $Z$ ist, auf dem Band steht das Wort $W{W}^{\prime }$, und links und rechts davon sind nur Blank-Symbole. Der Schreiblesekopf steht auf dem ersten Symbol von $W^{\prime }$. Das $Z$ wird zwischen $W$ und $W^{\prime }$ geschrieben, weil der Kopf auf dem ersten Symbol von $W^{\prime }$ steht.

Startkonfiguration

Die Startkonfiguration einer Turing-Maschine für ein Eingabewort $W$ ist der Startzustand $Z_0$ und das Wort $W$. Wenn das Eingabewort das leere Wort ist, verwenden wir ein Blank-Symbol. Die Startkonfiguration für das leere Wort ist also $Z_0\text{Blank}$.

Transitionsrelation

Die Transitionsrelation definiert die Übergänge zwischen den Konfigurationen der Turing-Maschine. Diese Übergänge hängen von der Zustandsüberführungsfunktion $\delta$ ab.

Beispiele für die Transitionsrelation

1. Neutraler Übergang (N):

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

2. Übergang nach links (L):

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

3. Übergang nach rechts (R):

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

4. Spezialfall (R) am Ende des Wortes:

   • Vorher: Das Band enthält

$B_1{B}_2\dots B_M{A}_1\text{Blank}$.

• Nachher: Das Band enthält $B_1{B}_2\dots B_{M}C\text{Blank}$. Der Schreiblesekopf bewegt sich nach rechts auf das Blank-Symbol.
• Zustandsänderung: Von Zustand $Z$ zu $Z^{\prime }$.

5. Spezialfall (L) am Anfang des Wortes:
   • Vorher: Das Band enthält $\text{Blank}{B}_1{B}_2\dots B_M{A}_1$.
   • Nachher: Das Band enthält $\text{Blank}C{B}_1{B}_2\dots B_M{A}_1$. Der Schreiblesekopf bewegt sich nach links auf das Blank-Symbol.
   • Zustandsänderung: Von Zustand $Z$ zu $Z^{\prime }$.

Akzeptierte Sprache einer Turing-Maschine

Die akzeptierte Sprache einer Turing-Maschine $M=(Z,\Sigma ,\Gamma ,\delta ,Z_0,\text{Blank},E)$ ist die Menge aller Worte $W\in {\Sigma }^{\ast }$, für die es eine Konfiguration $UZV$ gibt, wobei $U$ und $V$ Worte über dem Bandalphabet sind und $Z$ ein Endzustand ist. Die Startkonfiguration ist $Z_{0}W$. Das bedeutet, dass die Turing-Maschine $M$ das Wort $W$ akzeptiert, wenn sie von der Startkonfiguration $Z_{0}W$ in eine Konfiguration $UZV$ übergehen kann, wobei $Z$ ein Endzustand ist.

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.

Zustandsgraph

Der Zustandsgraph einer Turing-Maschine zeigt die Zustände und Übergänge zwischen ihnen. Jede Kante im Graph ist beschriftet mit $A:B,X$, wobei:

• $A$ das gelesene Bandsymbol ist.
• $B$ das ersetzte Bandsymbol ist.
• $X$ die Bewegungsrichtung des Schreiblesekopfes ist (L = links, R = rechts, N = neutral).

Beispielzustandsgraph

Ein Beispiel aus dem Schöning-Buch zeigt eine Turing-Maschine mit vier Zuständen:

• Zustände: $Z_0,Z_1,Z_2,Z_3$.
• Eingabealphabet: $\{0,1\}$.
• Bandalphabet: $\{0,1,\text{Blank}\}$.
• Startzustand: $Z_0$.
• Blank-Symbol: $\text{Blank}$.
• Endzustand: $Z_3$.

Übergänge:

• $\delta (Z_0,\text{Blank})=(Z_1,\text{Blank},L)$
• $\delta (Z_0,0)=(Z_0,0,R)$
• $\delta (Z_0,1)=(Z_0,1,R)$

Übergänge in Turing-Maschinen

Diese Übergänge zeigen, dass die Turing-Maschine im Zustand $Z_0$ nach rechts rattert, bis sie ein Blank-Symbol erreicht. Dann wechselt sie in den Zustand $Z_1$ und bewegt den Kopf nach links. Im Zustand $Z_1$ ersetzt sie eine 1 durch eine 0 und verbleibt in $Z_1$ oder ersetzt eine 0 durch eine 1 und wechselt in den Zustand $Z_2$.

• Rattern nach rechts: Der Kopf bewegt sich nach rechts, bis ein Blank-Symbol erreicht wird.
• Zustandswechsel zu $Z_1$: Bei Erreichen des Blank-Symbols wechselt der Zustand zu $Z_1$ und der Kopf bewegt sich nach links.
• Ersetzen von Symbolen in $Z_1$:
  • Ersetzt eine 1 durch eine 0 und bleibt in $Z_1$.
  • Ersetzt eine 0 durch eine 1 und wechselt zu $Z_2$.

Beispielablauf

Wir betrachten eine Turing-Maschine mit der Anfangskonfiguration $Z_{0}0111$. Das Band enthält die Zeichenkette 00111, gefolgt von unendlich vielen Blank-Symbolen. Der Kopf steht auf der ersten Null und die Maschine ist im Zustand $Z_0$.

1. Erster Schritt:

   • Zustand: $Z_0$
   • Gelesenes Symbol: 0
   • Aktion: 0 schreiben, Kopf nach rechts bewegen
   • Neue Konfiguration: $Z_{0}0111$
   • Der Kopf steht nun auf der ersten 1.

2. Weitere Schritte in $Z_0$:

   • Der Kopf bewegt sich weiter nach rechts und ersetzt die gelesenen 1 durch 1, bis er auf das Blank-Symbol trifft.
   • Neue Konfiguration nach mehreren Schritten: $Z_{0}0011\_$
   • Zustandwechsel zu $Z_1$:
     • Blank-Symbol bleibt unverändert.
     • Kopf bewegt sich nach links.
     • Neue Konfiguration: $Z_{1}0011\_$
     • Der Kopf steht nun auf der letzten 1.

3. Schritte in $Z_1$:

   • Zustand: $Z_1$
   • Gelesenes Symbol: 1
   • Aktion: 1 durch 0 ersetzen, Kopf nach links bewegen
   • Neue Konfiguration: $Z_{1}0010\_$
   • Der Kopf steht auf der zweiten 1.

4. Übergang zu $Z_2$:

   • Gelesenes Symbol: 0
   • Aktion: 0 durch 1 ersetzen, Zustandwechsel zu $Z_2$
   • Neue Konfiguration: $Z_{2}0100\_$
   • Der Kopf steht auf der ersten 0.

5. Verbleib in $Z_2$ und Abschluss:

   • Zustand: $Z_2$
   • Gelesenes Symbol: 0
   • Aktion: 0 bleibt unverändert, Kopf nach links bewegen
   • Neue Konfiguration: $Z_{2}0100\_$
   • Der Kopf steht auf der ersten 1.

6. Abschluss im Zustand $Z_3$:

   • Gelesenes Symbol: 0
   • Aktion: Kopf bleibt auf der 0, Zustandwechsel zu $Z_3$
   • Endkonfiguration: $Z_{3}0100\_$
   • Die Maschine akzeptiert den Zustand und beendet die Berechnung.

Linear beschränkte Turing-Maschinen (LBAs)

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

Definition und Funktion

• Begrenzter Bereich: Der Kopf darf den Bereich der Eingabe nicht verlassen.
• Markierung des Endes: Das Ende der Eingabe wird durch ein markiertes Symbol (z.B. ${\hat{A}}_m$) 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 (z.B. ${\hat{A}}_1$ bis ${\hat{A}}_n$).

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.

Der Satz von Coroda besagt, dass die kontextsensitiven Sprachen genau von den LBAs erkannt werden. Dies wird in speziellen Vorlesungen wie FSK bewiesen, während TIMI-Zuhörer diese Aussage als gegeben hinnehmen müssen. Die Idee des Beweises beinhaltet, dass der LBA alle Wörter einer bestimmten Länge generiert und prüft, ob das gegebene Wort abgeleitet werden kann.

Einschränkungen bei Produktionsregeln

Die Produktionsregeln dürfen nicht schrumpfen, was sicherstellt, dass Wörter nicht länger als die Zielwortlänge $W$ werden. Ein Wort, das über die Länge $W$ hinausgeht, bedeutet, dass die Satzform zu groß wird und nicht kleiner wird.

Linear beschränkte Automaten (LBA)

• Modell für Typ-1-Sprache: LBAs sind ein Modell für kontextsensitive Sprachen.
• Konstruktion der Grammatik: Eine Grammatik muss konstruiert werden, die den Ablauf von LBAs oder Turing-Maschinen simuliert.
• Unterschiede zu allgemeinen Turing-Maschinen: Bei allgemeinen Turing-Maschinen können nicht-deterministische Maschinen durch deterministische simuliert werden, indem alle Möglichkeiten nacheinander durchprobiert werden.

Turing-Maschinen in der Chomsky-Hierarchie

• Typ-0-Sprachen: Beliebige Turing-Maschinen.
• Typ-1-Sprachen: Linear beschränkte Turing-Maschinen (nicht deterministisch).
• Typ-2-Sprachen: Nicht-deterministische Kellerautomaten.
• Typ-3-Sprachen: Endliche Automaten (deterministisch und nicht deterministisch).

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.

Chomsky-Hierarchie

• Typ-0 (rekursiv aufzählbar): Beliebige Turing-Maschinen.
• Typ-1 (kontextsensitiv): Linear beschränkte Turing-Maschinen.
• Typ-2 (kontextfrei): Nicht-deterministische Kellerautomaten.
• Typ-3 (regulär): 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.

Abschlusseigenschaften

• Reguläre Sprachen: Abgeschlossen bezüglich 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.
• Kontextsensitive 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.

Die Turing-Maschine wird weiterhin ein zentrales Modell für die Untersuchung der Berechenbarkeit und Komplexität bleiben. Die TIMI-Zuhörer sollten sich mit diesem Modell vertraut machen, da es in den folgenden Vorlesungen intensiv genutzt wird.

---

VL-08b

Zusammenfassung Vorabzusammenfassung

Deterministisch-kontextfreie Sprachen (Seite 1)

• Verwendung: Untersuchung von deterministisch-kontextfreien Sprachen und deren Eigenschaften.
• Funktionsweise:
  • Definition: Deterministische Kellerautomaten (DPDA) akzeptieren Sprachen mit Endzuständen.
  • Einschränkungen: Epsilon-Übergänge sind nur erlaubt, wenn keine anderen Übergänge möglich sind.
  • Eigenschaften: Deterministisch-kontextfreie Sprachen können in linearer Zeit entschieden werden, sind unter Komplementbildung abgeschlossen, aber nicht unter Vereinigung und Schnitt.

Deterministisch-Kontextfreie Sprachen

Einführung

Willkommen zur Vorlesung über Formale Sprachen und Komplexität sowie Theoretische Informatik für Medieninformatiker. Heute behandeln wir eine spezielle Klasse der kontextfreien Sprachen: die deterministisch-kontextfreien Sprachen. Diese Vorlesung wird kürzer sein als gewöhnlich, da wir einige Beweise auslassen und uns auf die Definitionen und grundlegenden Eigenschaften konzentrieren.

Deterministisch-Kontextfreie Sprachen (DCKS)

Definition

Deterministisch-kontextfreie Sprachen (DCKS) sind kontextfreie Sprachen, die von deterministischen Kellerautomaten (DPDA) akzeptiert werden. Ein DPDA unterscheidet sich von einem allgemeinen Kellerautomaten (PDA) dadurch, dass er für jede Kombination von Zustand und Kellersymbol höchstens einen Übergang hat.

Ein Kellerautomat mit Endzuständen ist formal definiert als ein 7-Tupel:

$$(Z,\Sigma ,\Gamma ,\Delta ,Z_0,\text{Raute},E)$$

• $Z$: Menge der Zustände
• $\Sigma$: Eingabealphabet
• $\Gamma$: Kelleralphabet
• $\Delta$: Zustandsübergangsfunktion
• $Z_0$: Startzustand
• $\text{Raute}$: Startsymbol im Keller
• $E$: Menge der Endzustände

Ein DPDA ist deterministisch, wenn für alle Kombinationen von Zustand $Z$, Eingabesymbol $A$ und Kellersymbol $A$ gilt:

$$\Delta (Z,A,A)+\Delta (Z,Y,A)\le 1$$

Das bedeutet, es gibt höchstens einen Übergang für jede Kombination aus Zustand und Kellersymbol.

Akzeptanz durch Endzustände

Deterministische Kellerautomaten akzeptieren Eingaben durch das Erreichen eines Endzustands und nicht durch einen leeren Keller. Epsilon-Übergänge sind erlaubt, jedoch nur, wenn keine anderen Übergänge verfügbar sind.

Beispiel einer deterministisch-kontextfreien Sprache

Ein Beispiel für eine deterministisch-kontextfreie Sprache ist die Sprache:

$$L=\{w\text{Dollar}{w}^R\mid w\in \{a,b{\}}^{\ast }\}$$

Hier sind alle Wörter $w$, gefolgt von einem Dollarzeichen und dann dem umgekehrten Wort $w^R$, deterministisch kontextfrei. Ein DPDA kann diese Sprache akzeptieren, indem er den ersten Teil des Wortes im Keller speichert und im zweiten Teil vergleicht.

Eigenschaften deterministisch-kontextfreier Sprachen

Gutartige Eigenschaften

Deterministisch-kontextfreie Sprachen (DCKS) haben mehrere wünschenswerte Eigenschaften:

• Lineare Zeitentscheidung: Das Wortproblem für DCKS kann in linearer Zeit entschieden werden, da der DPDA deterministisch ist und daher für jede Eingabe genau eine Berechnung durchführt.
• Eindeutige Grammatiken: Für jede durch einen DPDA akzeptierte Sprache gibt es eine eindeutige Grammatik.
• Abgeschlossenheit unter Komplementbildung: Wenn eine Sprache durch einen DPDA akzeptiert wird, so wird auch ihr Komplement durch einen DPDA akzeptiert.

Nicht-Abgeschlossenheit

Deterministisch-kontextfreie Sprachen sind jedoch nicht unter allen Operationen abgeschlossen:

• Vereinigung: Die Vereinigung zweier deterministisch-kontextfreier Sprachen ist im Allgemeinen nicht deterministisch-kontextfrei.
• Schnitt: Der Schnitt zweier deterministisch-kontextfreier Sprachen ist im Allgemeinen nicht deterministisch-kontextfrei.

Beweise der Nicht-Abgeschlossenheit

Um zu zeigen, dass deterministisch-kontextfreie Sprachen nicht unter Schnitt und Vereinigung abgeschlossen sind, betrachten wir folgende Beweise:

• Nicht-Abgeschlossenheit unter Vereinigung und Schnitt:
  • Angenommen, deterministisch-kontextfreie Sprachen wären unter Vereinigung abgeschlossen. Dann wären sie auch unter Schnitt abgeschlossen, da der Schnitt als Komplement der Vereinigung der Komplemente ausgedrückt werden kann. Dies steht jedoch im Widerspruch zu unserem Wissen, dass der Schnitt nicht abgeschlossen ist.

Beispielsprachen

• Sprache $a^i{b}^i$: Diese Sprache ist deterministisch kontextfrei. Ein DPDA kann diese Sprache akzeptieren, indem er die $a$‘s auf den Keller schreibt und mit den $b$‘s vergleicht.
• Sprache $a^i{b}^i{c}^i$: Diese Sprache ist nicht deterministisch kontextfrei, da der DPDA nicht deterministisch entscheiden kann, wann er von den $a$‘s zu den $b$‘s wechseln soll.

Entscheidbarkeitsprobleme für kontextfreie Sprachen

Entscheidbare Probleme

Einige wichtige Entscheidbarkeitsprobleme für kontextfreie Sprachen sind entscheidbar:

• Leerheitsproblem: Gegeben eine kontextfreie Grammatik, ist die durch die Grammatik erzeugte Sprache leer? Dieses Problem ist entscheidbar.
• Endlichkeitsproblem: Gegeben eine kontextfreie Grammatik, ist die durch die Grammatik erzeugte Sprache endlich? Auch dieses Problem ist entscheidbar.

Unentscheidbare Probleme

Es gibt jedoch auch mehrere unentscheidbare Probleme für kontextfreie Sprachen:

• Äquivalenzproblem: Es ist unentscheidbar, ob zwei kontextfreie Grammatiken die gleiche Sprache erzeugen.
• Schnittproblem: Es ist unentscheidbar, ob der Schnitt zweier kontextfreier Sprachen leer ist.

Letzte Anmerkungen zu Entscheidbarkeitsfragen

Der CYK-Algorithmus und andere Algorithmen für Typ-1-Sprachen haben gezeigt, dass das Wortproblem für kontextfreie Grammatiken entscheidbar ist. Diese Algorithmen arbeiten in polynomieller Zeit (kubische Zeit).

In den folgenden Vorlesungen werden wir einige dieser Beweise detaillierter betrachten. Das nächste Video wird länger sein und weitere Beweise zu den Entscheidbarkeitsfragen liefern. Die dargestellten Konzepte sind entscheidend für das Verständnis der Struktur und Eigenschaften von formalen Sprachen, insbesondere im Kontext der theoretischen Informatik.

---

VL-08c

Zusammenfassung Vorabzusammenfassung

Einführung in die Turing-Maschinen und Chomsky-Hierarchie (Seite 1)

• Verwendung: Überblick über die Chomsky-Hierarchie und die Einführung der Turing-Maschinen als Modell für Typ 1 und Typ 0 Sprachen.
• Funktionsweise:
  • Typ 1 Sprachen: Kontext-sensitive Sprachen, definiert durch Grammatiken, die Wörter nicht schrumpfen lassen.
  • Typ 0 Sprachen: Allgemeine Sprachen, definiert durch unbeschränkte Grammatiken.
  • Turing-Maschinen: Ein allgemeines Berechnungsmodell für Typ 1 und Typ 0 Sprachen.
  • Linear-beschränkte Turing-Maschinen: Speziell für Typ 1 Sprachen.

Einführung in die Turing-Maschinen und Chomsky-Hierarchie

Einführung

Willkommen zur Vorlesung Formale Sprachen und Komplexität und Theoretische Informatik für Medieninformatiker. Nachdem wir die Typ 3 Sprachen, also die regulären Sprachen, und das entsprechende Maschinenmodell, die endlichen Automaten, behandelt haben, wenden wir uns nun den Typ 2 Sprachen zu. Diese kontextfreien Sprachen werden durch Kellerautomaten erkannt. In dieser Vorlesung betrachten wir die Typ 1 und Typ 0 Sprachen der Chomsky-Hierarchie, die durch Turing-Maschinen beschrieben werden.

Überblick über die Chomsky-Hierarchie

Die Chomsky-Hierarchie klassifiziert formale Sprachen nach ihrer Komplexität und den entsprechenden Grammatiken:

• Typ 3 Sprachen: Reguläre Sprachen, die von endlichen Automaten erkannt werden.
• Typ 2 Sprachen: Kontextfreie Sprachen, die von Kellerautomaten erkannt werden.
• Typ 1 Sprachen: Kontextsensitive Sprachen, die von linear beschränkten Turing-Maschinen erkannt werden.
• Typ 0 Sprachen: Rekursiv aufzählbare Sprachen, die von allgemeinen Turing-Maschinen erkannt werden.

Typ 1 und Typ 0 Sprachen

• Typ 1 Sprachen (Kontextsensitive Sprachen): Diese Sprachen sind durch Grammatiken definiert, bei denen die Produktionen die Wörter nicht schrumpfen lassen. Das bedeutet, dass die linke Seite einer Produktion höchstens so lang sein darf wie die rechte Seite.

  • Beispiel: Wenn eine Produktion $A\to \alpha$ in einer kontextsensitiven Grammatik existiert, dann gilt $|A|\le |\alpha |$.
  • Diese Grammatiken werden auch als monotone Grammatiken bezeichnet, da sie die Monotonie-Bedingung erfüllen.

• Typ 0 Sprachen (Rekursiv aufzählbare Sprachen): Diese Sprachen sind durch allgemeine Grammatiken definiert, die keine Einschränkungen auf die Produktionen haben. Jede Produktion ist erlaubt.

Turing-Maschinen

Das Automatenmodell für Typ 1 und Typ 0 Sprachen sind die Turing-Maschinen, die von Alan Turing vorgeschlagen wurden. Turing-Maschinen sind für beide Sprachtypen nützlich, wobei allgemeine Turing-Maschinen die Typ 0 Sprachen und linear platzbeschränkte Turing-Maschinen die Typ 1 Sprachen erkennen.

Motivation für Turing-Maschinen

Begrenzungen von Kellerautomaten

Kellerautomaten sind auf kontextfreie Sprachen beschränkt, da sie nur einen Kellerspeicher haben, auf den nur von oben zugegriffen werden kann. Ein Beispiel für eine Sprache, die nicht von einem Kellerautomaten erkannt werden kann, ist $a^i{b}^i{c}^i$. Beim Lesen der $a$‘s kann die Anzahl $i$ im Keller gespeichert werden. Beim Lesen der $b$‘s wird diese Anzahl sukzessive reduziert, sodass beim Lesen der $c$‘s die Anzahl $i$ nicht mehr verfügbar ist.

Überwindung der Begrenzungen mit Turing-Maschinen

Turing-Maschinen beheben diese Begrenzung, indem sie ein Band als Speicher verwenden, auf das beliebig zugegriffen werden kann. Dieses Band ist nach links und rechts unendlich und ermöglicht das Schreiben und Lesen an beliebigen Positionen. Dadurch können Turing-Maschinen komplexere Sprachen erkennen, die von Kellerautomaten nicht erkannt werden können.

Modell einer Turing-Maschine

Eine Turing-Maschine besteht aus folgenden Komponenten:

• Band: Ein unendlich langes Band, das in Felder unterteilt ist. Jedes Feld kann ein Symbol aus einem Bandalphabet enthalten.
• Schreib-Lesekopf: Ein Kopf, der über das Band bewegt werden kann und Symbole lesen und schreiben kann.
• Endliche Steuerung: Ein endlicher Automat, der die Operationen der Turing-Maschine steuert.

Formalisierung

Eine Turing-Maschine wird formal als ein 7-Tupel $(Z,\Sigma ,\Gamma ,\Delta ,Z_0,\text{Raute},E)$ definiert, wobei:

• $Z$: Eine endliche Menge von Zuständen.
• $\Sigma$: Das endliche Eingabealphabet.
• $\Gamma$: Das endliche Bandalphabet, wobei $\Gamma \supseteq \Sigma$.
• $\Delta$: Die Zustandsüberführungsfunktion.
• $Z_0$: Der Startzustand.
• $\text{Raute}$: Das Blanksymbol, das leere Felder auf dem Band markiert.
• $E$: Die Menge der Endzustände.

Zustandsüberführungsfunktion

Die Zustandsüberführungsfunktion $\Delta$ unterscheidet sich je nach Typ der Turing-Maschine:

• Deterministische Turing-Maschine (DTM): $\Delta :Z\times \Gamma \to Z\times \Gamma \times \{L,R,N\}$

  • Diese Funktion nimmt einen Zustand und ein Symbol und liefert ein Tripel aus neuem Zustand, neuem Bandsymbol und einer Bewegung (links, rechts oder neutral).

• Nicht-deterministische Turing-Maschine (NTM): $\Delta :Z\times \Gamma \to \mathcal{P}(Z\times \Gamma \times \{L,R,N\})$

  • Diese Funktion liefert eine Menge möglicher Tripel, was bedeutet, dass die Maschine mehrere mögliche Übergänge hat.

Konfiguration und Ablauf

Eine Konfiguration einer Turing-Maschine beschreibt den aktuellen Zustand, den Inhalt des Bandes und die Position des Schreib-Lesekopfes. Eine Konfiguration ist ein Wort aus ${\Gamma }^{\ast }Z{\Gamma }^{\ast }$ und beschreibt vollständig den aktuellen Status der Maschine. In jedem Schritt liest die Turing-Maschine ein Symbol, schreibt ein neues Symbol und bewegt den Kopf nach links, rechts oder bleibt an der aktuellen Position.

Vergleich zu Kellerautomaten

Kellerautomaten

• Eingabe: Linear von links nach rechts.
• Speicher: Keller mit Zugriff nur von oben.

Turing-Maschinen

• Eingabe: Band mit unendlicher Ausdehnung nach links und rechts.
• Speicher: Band, auf das beliebig zugegriffen werden kann.
• Schreib-Lesekopf: Kann sowohl lesen als auch schreiben und sich in beide Richtungen bewegen.

Anwendungen und Relevanz

Turing-Maschinen sind ein grundlegendes Modell in der theoretischen Informatik und dienen als Basis für das Verständnis 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 den folgenden Vorlesungen werden wir die formale Definition von Turing-Maschinen vertiefen und ihre Rolle in der Chomsky-Hierarchie und der theoretischen Informatik weiter untersuchen.

Konfiguration einer Turing-Maschine

Eine Konfiguration einer Turing-Maschine beschreibt den aktuellen Zustand, den Inhalt des Bands und die Position des Schreiblesekopfs. Dies wird als ein Wort der Form $WZ{W}^{\prime }$ geschrieben, wobei:

• $W$: Der Teil des Bandes links vom Schreiblesekopf.
• $Z$: Der aktuelle Zustand der Turing-Maschine.
• $W^{\prime }$: Der Teil des Bandes unter und rechts vom Schreiblesekopf.

Diese Darstellung bedeutet, dass die Turing-Maschine im Zustand $Z$ ist, das Band das Wort $W{W}^{\prime }$ enthält und der Schreiblesekopf auf dem ersten Symbol von $W^{\prime }$ steht. Links von $W$ und rechts von $W^{\prime }$ befinden sich nur Blanksymbole.

Startkonfiguration

Die Startkonfiguration einer Turing-Maschine für ein Eingabewort $W$ ist $Z_{0}W$. Hierbei steht der Schreiblesekopf auf dem ersten Symbol von $W$.

Spezialfall des leeren Wortes

Wenn das Eingabewort das leere Wort $ϵ$ ist, definieren wir die Startkonfiguration als $Z_0\text{Blank}$. In diesem Fall steht der Schreiblesekopf auf dem Blanksymbol. Das Band ist komplett leer und der Schreiblesekopf kann an beliebiger Stelle platziert werden, da das Band unendlich viele Zellen nach links und rechts hat.

Transitionsrelation

Die Transitionsrelation beschreibt die Bewegung der Turing-Maschine von einer Konfiguration zur nächsten. Angenommen, wir haben eine Turing-Maschine $M=(Z,\Sigma ,\Gamma ,\Delta ,Z_0,\text{Blank},E)$, dann definieren wir die Transitionsrelation ${⊢}_M$ wie folgt. Wir verwenden dabei die Zustandsübergangsfunktion $\Delta$.

Deterministische Turing-Maschine

Für eine deterministische Turing-Maschine wird die Transitionsrelation ${⊢}_M$ wie folgt definiert:

1. Neutralbewegung (N):

   • Gegeben sei die Konfiguration $B_1{B}_2\dots B_{M}Z{A}_1{A}_2\dots A_N$.
   • Wenn $\Delta (Z,A_1)=(Z^{\prime },C,N)$, dann wird dies zu $B_1{B}_2\dots B_M{Z}^{\prime }C{A}_2\dots A_N$.
   • Der Schreiblesekopf bleibt auf dem ersetzten Symbol $C$ stehen.

2. Bewegung nach links (L):

   • Gegeben sei die Konfiguration $B_1{B}_2\dots B_{M}Z{A}_1{A}_2\dots A_N$.
   • Wenn $\Delta (Z,A_1)=(Z^{\prime },C,L)$, dann wird dies zu $B_1{B}_2\dots Z^{\prime }{B}_{M}C{A}_2\dots A_N$.
   • Der Schreiblesekopf bewegt sich um eine Position nach links und steht nun auf dem Symbol $B_M$.

3. Bewegung nach rechts (R):

   • Gegeben sei die Konfiguration $B_1{B}_2\dots B_{M}Z{A}_1{A}_2\dots A_N$.
   • Wenn $\Delta (Z,A_1)=(Z^{\prime },C,R)$, dann wird dies zu $B_1{B}_2\dots B_{M}C{Z}^{\prime }{A}_2\dots A_N$.
   • Der Schreiblesekopf bewegt sich um eine Position nach rechts und steht nun auf dem Symbol $A_2$.

Spezialfälle

1. Bewegung nach rechts am Ende des Wortes:

   • Gegeben sei die Konfiguration $B_1{B}_2\dots B_{M}Z{A}_1\text{Blank}$.
   • Wenn $\Delta (Z,A_1)=(Z^{\prime },C,R)$, dann wird dies zu $B_1{B}_2\dots B_{M}C{Z}^{\prime }\text{Blank}$.
   • Der Schreiblesekopf bewegt sich um eine Position nach rechts auf das Blanksymbol.

2. Bewegung nach links am Anfang des Wortes:

   • Gegeben sei die Konfiguration $\text{Blank}Z{A}_1{A}_2\dots A_N$.
   • Wenn $\Delta (Z,A_1)=(Z^{\prime },C,L)$, dann wird dies zu $\text{Blank}{Z}^{\prime }C{A}_2\dots A_N$.
   • Der Schreiblesekopf bewegt sich um eine Position nach links auf das Blanksymbol und ein weiteres Blanksymbol wird links von $C$ eingefügt.

Notationen und Definitionen

Reflexiv-transitive Hülle

Für die i-fache Anwendung der Transitionsrelation schreiben wir ${⊢}_M^i$. Die reflexiv-transitive Hülle, also 0 oder mehrfache Anwendungen der Transitionsrelation, wird mit ${⊢}_M^{\ast }$ bezeichnet. Der Index $M$ wird weggelassen, wenn klar ist, welche Turing-Maschine gemeint ist.

Akzeptierte Sprache

Eine Turing-Maschine $M=(Z,\Sigma ,\Gamma ,\Delta ,Z_0,\text{Blank},E)$ akzeptiert ein Wort $w\in {\Sigma }^{\ast }$, wenn es eine Konfiguration $uZv$ gibt, wobei $Z\in E$ ein Endzustand ist und $uv\in {\Gamma }^{\ast }$ gilt, sodass die Startkonfiguration $Z_{0}w$ durch eine beliebige Anzahl von Schritten ${⊢}_M^{\ast }$ zu $uZv$ führt.

Triviale Beispiele

1. Akzeptanz aller Eingaben:

   • Wenn $Z_0\in E$, akzeptiert die Turing-Maschine jede Eingabe sofort.

2. Akzeptanz keiner Eingaben:

   • Wenn $E=\varnothing$, akzeptiert die Turing-Maschine keine Eingaben.

Darstellung als Zustandsgraph

Die Übergänge einer Turing-Maschine können als Zustandsgraph dargestellt werden. Eine Kante von $Z$ nach $Z^{\prime }$ ist beschriftet mit $A:B,X$, was bedeutet, dass im Zustand $Z$ das Symbol $A$ gelesen wird, durch $B$ ersetzt wird und der Kopf in Richtung $X$ bewegt wird.

Beispiel

Ein Beispiel aus dem Schöning-Buch mit vier Zuständen:

• Zustände: $Z_0,Z_1,Z_2,Z_3$
• Eingabealphabet: $\{0,1\}$
• Bandalphabet: $\{0,1,\text{Blank}\}$
• Startzustand: $Z_0$
• Blanksymbol: $\text{Blank}$
• Endzustand: $Z_3$

Übergänge

1. $Z_0\to Z_0$ bei Lesen von $0$ oder $1$:

   • Bei Lesen von $0$ oder $1$ wird das Symbol beibehalten und der Kopf nach rechts bewegt.
   • Ziel: Den rechten Rand der Binärzahl erreichen.

2. $Z_0\to Z_1$ bei Lesen von $\text{Blank}$:

   • Bei Lesen von $\text{Blank}$ wird das Symbol beibehalten und der Kopf nach links bewegt.

3. $Z_1$ invertiert Bits:

   • Bei Lesen von $1$ wird $1$ durch $0$ ersetzt und der Kopf nach links bewegt.
   • Bei Lesen von $0$ wird $0$ durch $1$ ersetzt und der Kopf nach links bewegt, dabei wird in $Z_2$ gewechselt.

4. $Z_2$ bewegt den Kopf nach rechts:

   • Bei Lesen von $0$ oder $1$ wird das Symbol beibehalten und der Kopf nach rechts bewegt.

5. $Z_2\to Z_3$ bei Lesen von $\text{Blank}$:

   • Bei Lesen von $\text{Blank}$ wird das Symbol beibehalten und die Maschine wechselt in den Endzustand $Z_3$.

Durch diese Übergänge wird die Binärzahl auf dem Band invertiert und die Turing-Maschine akzeptiert, wenn sie das Ende des Wortes erreicht hat.

Beispiel einer Turing-Maschine

Ablauf

Nehmen wir an, wir haben eine Turing-Maschine, die eine Binärzahl um 1 erhöht. Hier ist eine detaillierte Beschreibung des Ablaufs:

1. Rückwärtsbewegung und Inversion:

   • Der Kopf bewegt sich rückwärts über die Binärzahl und invertiert die Bits (1 wird zu 0, 0 wird zu 1), bis eine 0 zu einer 1 geändert wird.
   • Danach wechselt der Zustand in einen Modus, in dem keine weiteren Änderungen vorgenommen werden.

2. Zurück zum Start:

   • Im neuen Modus bewegt sich der Kopf weiter rückwärts zum Anfang der Eingabe.
   • Wenn der Kopf das Blanksymbol erreicht, wechselt er in den Endzustand und akzeptiert die Eingabe.

Transitionsrelationen im Detail

Betrachten wir die Konfigurationen und die Übergänge der Turing-Maschine im Detail:

1. Initiale Bewegung nach rechts:

   • Ausgangszustand: $Z_{0}00111$
   • Der Kopf bewegt sich nach rechts, wobei die Symbole unverändert bleiben.

2. Erreichen des rechten Endes:

   • Konfiguration nach mehreren Schritten: $00111\text{Blank}$
   • Der Kopf steht auf dem Blanksymbol im Zustand $Z_0$.

3. Wechsel zu $Z_1$ und Bewegung nach links:

   • Übergang: $Z_0\text{Blank}\to Z_1\text{Blank}$
   • Der Kopf bewegt sich nach links auf die letzte 1 und wechselt zu $Z_1$.

4. Invertieren der Bits und Übertrag:

   • Konfiguration: $0011\text{Blank}$
   • Der Kopf invertiert die Bits, wobei die 1 zu 0 wird und der Kopf nach links wechselt.
   • Sobald eine 0 in eine 1 geändert wird, wechselt der Zustand zu $Z_2$.

5. Bewegung nach links bis zum Start:

   • Konfiguration: $0100\text{Blank}$
   • Im Zustand $Z_2$ bewegt sich der Kopf weiter nach links, ohne die Symbole zu ändern.

6. Erreichen des linken Endes und Akzeptanz:

   • Übergang: $0100\to Z_3\text{Blank}0100$
   • Der Kopf erreicht das linke Blanksymbol, wechselt in den Endzustand $Z_3$ und akzeptiert die Eingabe.

Beispielablauf im Detail

Schritt-für-Schritt Analyse

1. Initiale Konfiguration:

   • Eingabe: $00111$
   • Startzustand: $Z_0$
   • Band: $\text{Blank}00111\text{Blank}$

2. Bewegung nach rechts:

   • Übergänge:
     • $Z_{0}0\to Z_{0}0R$
     • $Z_{0}0\to Z_{0}0R$
     • $Z_{0}1\to Z_{0}1R$
     • $Z_{0}1\to Z_{0}1R$
     • $Z_0\text{Blank}\to Z_1\text{Blank}L$
   • Konfiguration nach Bewegungen:
     • $00111\text{Blank}$
     • Kopf auf $\text{Blank}$, Zustand $Z_1$

3. Invertieren und Rückwärtsbewegung:

   • Übergänge:
     • $Z_{1}1\to Z_{1}0L$
     • $Z_{1}1\to Z_{1}0L$
     • $Z_{1}0\to Z_{2}1L$
   • Konfiguration nach Inversion:
     • $0100\text{Blank}$
     • Kopf auf der zweiten 0, Zustand $Z_2$

4. Bewegung zum Start und Akzeptanz:

   • Übergänge:
     • $Z_{2}0\to Z_{2}0L$
     • $Z_2\text{Blank}\to Z_3\text{Blank}$
   • Endkonfiguration:
     • $0100\text{Blank}$
     • Kopf auf der ersten 0, Zustand $Z_3$
     • Eingabe akzeptiert

Beispielanalyse

Die Turing-Maschine interpretiert die Eingabe als Binärzahl und addiert 1 hinzu. Der Ablauf kann zusammengefasst werden:

• Zustand $Z_0$: Bewegung nach rechts bis zum Ende der Eingabe.
• Zustand $Z_1: Invertieren der Bits und Bewegung nach links, bis eine 0 zu 1 geändert wird.
• Zustand $Z_2$: Weiteres Zurückbewegen bis zum Anfang der Eingabe.
• Zustand $Z_3$: Akzeptieren der Eingabe.

Ergebnisprüfung

Die Eingabe $00111$ wird korrekt um 1 erhöht zu $0100$, was der korrekten Addition 7 + 1 = 8 entspricht.

Varianten von Turing-Maschinen: LBAs

Linear beschränkte Turing-Maschinen (LBAs) sind eine Variante, bei der der Schreib-Lesekopf den Bereich der Eingabe auf dem Band nicht verlassen darf. Dies bedeutet, dass die Maschine nur innerhalb der Grenzen der ursprünglichen Eingabe operieren kann.

Definition

Eine LBA ist eine Turing-Maschine $M=(Z,\Sigma \cup \hat{\Sigma },\Gamma ,\Delta ,Z_0,\text{Blank},E)$, die folgende Bedingungen erfüllt:

• Der Schreib-Lesekopf darf den Bereich der Eingabe nicht verlassen.
• Die Eingabe ist am Ende mit einem speziellen Symbol ${\hat{a}}_m$ markiert, um das Ende der Eingabe anzuzeigen.

Eigenschaften

• LBAs erkennen kontextsensitive Sprachen (Typ 1 Sprachen).
• Die Länge der Konfigurationen bleibt immer innerhalb der ursprünglichen Eingabelänge.

Beispiel und Anwendung

Ein LBA beginnt mit einer Eingabe der Form $a_1{a}_2\dots a_{m-1}{\hat{a}}_m$ und arbeitet nur innerhalb dieser Grenzen. Es markiert das Ende der Eingabe und operiert entsprechend.

Satz von Kuroda

Der Satz von Kuroda besagt, dass kontextsensitive Sprachen genau die Sprachen sind, die von LBAs erkannt werden. Dies bedeutet, dass LBAs ein äquivalentes Modell für die Beschreibung von Typ 1 Sprachen darstellen.

Die Beweise und weitere Details zu LBAs und dem Satz von Kuroda werden in späteren Vorlesungen behandelt.

Zusammenfassung

In dieser Vorlesung haben wir eine detaillierte Beispielanalyse einer Turing-Maschine durchgeführt und die grundlegenden Transitionsrelationen und Konfigurationen erklärt. Wir haben gesehen, wie Turing-Maschinen Eingaben verarbeiten und welche Schritte notwendig sind, um eine Berechnung durchzuführen. Darüber hinaus haben wir eine spezielle Variante der Turing-Maschinen, die LBAs, eingeführt und ihre Bedeutung im Kontext der kontextsensitiven Sprachen erläutert.

Zusammenfassung Vorabzusammenfassung

Platzbeschränkung und Simulation von Turing-Maschinen (Seite 3)

• Verwendung: Erläuterung der Platzbeschränkungen für kontextsensitive Sprachen und die Simulation von nicht-deterministischen Turing-Maschinen.
• Funktionsweise:
  • Platzbeschränkung: Nutzung des Speicherplatzes entsprechend der Länge der Eingabe.
  • Simulation: Nicht-deterministische Turing-Maschinen können durch deterministische simuliert werden.
  • Vergleich: Unterschiede und Ähnlichkeiten zwischen deterministischen und nicht-deterministischen Turing-Maschinen.

Platzbeschränkung und Simulation von Turing-Maschinen

Platzbeschränkung bei kontextsensitiven Sprachen

Grundprinzip

Kontextsensitive Sprachen (Typ 1 Sprachen) unterliegen der Einschränkung, dass die Produktionen in ihren Grammatiken die Wörter nicht schrumpfen lassen dürfen. Das bedeutet, die Länge der abgeleiteten Wörter darf niemals kleiner werden als die Länge der vorhergehenden Wörter.

Bedeutung der Platzbeschränkung

Eine kontextsensitive Grammatik, die ein Wort $W$ der Länge $n$ erzeugt, benötigt nur den Platz der Eingabe, um das Wort abzuleiten. Da die Produktionen die Wörter nicht schrumpfen lassen, wächst die Länge der abgeleiteten Wörter monoton. Dies bedeutet, dass ein linear beschränkter Speicherplatz ausreicht, um die Ableitung durchzuführen.

Monotonie der Ableitungen

Die Ableitungen in einer kontextsensitiven Grammatik wachsen monoton in der Wortlänge. Bei kontextfreien oder kontextsensitiven Sprachen kann es hingegen passieren, dass die Wortlänge variiert. Bei kontextsensitiven Sprachen garantiert die Monotonie der Ableitungen jedoch, dass die Wortlänge nie schrumpft.

Umsetzung in Turing-Maschinen

Für kontextsensitive Sprachen verwenden wir linear beschränkte Turing-Maschinen (LBAs), die nur den Bereich der Eingabe auf dem Band nutzen dürfen. Dies bedeutet, dass die LBAs nur innerhalb des begrenzten Speicherbereichs operieren und das Band nicht verlassen dürfen.

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. Da der Verzweigungsgrad endlich ist, kann dieser Prozess durch Abzählen und systematisches Durchprobieren durchgeführt werden.

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. Wenn eine akzeptierende Berechnung gefunden wird, akzeptiert die deterministische Turing-Maschine die Eingabe.

Unterschiede in der Laufzeit

Obwohl NTMs und DTMs äquivalent in ihrer Ausdruckskraft sind, unterscheiden sie sich in der Laufzeitkomplexität. Die Simulation eines nicht-deterministischen Algorithmus durch einen deterministischen kann zu einer exponentiellen Laufzeit führen. Dieser Unterschied wird in der Komplexitätstheorie näher untersucht.

LBAs und ihre Rolle bei kontextsensitiven Sprachen

Definition und Eigenschaften

LBAs sind Turing-Maschinen, die den Speicherplatz auf die Länge der Eingabe beschränken. Die Eingabe wird am Ende mit einem speziellen Symbol markiert, um das Ende des Eingabebereichs anzuzeigen. Innerhalb dieser Begrenzung arbeitet die LBA, ohne den markierten Bereich zu verlassen.

Äquivalenz zu kontextsensitiven Sprachen

Ein wichtiger Satz in der formalen Sprachtheorie ist der Satz von Kuroda, der besagt, dass kontextsensitive Sprachen genau die Sprachen sind, die von LBAs erkannt werden. Das bedeutet, dass LBAs ein äquivalentes Modell für die Beschreibung und Erkennung von kontextsensitiven Sprachen darstellen.

Zusammenfassung und Ausblick

Überblick über die Chomsky-Hierarchie

Die Chomsky-Hierarchie klassifiziert formale Sprachen nach ihrer Komplexität und den entsprechenden Grammatiken. Die Hierarchie umfasst:

• Typ 0: Rekursiv aufzählbare Sprachen (allgemeine Turing-Maschinen)
• Typ 1: Kontext-sensitive Sprachen (linear beschränkte Turing-Maschinen)
• Typ 2: Kontextfreie Sprachen (Kellerautomaten)
• Typ 3: Reguläre Sprachen (endliche Automaten)

Automaten-Modelle und Grammatiken

Die verschiedenen Typen von Sprachen haben entsprechende Automaten-Modelle und Grammatiken:

• Typ 0: Allgemeine Turing-Maschinen (deterministisch und nicht-deterministisch)
• Typ 1: Linear beschränkte Turing-Maschinen (nicht-deterministisch)
• Typ 2: Kellerautomaten (nicht-deterministisch)
• Typ 3: Endliche Automaten (deterministisch und nicht-deterministisch)

Wichtige Resultate

• Äquivalenz von NTMs und DTMs: Beide akzeptieren die gleichen Sprachen, unterscheiden sich jedoch in der Laufzeit.
• Satz von Kuroda: Kontext-sensitive Sprachen werden genau von LBAs erkannt.
• Unbekannte Äquivalenz bei LBAs: Es ist nicht bekannt, ob deterministische und nicht-deterministische LBAs die gleichen Sprachen akzeptieren.

Ausblick

In den folgenden Vorlesungen werden wir uns intensiver mit der Berechenbarkeit und der Komplexität von Problemen befassen. Die Turing-Maschine wird dabei eine zentrale Rolle spielen, da sie das grundlegende Modell für die Berechenbarkeitstheorie darstellt. Wir werden untersuchen, welche Probleme berechenbar sind und welche nicht, und die Grenzen der Berechenbarkeit erforschen.

Abschließend sei gesagt, dass die formalen Sprachen und die zugehörigen Automaten-Modelle ein fundamentales Verständnis der theoretischen Informatik ermöglichen und die Grundlage für viele weitere Themen in der Informatik bilden.

---