Das Halteproblem für Turingmaschinen · Varianten des PKP IFester Startindex i 1 = 1: Das Modiﬁzierte PKP (MPKP) Eingabe: Ein endliches Alphabet , eine Zahl k 2N >0 und eine Folge

Das Halteproblem für Turingmaschinen

Das Halteproblem für Turingmaschinen ist definiert als die SpracheH := { 〈T 〉w : T ist eine TM, die bei Eingabe w ∈ {0, 1}∗ hält }.

Behauptung: H ⊆ {0, 1}∗ ist nicht entscheidbar.

Beweis:Wir zeigen, dass U 6 H ist, d.h. wir konstruieren eine Reduktion von U auf H.Aus der Unentscheidbarkeit von U folgt dann, dass auch H unentscheidbar ist.Die Reduktion von U auf H wird durch die Abbildung f : {0, 1}∗ → {0, 1}∗realisiert, bei der für alle u ∈ {0, 1}∗ das Wort f (u) wie folgt definiert ist:I Falls es eine TM T und ein Wort w ∈ {0, 1}∗ gibt, so dass u = 〈T 〉w , so ist

f (u) := 〈T ′〉w , wobei T ′ die TM ist, die T simuliert und immer dann, wenn Tin einem nicht-akzeptierenden Zustand hält, in eine Endlosschleife geht.Dann gilt: u ∈ U ⇐⇒ 〈T 〉w ∈ U ⇐⇒ T akzeptiert w

⇐⇒ T ′ hält bei Eingabe w ⇐⇒ 〈T ′〉w ∈ H ⇐⇒ f (u) ∈ H.

I Sonst setze f (u) := 〈T0〉ε, wobei T0 eine TM ist, die bei Eingabe ε sofort ineine Endlosschleife geht. Dann gilt: u 6∈ U und f (u) 6∈ H.

Man sieht leicht, dass die Funktion f berechenbar ist. Somit ist U 6 H mittels f .

Unentscheidbarkeit und Reduktionen Das Halteproblem H 61 / 76

Das spezielle Halteproblem

Das spezielle Halteproblem Hε für Turingmaschinen ist definiert als die SpracheHε := { 〈T 〉 : T ist eine TM, die bei Eingabe des leeren Worts ε hält }.

Behauptung: Hε ⊆ {0, 1}∗ ist nicht entscheidbar.

Beweis:Wir zeigen, dass H 6 Hε ist, d.h. wir konstruieren eine Reduktion von H auf Hε.Aus der Unentscheidbarkeit von H folgt dann, dass auch Hε unentscheidbar ist.Die Reduktion von H auf Hε wird durch die Abbildung f : {0, 1}∗ → {0, 1}∗realisiert, bei der für alle u ∈ {0, 1}∗ das Wort f (u) wie folgt definiert ist:I Falls es eine TM T und ein Wort w gibt, so dass u = 〈T 〉w , so ist

f (u) := 〈T ′〉, wobei T ′ die TM ist, die bei leerer Eingabe zunächst das Wortw aufs Band schreibt und dann T simuliert. Dann gilt:

u ∈ H ⇐⇒ 〈T 〉w ∈ H ⇐⇒ T hält bei Eingabe w

⇐⇒ T ′ hält bei Eingabe ε ⇐⇒ 〈T ′〉 ∈ Hε ⇐⇒ f (u) ∈ Hε.

I Sonst setze f (u) := 〈T0〉, wobei T0 eine TM ist, die bei Eingabe ε sofort ineine Endlosschleife geht. Dann gilt: u 6∈ H und f (u) 6∈ Hε.

Man sieht leicht, dass die Funktion f berechenbar ist. Somit ist H 6 Hε mittels f .

Unentscheidbarkeit und Reduktionen Das spezielle Halteproblem Hε 62 / 76

ZusammenfassungDie folgenden Sprachen über dem Alphabet {0, 1} sind nicht entscheidbar:

DiagonalspracheD = {〈T 〉 : T ist eine TM, die das Eingabewort 〈T 〉 nicht akzeptiert}

Universelle SpracheU = {〈T 〉w : T ist eine TM, die das Eingabewort w ∈ {0, 1}∗ akzeptiert}

HalteproblemH = {〈T 〉w : T ist eine TM, die bei Eingabe w ∈ {0, 1}∗ hält}

spezielles HalteproblemHε = {〈T 〉 : T ist eine TM, die bei Eingabe des leeren Worts ε hält}

