Zusammenfassung KE4 PDF

Preview

Summary

KE 4 Entscheidbare und erkennbare Sprachen 4 Das Modell Turingmaschine - Ziel: starkes Berechnungsmodell, das die Arbeitsweise eines idealisierten Computers nachbildet - eingeführt 1936 von Alan Turing - besteht aus: o Band (unendlicher Speicher) ▪ Blanksymbol □, nicht im Alphabet vorkommendes Zeich...

Description

KE 4 Entscheidbare und erkennbare Sprachen 4.1 Das Modell Turingmaschine • Ziel: starkes Berechnungsmodell, das die Arbeitsweise eines idealisierten Computers nachbildet • eingeführt 1936 von Alan Turing • besteht aus: o Band (unendlicher Speicher) ▪ Blanksymbol □, nicht im Alphabet vorkommendes Zeichen für Bandanfang/ende ▪ Übergänge vom Zeichen an Kopfposition abhängig o Steuermechanismus

•

•

•

•

•

Eingabe: o nicht separat verfügbar o wird auch nicht (notwendigerweise) zeichenweise verarbeitet o steht am Anfang der Berechnung auf dem Band und die Zeichen können in einer beliebigen Abfolge gelesen werden endliche Kontrolleinheit: o verfügt über zwei gesondert ausgezeichnete Zustände o Geht die Turingmaschine in einen dieser Zustände über, wird die Berechnung sofort gestoppt ▪ Einer dieser gesonderten Zustände ist der akzeptierende Zustand ▪ Der andere gesonderte Zustand ist der verwerfende Zustand Definition 4.1 — Turingmaschine. Unter einer Turingmaschine M verstehen wir ein 7-Tupel M = (Q, Σ, Γ, δ, q0, qA, qV), für das gilt o Q ist eine endliche Menge von Zuständen, o Σ ist ein endliches Alphabet (□ ∉ Σ), o Γ ist ein endliches Alphabet (das Arbeitsalphabet) (Σ ⊂ Γ, □ ∈ Γ), o δ : Q × Γ → Q × Γ × {L, R} (Übergangsfunktion), o q0 ∈ Q ist der Startzustand, o qA ∈ Q ist der akzeptierende Zustand, o qV ∈ Q ist der verwerfende Zustand (qV ≠ qA). Konfiguration einer TM o Konfiguration = Bandinhalt + Kopfposition + aktueller Zustand o Bandinhalt = beschriebene Zeichen des Bandes = endlicher Wert o Default Symbol des Bandes heißt Blanksymbol □ o Schreibweise für Konfigurationen: w1qw2 → Bandinhalt w1w2, Kopf hinter w1, Zustand q

Bsp.: aq3bbb Überführung von Konfigurationen

o o

die Übergangsfunktion δ bildet ein Paar von Zustand und Zeichen aus dem Arbeitsalphabet in ein Tripel von Zustand, Zeichen und einem Zeichen aus {L, R} ab δ(p, a) = (q, b, L):

δ(p, a) = (r, b, R):

•

•

• • •

•

•