Die folgenden Sprachen sind semi-entscheidbar, aber nicht entscheidbar:Hε, H, U, D = {0, 1}∗ \ D

Die folgenden Sprachen sind nicht semi-entscheidbar:Hε, H, U, D.

Frage: Gibt es auch unentscheidbare Probleme, die nichts mit Turingmaschinen oderEigenschaften von Programmen zu tun haben?

Unentscheidbarkeit und Reduktionen Das spezielle Halteproblem Hε 63 / 76

Das Postsche Korrespondenzproblem

Das Postsche Korrespondenzproblem 64 / 76

Das Postsche Korrespondenzproblem

Das Postsche Korrespondenzproblem (PKP)Eingabe: Ein endliches Alphabet Σ, eine Zahl k ∈ N>0 und eine Folge von

Wortpaaren (x1, y1), (x2, y2), . . . , (xk , yk ) mit x1, y1, . . . , xk , yk ∈ Σ+.

Frage: Gibt es ein n ∈ N>0 und Indizes i1, . . . , in ∈ {1, . . . , k}, so dassxi1 xi2 · · · xin = yi1 yi2 · · · yin ?

Beispiel:

Das PKP mit Eingabe Σ = {0, 1}, k = 3 und

(x1, y1) = (1, 111), (x2, y2) = (10111, 10), (x3, y3) = (10, 0).

hat eine Lösung mit n = 4 und i1 = 2, i2 = 1, i3 = 1, i4 = 3, denn:

x2x1x1x3 = 10111 1 1 10

y2y1y1y3 = 10 111 111 0.

Beachte: Das PKP ist semi-entscheidbar.

Ziel: Wir wollen zeigen, dass das PKP unentscheidbar ist.Das Postsche Korrespondenzproblem 65 / 76

Varianten des PKP

I Fester Startindex i1 = 1:

Das Modifizierte PKP (MPKP)Eingabe: Ein endliches Alphabet Σ, eine Zahl k ∈ N>0 und eine Folge von

Wortpaaren (x1, y1), (x2, y2), . . . , (xk , yk ) mit x1, y1, . . . , xk , yk ∈ Σ+.

Frage: Gibt es ein n ∈ N>0 und Indizes i1, . . . , in ∈ {1, . . . , k}, so dassi1 = 1 und xi1 xi2 · · · xin = yi1 yi2 · · · yin ?

Beispiel: Betrachtet als Eingabe für’s MPKP hat das auf der vorherigen Foliegegebene Beispiel keine Lösung.

I Festes Alphabet Σ:

Das PKP über Alphabet Σ (PKPΣ)Eingabe: Eine Zahl k ∈ N>0 und eine Folge von Wortpaaren (x1, y1), (x2, y2),

. . . , (xk , yk ) mit x1, y1, . . . , xk , yk ∈ Σ+.

Frage: Gibt es ein n ∈ N>0 und Indizes i1, . . . , in ∈ {1, . . . , k}, so dassxi1 xi2 · · · xin = yi1 yi2 · · · yin ?


Unentscheidbarkeit des PKP

Satz: Hε 6 MPKP 6 PKP 6 PKP{0,1}.

Insbesondere sind das Postsche Korrespondenzproblem PKP sowie seine VariantenMPKP und PKP{0,1} nicht entscheidbar.

Beweis:PKP 6 PKP{0,1}:I Für ein endliches Alphabet Σ = {a1, . . . , am} sei hΣ : Σ∗ → {0, 1}∗ der

Homomorphismus mit hΣ(aj ) := 0 1j für alle j ∈ {1, . . . ,m}.I Die Reduktion von PKP auf PKP{0,1} wird durch die Abbildung f realisiert, die einer

EingabeΣ, k , (x1, y1), . . . , (xk , yk )

für’s PKP die folgende Eingabe für’s PKP{0,1} zuordnet:

k ,(hΣ(x1), hΣ(y1)

), . . . ,

(hΣ(xk ), hΣ(yk )

).

I Für alle n ∈ N>0 und alle i1, . . . , in ∈ {1, . . . , k} gilt:xi1 xi2 · · · xin = yi1 yi2 · · · yin ⇐⇒ hΣ(xi1 )hΣ(xi2 ) · · · hΣ(xin ) = hΣ(yi1 )hΣ(yi2 ) · · · hΣ(yin ).

I f ist berechenbar. Somit ist f eine Reduktion von PKP auf PKP{0,1}.

MPKP 6 PKP: Übung! (siehe z.B. die Bücher von Wegener oder Schöning)Das Postsche Korrespondenzproblem 67 / 76

Unentscheidbarkeit des PKP: Hε 6 MPKP (1/2)Gesucht: Eine berechenbare Funktion f , die jedem Wort w ∈ {0, 1}∗ eine Eingabef (w) für’s MPKP zuordnet, so dass gilt:

w ∈ Hε, d.h. w = 〈T 〉 für eineTM T , die bei leerer Eingabe ε hält

⇐⇒ das MPKP f (w) besitzt eine Lösung

Leichter Fall: w ist keine Repräsentation einer TM.Dann sei f (w) eine Eingabe für’s MPKP, die keine Lösung besitzt, z.B.,Σ = {0, 1}, k = 1, x1 = 0, y1 = 1.

Schwieriger Fall: w = 〈T 〉 für eine TM T . Idee:I Repräsentiere Konfigurationen einer TM T = (Σ,Q, Γ, δ, q0,F ) durch Worte über

dem Alphabet Γ∪̇Q wie folgt:uqv repräsentiert die Situation, bei der die TM in Zustand q ist, dieBandinschrift uv ist, und der Kopf auf dem ersten Symbol von v steht.

I Startkonfiguration bei Eingabe des leeren Worts ε: q0�I O.B.d.A. betrachten wir nur Turingmaschinen, die nur dann in einen Zustand aus F

gehen, wenn sie unmittelbar danach anhalten.I Konstruiere eine Eingabe f (〈T 〉) für’s MPKP, die aufeinander folgende

Konfigurationen von T erzeugt.Alphabet: Γ ∪̇Q ∪̇ {#}. Das Symbol # dient als Trennsymbol zwischen einzelnen Konfigurationen.


Unentscheidbarkeit des PKP: Hε 6 MPKP (2/2)Für eine gegebene TM T werden die Wortpaare (x1, y1), (x2, y2), . . . , (xk , yk ) wie folgtgewählt (für ein geeignetes k ∈ N>0):

Starttupel: (x1, y1) mit x1 := # und y1 := #q0�#.

Überführungsregeln:I (qa, q′a′), falls δ(q, a) = (q′, a′, ↓)I (qa, a′q′), falls δ(q, a) = (q′, a′,→)I (bqa, q′ba′), falls δ(q, a) = (q′, a′,←), für b ∈ ΓI (#qa,#q′�a′), falls δ(q, a) = (q′, a′,←)I (q#, q′a′#), falls δ(q,�) = (q′, a′, ↓)I (q#, a′q′#), falls δ(q,�) = (q′, a′,→)I (bq#, q′ba′#), falls δ(q,�) = (q′, a′,←), für b ∈ Γ

Kopierregeln: (a, a) mit a ∈ Γ ∪ {#}.Löschregeln: (aq, q) sowie (qa, q) mit q ∈ F und a ∈ Γ

Abschlussregeln: (q##,#) mit q ∈ F .

Behauptung:T hält bei Eingabe ε ⇐⇒ f (〈T 〉) besitzt eine Lösung mit Starttupel (x1, y1).

Begründung: siehe Tafel.Das Postsche Korrespondenzproblem 69 / 76

Unentscheidbare Grammatik-Probleme

Unentscheidbare Grammatik-Probleme 70 / 76

Zwei Kontextfreie Grammatiken

Durch Reduktionen vom Postschen Korrespondenzproblem PKP können wir zeigen,dass viele Fragestellungen zu kontextfreien Grammatiken nicht entscheidbar sind:

Satz:Folgende Probleme, bei denen die Eingabe aus zwei kontextfreien Grammatiken Gund G′ besteht, sind unentscheidbar:

(a) Ist L(G) ∩ L(G′) = ∅? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Leerer Schnitt)

(b) Ist |L(G) ∩ L(G′)| =∞? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Unendlicher Schnitt)

(c) Ist L(G) ∩ L(G′) kontextfrei ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Kontextfreier Schnitt)

(d) Ist L(G) ⊆ L(G′) ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Subsumption)

(e) Ist L(G) = L(G′) ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Äquivalenz)

Beweis:(a)&(b): siehe Tafel

(c)–(e): Übung (siehe auch die Bücher von Wegener und Schöning)