Definition 4.2 — Akzeptanz eines Wortes durch eine Turingmaschine. Wir sagen, eine Turingmaschine akzeptiert die Eingabe w, falls es eine Folge von nichtverwerfenden Konfigurationen K0, K1, . . ., Km (Lauf) gibt, für die gilt: 1. K0 ist die Startkonfiguration bezüglich w, 2. für alle 1 ≤ i ≤ m ist Ki die Folgekonfiguration von Ki−1, 3. Km ist eine akzeptierende Konfiguration. Die Konfigurationsfolge bezeichnen wir als akzeptierenden Berechnungspfad der Turingmaschine bei Eingabe w L(M) bezeichnet die Menge der von M akzeptierten Wörter, akzeptierte Sprache. Häufig sprechen wir statt von akzeptierten Wörtern (Sprachen) auch von erkannten Wörtern (Sprachen). die Notation M(w) gibt an, dass wir eine Turingmaschine M mit Eingabe w betrachten. Berechnungspfad: eine Folge von Zustandsübergängen, wie in Definition 4.2, wobei Km entweder verwerfende oder akzeptierende Konfiguration ist Möglichkeiten für Nicht-Akzeptanz: o Lauf führt zu einer Konfiguration mit qv o Lauf erreicht weder qa noch qv (M stoppt nicht) → zykelt Angabe von TM Programmen: o 1. Diagrammform ▪ Programm wird präzise angegeben ▪ Spezifikation von Q und Γ ▪ Übergangsfunktion wird in Diagrammform angegeben ▪ Fehlende Übergänge im Diagramm würden nach qv führen ▪ Nachteil: unübersichtlich o 2. Modulbeschreibung ▪ Programm wird verbal beschrieben ▪ Abfolge von Modulen (= Befehlssequenzen) ▪ Module sind problemlos als TM-Teilprogramme formulierbar ▪ Nachteil: Interpretationsspielraum Definition 4.3 — entscheidbar. Eine Sprache L heißt entscheidbar, falls es einen Entscheider M gibt, sodass L(M) = L. Wir sagen, dass L durch M entschieden wird. Die Klasse der entscheidbaren Sprachen bezeichnen wir mit 𝔼. Die Sprachklasse 𝔼 wird häufig auch die Menge der rekursiven Sprachen genannt o o

• •

w ∈ L → TM stoppt in qA w ∉ L → TM stoppt in qV

Eine TM heißt Entscheider, wenn sie auf alle Eingaben stoppt. Definition 4.4 — erkennbar. Eine Sprache L heißt erkennbar, falls es eine Turingmaschine M gibt, sodass L(M) = L. Wir sagen, dass L durch M erkannt wird. Die Klasse der erkennbaren Sprachen bezeichnen wir mit 𝔸.

o o

w ∈ L → TM stoppt in qA w ∉ L → TM stoppt in qV oder zykelt

4.2 Varianten der Turingmaschine 4.2.1 Mehrband-Turingmaschine • Idee: TM hat k Bänder zur Verfügung

• •

• •

Kopfpositionen und Bewegungen unabhängig Übergang hängt von allen Zeichen auf Kopfpositionen ab → δ : Q × Γk → Q × Γk × {L, R, N}k L = links, R = rechts, N = neutral (Kopf wird nicht bewegt) Bsp.: δ(qi,(a,x)) = (ql,(y,c),(R,L)) Initial: Eingabe steht auf 1. Band, sonst überall Blanks Satz 4.1 Zu jeder Mehrband-Turingmaschine gibt es eine 1-Band-Turingmaschine, welche die gleiche Sprache akzeptiert. o Simulation durch Mehrspurtechnik ▪ Idee: Unterteile das Band durch Erweiterung des Arbeitsalphabetes in Spuren ▪ neues Arbeitsalphabet: Γk ▪ Spur i ist def. durch die i-ten Komponenten der Bandsymbols

o

Bsp. ▪ Ziel: Identifikation Spur = Band ▪ Wie kann man unabhängige Kopfbewegungen simulieren? Simulation der Kopfbewegungen: ▪ Extrazeichen für Markierung der Kopfposition ▪ a‘ für a, b‘ für b usw. ▪ Umsetzung der Markierung zum Abgleich der Kopfpositionen, ggf. Zeichen an Kopfposition ändern Bsp.:

▪

Für jeden Befehl gibt es nur ein Unterprogramm, welches das Umsetzen der Marken und das Ändern der Kopfposition übernimmt.

4.2.2 Halbband-Turingmaschine und LBA • Halbband-Turingmaschine hat ein einseitig beschränktes Band • Startkonfiguration: Kopf steht auf Zelle 0, Eingabe beginnt ab Kopfposition • Satz 4.2 Zu jeder Turingmaschine gibt es eine Halbband-Turingmaschine, welche die gleiche Sprache erkennt.

o

•

•