Zwei Deterministisch Kontextfreie SprachenAuf ähnliche Art erhalten wir auch einen Beweis für folgenden Satz:

Satz:Folgende Probleme, bei denen die Eingabe aus zweideterministischen Kellerautomaten K und K ′ besteht, sind unentscheidbar:

(a) Ist L(K ) ∩ L(K ′) = ∅? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Leerer Schnitt)

(b) Ist |L(K ) ∩ L(K ′)| =∞? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Unendlicher Schnitt)

(c) Ist L(K ) ∩ L(K ′) kontextfrei ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Kontextfreier Schnitt)

(d) Ist L(K ) ⊆ L(K ′) ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (Subsumption)

Beweis: Ähnlich wie der Beweis des entsprechenden Resultate für KFGs:Z.B. beim Beweis der Unentscheidbarkeit des “Leerer Schnitt”-Problems für KFGshatten wir zwei Grammatiken G und G′ konstruiert, deren Sprachen L(G) und L(G′)sogar deterministisch kontextfrei sind.

Satz von Sénizergues (1997): (hier ohne Beweis)

Das Äquivalenzproblem für deterministische Kellerautomaten ist entscheidbar.D.h. es gibt einen Algorithmus, der bei Eingabe zweier DPDAs K und K ′ entscheidet,ob L(K ) = L(K ′) ist.


Eine Kontextfreie Grammatik

Satz:Folgende Probleme, bei denen die Eingabe aus einer kontextfreien Grammatik Gbesteht, sind nicht entscheidbar:

(a) Ist G mehrdeutig?

(b) Ist L(G) kontextfrei?

(c) Ist L(G) regulär?

(d) Ist L(G) deterministisch kontextfrei?

Beweis: (a): Wir reduzieren das (unentscheidbare) “Leerer Schnitt”-Problem fürDPDAs auf das Mehrdeutigkeitsproblem für KFGs:

Seien K1 und K2 zwei DPDAs.Konstruiere mit Hilfe der Tripelkonstruktion zwei eindeutige KFGsG1 = (Σ,V1,S1,P1) und G2 = (Σ,V2,S2,P2) mit L(G1) = L(K1) undL(G2) = L(K2). O.B.d.A. sind die Variablenmengen von G1 und G2 disjunkt.Sei G = (Σ,V ,S,P) mit V := {S}∪̇V1∪̇V2 und P := P1 ∪ P2 ∪ {S → S1 |S2}.Dann ist L(G) = L(G1) ∪ L(G2). Und G ist genau dann mehrdeutig, wennL(G1) ∩ L(G2) = ∅.

(b)–(d): Übung (siehe auch die Bücher von Wegener und Schöning)Unentscheidbare Grammatik-Probleme 73 / 76

Zusammenfassung

Zusammenfassung 74 / 76

Zusammenfassung (1/2)

I Wir haben folgende Begriffe kennengelernt:I entscheidbare ProblemeI semi-entscheidbare Probleme

(äquivalent zu: rekursiv aufzählbare Probleme)I berechenbare partielle Funktionen

I Wenn die Church-Turing-These korrekt ist, sind diese Begriffe unabhängig von derWahl des konkreten Berechnungsmodells.

I Als konkrete Berechnungsmodelle haben wir Turingmaschinen undMehrband-Turingmaschinen kennengelernt.

I Aus dem Satz von Rice folgt, dass fast alle semantischen Eigenschaften vonProgrammen oder Turingmaschinen unentscheidbar sind.

I Mittels Diagonalisierung haben wir gezeigt, dass die Diagonalsprache

D = {〈T 〉 : T ist eine TM, die die Eingabe 〈T 〉 nicht akzeptiert} ⊆ {0, 1}∗

nicht entscheidbar ist.



I Reduktionen lieferten die Unenscheidbarkeit vieler weiterer Sprachen(Merke: Wenn L unentscheidbar und L 6 K , dann ist auch K unentscheidbar):

I die universelle SpracheU := {〈T 〉w : T ist eine TM, die das Eingabewort w akzeptiert} ⊆ {0, 1}∗

I das HalteproblemH := {〈T 〉w : T ist eine TM, die bei Eingabe w hält} ⊆ {0, 1}∗

I das spezielle HalteproblemHε := {〈T 〉 : T ist eine TM, die bei Eingabe des leeren Worts hält} ⊆ {0, 1}∗