Beweisidee: Band der TM wird durch 2 Spuren auf dem Halbband simuliert, aktuelle Spur wird sich im Zustand „gemerkt“

Definition 4.5 — Linear beschränkter Automat (LBA). Eine Turingmaschinea , welche nur den Speicherplatz benutzen darf, auf dem ihre Eingabe anfangs stand, heißt Linear beschränkter Automat, kurz LBA. Falls der Kopf über den erlaubten Bereich hinausbewegt werden würde, bleibt er stattdessen stehen. a Nach der Definition ist ein LBA ein deterministisches Modell. Häufig wird auch das nichtdeterministische Äquivalent als LBA bezeichnet. Es ist nicht bekannt, ob beide Varianten gleichmächtig sind LBAs können weniger Sprachen erkennen als TMs

4.2.3 Nichtdeterministische Turingmaschine • Definition 4.6 — Nichtdeterministische Turingmaschine. Eine nichtdeterministische Turingmaschine (kurz NTM) ist ein 7-Tupel M = (Q, Σ, Γ, δ, q0, qA, qV), für welches die gleichen Bedingungen gelten wie für die Turingmaschine. Einzige Ausnahme ist die Übergangsfunktion δ, welche die Form δ : Q × Γ → P(Q × Γ × {L, R}) hat. • Definition 4.7 — Berechnungsbaum. Sei M eine NTM und w das Eingabewort. Der Berechnungsbaum zu M und w ist ein (nicht notwendigerweise endlicher) Baum, dessen Knoten mit Konfigurationen beschriftet sind. Die Wurzel des Berechnungsbaumes ist mit der Startkonfiguration beschriftet. Jeder Knoten mit Konfiguration K (K nicht verwerfend oder akzeptierend) hat ein Kind für jede Folgekonfiguration von K. Die Kinder sind mit den dazugehörigen Folgekonfigurationen beschriftet, Kurzform: o Baum dessen Knoten mit Konfigurationen beschriftet sind o Wurzel = Startkonfiguration o Blätter = akzeptierende / verwerfende Konfigurationen o Kinder eines Knotens mit Beschriftung C sind mit den Folgekonfigurationen von C beschriftet o Berechnungsbaum hängt von der TM und der Eingabe ab o es kann Knoten mit gleicher Beschriftung geben → nicht zusammenfassen! • Definition 4.8 — Akzeptanz eines Wortes durch eine NTM. Eine NTM N akzeptiert oder erkennt ihre Eingabe w, falls der Berechnungsbaum zu N und w einen Knoten enthält, der mit einer akzeptierenden Konfiguration beschriftet ist.

• •

Bsp.: Satz 4.3 Für jede nichtdeterministische Turingmaschine N gibt es eine Turingmaschine M mit L(M) = L(N).

•

4.2.4 Turingmaschinen für Funktionen • für Probleme die nicht nur mit „ja“ oder „nein“ beantwortet werden können • bei Entscheidungsproblemen/Sprachen o Funktion bildet von Σ* in die Menge {0, 1} ab (0 für „nein“, 1 für „ja“) → Charakteristische Funktion • bei anderen Funktionen o zusätzliches Ausgabeband o wird die Berechnung beendet, entspricht der beschriebene Teil des Ausgabebandes dem Funktionswert o TM zykelt → Funktion an dieser Stelle undefiniert • Definition 4.9 — partielle Funktion. Seien X und Y zwei Mengen. Eine Relation R ⊆ X × Y heißt partielle Funktion, falls es für jedes x ∈ X keine zwei y, y‘ ∈ Y gibt (y , y‘ ) mit (x, y) ∈ R und (x, y‘ ) ∈ R • Die Relationen, welche partielle Funktionen beschreiben, nennt man auch rechtseindeutig. • Partielle Funktionen, die für alle x ∈ X definiert sind, nennen wir totale Funktionen. • Definition 4.10 — berechenbare Funktion. Eine partielle Funktion heißt berechenbar, falls es eine Turingmaschine gibt, die diese Funktion berechnet. 4.3 Die Church–Turing-These • Begriff des Algorithmus: o Intuitiv: Ein Algorithmus besteht aus einer endlichen Anzahl von elementaren Anweisungen, sodass einer Eingabe in endlicher Zeit die Antwort „ja“ oder „nein“ zugeordnet werden kann o Problem: den Begriff „elementare Anweisungen“ zu formalisieren o Lösung (These): Wir identifizieren den Begriff des Algorithmus mit dem Begriff der Turingmaschine (als Instanz des Turingmaschinenmodells) → Church-Turing-These (nicht beweisbar) 4.4 Aufzählbare Sprachen • Modell: TM als Aufzähler:

o

ein Aufzähler für L ⊆ Σ* ist eine 2-Band TM mit einem Ausgabe- und einem Arbeitsband

Ausgabeband nicht lesbar, nach jedem Zugriff bewegt sich der Kopf nach rechts, bleibt sonst stehen o TM schreibt auf das Ausgabeband w1#w2#w3…, wobei # ∉ Σ und L ∪i wi o Definition 4.11 — Aufzähler. Ein Aufzähler ist eine deterministische Turingmaschine, die ein Arbeitsband und ein Ausgabeband besitzt. Der Kopf auf dem Ausgabeband kann nur an seiner Position verbleiben oder nach rechts umgesetzt werden. Zu Beginn der Berechnung sind Arbeitsband und Ausgabeband mit Blanksymbolen beschriftet o Achtung: Wiederholungen der Wörter aus L sind erlaubt Definition 4.12 — aufzählbar. Wir nennen eine Sprache L ⊆ Σ* aufzählbar, falls es einen Aufzähler A gibt, welcher auf das Ausgabeband das Wort w1#w2#w3# . . . schreibt (mit wi ∈ Σ*), sodass L = ∪i {wi}. Wir schreiben L(A) = L. Beispiel: L = Σ* = {0,1}* o Ablauf: Zähle zuerst Σ0 auf, dann Σ1, Σ2 usw (Standardaufzählung) o Teilmodul: Zähle Σi auf (Beginn: Arbeitsband 0i) ▪ 1. Kopiere Arbeitsband + # auf Ausgabe ▪ 2. Wenn auf Arbeitsband 1* steht, verlasse Modul ▪ Addiere +1 auf Binärzahl auf Arbeitsband ▪ Gehe zu 1. o Modul: Addiere +1 ▪ 1. Gehe nach rechts ▪ 2. Wenn Kopf auf 1 ersetzte 1 durch 0, gehe 1x nach links, wiederhole 2. ▪ 3. Wenn 0 ersetzte 0 durch 1 und stoppe Modul Satz 4.4 Eine Sprache ist genau dann aufzählbar, wenn sie erkennbar ist. o Beweis: o 1. Teil: L ist aufzählbar ⇒ L ist erkennbar ▪ sei A ein Aufzähler für L ▪ Wir konstruieren TM M, welche L erkennt ▪ M simuliert A auf zwei Extra-Bändern (Unterprogramm) ▪ Fall ein # aufs Ausgabeband geschrieben wurde, vergleiche ausgegebenes Wort mit Eingabe ▪ Wörter identisch → w ∈ L → akzeptiere ▪ Ansonsten fahre mit Simulation A fort ▪ M(w) zykelt für alle w ∉ L, aber das ist erlaubt o 2. Teil: L ist erkennbar ⇒ L ist aufzählbar ▪ sei M TM der L erkennt, wir konstruieren Aufzähler A für L ▪ Zähle Σ* als s1#s2#s3… auf Extra-Band auf (mittels Aufzähler, so weit wie benötigt) o

•

•

•

▪

▪ ▪

alle sj werden ab einem bestimmten i erkannt und erscheinen auf dem Ausgabeband sj ∉ L wird nie ausgegeben