I das Postsche Korrespondenzproblem PKPund seine Varianten MPKP und PKP{0,1}

I viele Probleme, die kontextfreie Grammatiken oder deterministischeKellerautomaten betreffen,z.B. das “Leerer Schnitt”-Problem.


Kapitel: Die Chomsky Hierarchie

Die Chomsky Hierarchie 1 / 14

Allgemeine Grammatiken

DefinitionEine Grammatik G = (Σ,V ,S,P) besteht aus:

einem endlichen Alphabet Σ,

einer endlichen Menge V von Variablen (oder Nichtterminalen) mit Σ ∩ V = ∅,dem Startsymbol S ∈ V und

einer endlichen Menge P von Produktionen der Form u → v mit

u ∈ (Σ ∪ V )∗ V (Σ ∪ V )∗ und v ∈ (Σ ∪ V )∗

Eine Grammatik G erzeugt eine Sprache L(G) ⊆ Σ∗ wie folgt:

Beginne mit dem Startsymbol S und wende dann Produktionen an:

Eine Produktion u → v ersetzt ein Vorkommen von u durch ein Vorkommen von v .

Details: nächste Folie


Die von einer Grammatik erzeugte Sprache

Sei G = (Σ,V ,S,P) eine Grammatik.

Für eine Produktion u → v und ein Wort w1 = xuy wird das Wort w2 = xvyabgeleitet. Wir schreiben

xuy ⇒ xvy .

Für Worte r , s ∈ (Σ ∪ V )∗ schreiben wir

r ∗⇒ s :⇐⇒ Es gibt Worte w1 = r , w2, . . . , wk = s, für k > 1, so dass

w1 ⇒ w2 ⇒ · · · ⇒ wk .

s kann in null, einem oder mehreren Schritten aus r abgeleitet werden.

L(G) ={

w ∈ Σ∗ : S ∗⇒ w}

ist die von der Grammatik G erzeugte Sprache.


Beispiel: Eine Grammatik, die die Sprache L := {anbncn : n ∈ N>0} erzeugt

Wir wissen bereits, dass diese Sprache nicht kontextfrei ist — somit haben wir keineChance, eine kontextfreie Grammatik zu finden, die L erzeugt.

Eine nicht-kontextfreie Grammatik G = (Σ,V ,S,P) mit L(G) = L:I Σ = {a, b, c}I V = {S,B,C}I Startsymbol SI P besteht aus folgenden Produktionen: S → aSBC | aBC

CB → BCaB → abbB → bbbC → bccC → cc.

Behauptung: L(G) = {anbncn : n ∈ N>0}.

Beweis: siehe Tafel.


Die Chomsky Hierarchie (1/2)

(0) Allgemeine Grammatiken, wie sie am Anfang dieses Kapitels definiert wurden,heißen Typ 0-Grammatiken.

(1) Eine Grammatik G = (Σ,V ,S,P) heißt monoton oder Typ 1-Grammatik, falls fürjede Produktion (u → v) ∈ P gilt: |u| 6 |v |.Beispiel: Die Grammatik für {anbncn : n > 1} der vorherigen Folie ist monoton.

Eine Grammatik G = (Σ,V ,S,P) heißt kontextsensitiv, falls jede Produktion in Pvon der Form uXv → uxv ist, mit X ∈ V , u, x , v ∈ (Σ ∪ V )∗ und x 6= ε.

Beachte: Per Definition ist jede kontextsensitive Grammatik ist monoton.Umgekehrt kann man zeigen (hier ohne Beweis), dass es für jede monotoneGrammatik eine kontextsensitive Grammatik gibt, die dieselbe Sprache erzeugt.In der Literatur wird daher der Begriff “kontextsensitive Grammatik” oft alsSynonym für “monotone Grammatik” verwendet.

Sonderfall: Erzeugen des leeren WortsPer Definition gilt für monotone Grammatiken G, dass ε 6∈ L(G).Um auch Sprachen erzeugen zu können, die das leere Wort enthalten, erlauben wir alsTyp 1-Grammatiken auch Grammatiken der Form(

Σ, V ∪̇ {S′}, S′, P ∪ {S′ → ε | S}

),

wobei (Σ, V , S, P) eine monotone Grammatik ist.


Die Chomsky Hierarchie (2/2)