4.5 co-Aufzählbare Sprachen • Definition 4.13 Sei C eine Klasse von Sprachen, dann definieren wir als co-C die Menge der Sprachen, deren Komplement in C ist. Es gilt also: co-C = {L | 𝐿 ∈ C} • im allg gilt nicht co-C = 𝐶 ; Bsp.: co-CFL ist nicht die Menge der nichtkontextfreien Sprachen, sondern die Menge der Sprachen, deren Komplement kontextfrei ist. • bei Sprachen, die unter Komplement abgeschlossen sind, gilt co-C = C Bsp.: co-REG = REG, co-CFL ≠ CFL • • •

Lemma 4.1 Die entscheidbaren Sprachen sind unter Komplement abgeschlossen. Es gilt also 𝔼 = co-𝔼. Satz 4.5 Es gilt: 𝔼 = 𝔸 ∩ co-𝔸 o Beweis:

4.6 Die Universelle Turingmaschine 4.6.1 Kodierung von Turingmaschinen • Ziel: jede TM als eindeutiges Wort über {0, 1} darstellen • Konventionen: o Zustände sind die Zahlen 1, 2, 3, … o 1 = q0, 2 = qa, 3 = qv o Γ = {a1, a2, a3,…} • Kodierung eines Befehls: o δ(i, ax) = (j, ay, L) entspricht 1i01x01j01y01 o δ(i, ax) = (j, ay, R) entspricht 1i01x01j01y011 0 :Trennzeichen • = 0000… • Konvention: syntaktisch fehlerhafte Wörter kodieren die alles verwerfende Maschine 4.6.2 Simulation von Turingmaschinen • Ziel: gesucht ist TM U, die andere TM simulieren kann • U() soll akzeptieren wenn M(w) akzeptiert, sonst nicht akzeptieren (verwerfen oder zykeln) • Aufbau von U:

•

•

•

o U besitzt Simulationsband, entspricht Band von M o Befehle werden auf einem Programmband abgelegt o Zustandsband enthält aktuellen Zustand der Simulation Simulation eines Schrittes von M(w): o suche auf dem Programmband nach einem ausführbaren Befehl o Modifiziere entsprechend des Befehls das Simulations- und Zustandsband (ersetzten durch Folgekonfiguration) Programm von U o Schreibe Startkonfiguration auf das Simulationsband (Eingabe w) o Simuliere einen Schritt von M(w) o Wiederhole bis akzeptierende oder verwerfende Konfiguration erreicht Satz 4.6 Es existiert eine Turingmaschine, genannt universelle Turingmaschine, welche bei Eingabe das gleiche Verhalten zeigt wie M(w).

4.7 Wichtige Sprachen mit Bezug zu Berechnungsmodellen • Sprache von UTM (universelle Turingmaschine) o ATM := { | die Turingmaschine M akzeptiert w} o die UTM ist kein Entscheider • Satz 4.7 Die Sprache ATM ist aufzählbar. • ähnliche Sprachen: o HALT := { | die TM M hält bei Eingabe w} o ETM := { | M ist Turingmaschine mit L(M) = ∅} o EQTM := {| M1, M2 sind Turingmaschinen mit L(M1) = L(M2)} o ACFG := { | w kann aus der kontextfreien Grammatik G abgeleitet werden} o ECFG := { | G ist kontextfreie Grammatik mit L(G) = ∅} o EQCFG := { | G1, G2 sind kontextfreie Grammatiken mit L(G1) = L(G2)} o ADEA := { | w wird vom DEA M akzeptiert} o EDEA := { | M ist DEA mit L(M) = ∅} o EQDEA := { | M1, M2 sind DEAs mit L(M1) = L(M2)} • Satz 4.8 Die Sprachen ACFG und ADEA sind entscheidbar 4.8 Abschlusseigenschaften der entscheidbaren und aufzählbaren Sprachen • Satz 4.9 Sowohl die entscheidbaren als auch die aufzählbaren Sprachen sind unter Schnitt und Vereinigung abgeschlossen. • Satz 4.10 Die aufzählbaren und die entscheidbaren Sprachen sind unter Konkatenation abgeschlossen...