(2) Eine Grammatik G = (Σ,V ,S,P) heißt kontextfrei oder Typ 2-Grammatik, fallsjede Produktion in P von der Form X → x ist, mit X ∈ V und x ∈ (Σ ∪ V )∗.

Wir wissen bereits, dass die Typ 2-Grammatiken genau die kontextfreien Sprachenerzeugen.

Beachte: Für jede Typ 2-Grammatik G kann man leicht eine Typ 1-Grammatikkonstruieren, die dieselbe Sprache erzeugt:

1. Sei Vε = {X ∈ V : X ∗⇒ ε}.2. Für jedes A ∈ Vε tue Folgendes:

Entferne aus P alle Produktionen der Form A→ ε undfüge für jede Produktion der Form (B → uAv) ∈ P mit uv 6= εeine zusätzliche Produktion der Form B → uv ein.

3. Falls S ∈ Vε, so wähle ein neues Startsymbol S′ und füge die zusätzlichenProduktionen S′ → S und S′ → ε ein.

(3) Eine Grammatik G = (V ,Σ,S,P) heißt regulär oder Typ 3-Grammatik, falls jedeProduktion in P von der Form X → ε oder X → aY mit X ,Y ∈ V und a ∈ Σ ist.

Wir wissen bereits, dass die Typ 3-Grammatiken genau die regulären Sprachenerzeugen.


Die Sprachen der Chomsky Hierarchie

Für jedes i ∈ {0, 1, 2, 3} seiLi die Klasse aller Sprachen, die von Typ i-Grammatiken erzeugt werden.

Es gilt:I L3 ist die Klasse aller regulären Sprachen (kurz auch: REG oder Typ 3-Sprachen).I L2 ist die Klasse aller kontextfreien Sprachen

(kurz auch: CFL, für “context-free language”, oder Typ 2-Sprachen).I L1 wird die Klasse aller kontextsensitiven Sprachen genannt

(kurz auch: CSL, für “context-sensitive language”, oder Typ 1-Sprachen).I L0 wird die Klasse aller Typ 0-Sprachen genannt.

Es gilt:L0 )︸︷︷︸

H∈L0\L1

L1 )︸︷︷︸{anbncn :n>1}∈L1\L2

L2 )︸︷︷︸{anbn :n>1}∈L2\L3

L3.


Charakterisierung der Typ 0- und der Typ 1-Sprachen

Frage:

I Was genau sind die Typ 0-Sprachen?

I Was genau sind die Typ 1-Sprachen?

Antwort:

Satz:

(a) Die Typ 0-Sprachen sind genau die semi-entscheidbaren Sprachen L ⊆ Σ∗.

(b) Die Typ 1-Sprachen sind genau die Sprachen L ⊆ Σ∗, die von einernichtdeterministischen Turingmaschine mit linear beschränktem Platz entschiedenwerden können. Solche Turingmaschinen heißen auch linear beschränkteAutomaten (kurz: LBA).


Typ 0-Sprachen und Semi-Entscheidbare Sprachen (1/3)

Beweis von (a):

I Jede Typ 0-Sprache ist semi-entscheidbar:

Dies erhält man leicht durch einen Algorithmus, der bei Eingabe von w ∈ Σ∗ nachund nach sämtliche möglichen Ableitungen der Typ 0-Grammatik G durchprobiertund anhält, falls er eine Ableitung für w gefunden hat.

I Jede semi-entscheidbare Sprache wird von einer Typ 0-Grammatik erzeugt:

Sei T eine Turingmaschine, die L ⊆ Σ∗ semi-entscheidet.Wir konstruieren eine Grammatik G mit L(G) = L.

- Berechnungen von T beginnen natürlich stets mit der Eingabe w , aberAbleitungen von w enden mit w .

- Also sollten wir die Grammatik G so konstruieren, dass die Berechnungenvon T „rückwärts“ simuliert werden.

O.B.d.A gibt es nur einen Zustand qh, in dem T anhält,und wenn T hält, ist das Band leer.



Angenommen, wir unterbrechen die Berechnung von T auf Eingabe w zu einembeliebigen Zeitpunkt.

Wir beschreiben die aktuelle Konfiguration der TM genauso wie im Beweis derUnentscheidbarkeit des Postschen Korrespondenzproblems:

Die Situation, in der T im Zustand q ist, die Bandbeschriftung α1 · · ·αi−1αi · · ·αN

hat und der Kopf auf Position i steht, beschreiben wir durch das Wort

α1 · · ·αi−1 q αi · · ·αN ∈ (Γ ∪Q)∗.

- Unsere Grammatik G erzeugt diese Beschreibungen als Zwischenschritte.

- G erzeugt zuerst die Endkonfiguration, in der T mit leerem Band anhält, indemsie die folgende Produktion nutzt:

S → �qh�



- Für jeden Befehl δ(q, a) = (q′, b,←) nehmen wir die Produktion

q′cb → cqa

für alle c ∈ Γ auf:

Wenn die Konfiguration ∗ · · · ∗ q′cb ∗ · · · ∗ schon erzeugt wurde, können wirdamit die mögliche Vorgänger-Konfiguration ∗ · · · ∗ cqa ∗ · · · ∗ erzeugen.

- Für jeden Befehl δ(q, a) = (q′, b,→) nehmen wir die Produktion bq′ → qa auf.

- Für jeden Befehl δ(q, a) = (q′, b, ↓) nehmen wir die Produktion q′b → qa auf.

- Am Ende der Ableitung haben wir ein Wort der Form �∗q0w�∗ erzeugt.

- Jetzt lösche q0 und alle �-Symbole mit weiteren Produktionen.

Die dadurch entstehende Grammatik erzeugt genau die Worte, die von T akzeptiertwerden.


Typ 1-Sprachen und linearer Speicherplatz

Satz:L ⊆ Σ∗ ist genau dann kontextsensitiv, wenn L ⊆ Σ∗ von einer nichtdeterministischenTuringmaschinen auf linearem Speicherplatz entschieden wird.

Insbesondere ist jede kontextsensitive Sprache entscheidbar.

Beweis:“=⇒”: Es gelte L = L(G), für eine Typ-1 Grammatik G.Warum kann L von einer nichtdeterministischen Turingmaschine T auf linearem Platzakzeptiert werden?

T “rät” eine Ableitung S ∗⇒ w von w .

Falls S ⇒ u1 ⇒ u2 ⇒ · · · ⇒ u` mit u` = w eine Ableitung von w ist, so ist|ui | 6 |ui+1| 6 |w |, für alle i < `, da G monoton ist.

Daher kann T zu jedem Zeitpunkt i die Worte ui , ui+1, w auf seinem Bandspeichern.

Insgesamt reicht linearar Speicherplatz O(|w |) aus!

“⇐=”: Übung (ähnlich wie der entsprechende Beweis für Typ 0-Sprachen).



Die Chomsky-Hierarchie besteht aus folgenden Klassen von Sprachen:

I Typ 0-Sprachen, d.h. Sprachen, die von allgemeinen Grammatiken erzeugtwerden.Dies sind genau die semi-entscheidbaren Sprachen.

I Typ 1-Sprachen, d.h. Sprachen, die von monotonen (oder kontextsensitiven)Grammatiken erzeugt werden.Dies sind genau die Sprachen, die von linear beschränkten Automaten (d.h.nichtdeterministische Turingmaschinen mit linear beschränktem Platz) entschiedenwerden.

I Typ 2-Sprachen, d.h. Sprachen, die von kontextfreien Grammatiken erzeugtwerden.Dies sind genau die Sprachen, die von nichtdeterministischen Kellerautomatenakzeptiert werden.

I Typ 3-Sprachen, d.h. Sprachen, die von regulären Grammatiken erzeugt werden.Dies sind genau die Sprachen, die von endlichen Automaten akzeptiert werden.


Zusammenfassung (2/2)Trennende Beispiele:

I Eine Typ 2-Sprache (kontextfrei), die keine Typ 3-Sprache (regulär) ist:

{anbn : n > 1}.

I Eine Typ 1-Sprache (kontextsensitiv), die keine Typ 2-Sprache (kontextfrei) ist:

{anbncn : n > 1}.

I Eine Typ 0-Sprache (semi-entscheidbar), die keine Typ 1-Sprache ist:

Halteproblem H := { 〈T 〉w : T ist eine TM, die bei Eingabe w hält } ⊆ {0, 1}∗

I Eine Sprache, die keine Typ 0-Sprache ist:

H := {0, 1}∗ \ H.


Documents

Das Halteproblem für Turingmaschinen · Varianten des PKP IFester Startindex i 1 = 1: Das Modiﬁzierte PKP (MPKP) Eingabe: Ein endliches Alphabet , eine Zahl k 2N >0 und eine Folge