Embed Size (px)
Citation preview
Tutorium zu Berechenbarkeit undKomplexitat
Notizen zu den vorgestellten Inhalten im Tutorium imWintersemester 2016 / 2017
Sebastian Kupper
29. Januar 2018
1 Kurzwiederholung Automaten und formale Sprachen
Berechenbarkeit und Komplexitat baut auf der Vorlesung”Automaten und formale Spra-
chen“ auf. Essener Studenten besuchen eine vergleichbare Vorlesung unter dem Titel
”Modelle der Informatik“. Zu Beginn des Tutoriums wiederholen wir einige Begrifflich-
keiten, Notationen und Ergebnisse aus der Automatentheorie, die fur das Verstandnisder Vorlesung Berechenbarkeit und Komplexitat hilfreich sein konnen. Die Inhalte diesesersten Teils des Tutoriums, sofern nicht ebenfalls Inhalt der Vorlesung oder der Ubung,sind nicht prufungsrelevant, konnen aber dazu beitragen, die Inhalte der Vorlesung undUbung besser zu verstehen und einzuordnen.
Notation 1.1. Im Folgenden verwenden wir die folgenden Symbole stets mit einer be-stimmten BedeutungΣ Alphabet (endliche Menge)Z Zustandsmenge eines Automaten (endliche Menge)G GrammatikS Startsymbol einer GrammatikV Variablenmenge einer Grammatik (endliche Menge)P Produktion einer Grammatik (Paare (V ∪ Σ)+ → (V ∪ Σ)∗)L Sprache (Teilmenge von Σ∗)ε Das leere Wort (die leere Sequenz uber einem beliebigen Alphabet Σ)Σ∗ Die Menge aller Sequenzen uber Σ, also
Σ∗ = a1a2, ...an | n ∈ N0,∀1 ≤ i ≤ n : ai ∈ ΣΣ+ Die Menge aller nicht-leeren Sequenzen uber Σ, also Σ+ = Σ∗ \ ε
Einer der wichtigsten Begriffe in der Theorie formaler Sprachen ist naturlich der Begriffeiner Sprache selbst.
Definition 1.2 (Sprache). Es sei Σ eine endliche Menge, genannt das Alphabet. Dannbezeichnen wir mit Σ∗ die Menge aller Worter (Sequenzen) uber Σ, formal:
Σ∗ = a1a2...an | n ∈ N0,∀1 ≤ i ≤ n : ai ∈ Σ
Σ∗ enthalt insbesondere auch die leere Sequenz ε, die wir auch das leere Wort nennen.Hierfur wird in obiger Definition n = 0 gesetzt.
Eine Sprache L uber dem Alphabet Σ (oder: Ein Problem) ist eine beliebige Teilmengevon Σ∗, i. Z. L ⊆ Σ∗.
Wir betrachten im Folgenden einige Beispiele fur Sprachen:
Beispiel 1.3. • ∅, die leere Sprache.
• Σ∗, die Sprache aller Worter.
• ε, die Sprache die nur das leere Wort enthalt.
• aw | w ∈ a, b∗ die Menge aller Worter uber dem Alphabet a, b, die mit abeginnen.
2
• anbn | n ∈ N0 uber dem Alphabet a, b.
• w ∈ (, )∗ | #((w) = #)(w) ∧ ∀w′ v w : #((w′) ≥ #)(w
′), die Sprache derkorrekt geklammerten Ausdrucke. v bezeichnet hierbei die Prafix-Relation. Es giltw′ v w genau dann wenn w sich schreiben lasst als w = w′w′′ mit w′′ ∈ a, b∗.
• N0 = n1n2...nm | m ∈ N,∀1 ≤ i ≤ m : ni ∈ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,m 6= 1 ⇒n1 6= 0.
• Primes = n ∈ N0 | n interpretiert als naturliche Zahl ist prim.
Bemerkung 1.4. In den Ubungen werden wir die Menge N0 oft mit der Zahlenmenge N0
identifizieren und dann, analog zur Sprache Primes, stets ein Wort uber N0 als naturlicheZahl in Dezimalschreibweise interpretieren. Analoge Schreibweisen werden fur Z oder Qverwendet.
Sprachen lassen sich auf verschiedene Weisen charakterisieren, im Kontext dieser Vor-lesung interessieren uns vor allem zwei Typen von Modellen:
1. Generative Modelle (Grammatiken)
2. Akzeptoren (Automaten / Maschinen)
Beide Modellsichten ergeben eine Hierarchie der Sprachen. Je allgemeiner das Modell,desto niedriger der Index der Sprachklasse, aber desto schwieriger wird es auch, Fragenuber die jeweilige Sprachklasse zu beantworten. Wir orientieren uns im Folgenden an derChomsky-Hierarchie der Sprachen, die anhand von Klassen von Grammatiken definiertist. Wir werden nun zunachst definieren was eine Grammatik ist und dann die Einteilungder Grammatikklassen vornehmen.
Definition 1.5. Eine Grammatik ist ein Vier-Tupel (V,Σ, P, S), wobei
• V eine endliche Menge, genannt die Menge der Variablen, ist. Wir verwenden furElemente A ∈ V ublicherweise Großbuchstaben und bezeichnen die Elemente vonV als Variablen.
• Σ eine endliche Menge, genannt das Alphabet, ist. Wir verwenden fur Elemen-te a ∈ Σ ublicherweise Kleinbuchstaben und bezeichnen die Elemente von Σ alsAlphabetsymbole oder Buchstaben.
• P eine Menge von Produktionen, das heißt Paaren (`, r) ∈ (V ∪ Σ)+ × (V ∪ Σ)∗.Dabei bezeichnet fur eine Menge M die Notation M+ := M∗ \ ε die Menge allernicht-leeren Sequenzen uber M . Wir verwenden fur P die sprechendere Notation`→ r.
• S ∈ V das Startsymbol genannt wird.
3
Eine Grammatik kann einen Ableitungsschritt an einem Wort w ∈ (V ∪ Σ)+ wie folgtdurchfuhren: Wenn es eine Regel ` → r gibt, so dass w sich schreiben lasst als w1`w2,w1, w1 ∈ (V ∪Σ)∗, dann kann w abgeleitet werden zu w1rw2. Das Vorkommen von ` wirdalso aus dem Wort entfernt und r an seiner Stelle eingesetzt. Wir schreiben
w ⇒G w1rw2
(oder w ⇒ w1rw2, wenn die Grammatik aus dem Kontext klar ist). Die von G erzeugteSprache ist definiert zu
L(G) = w ∈ Σ∗ | S ⇒∗G w.Dabei bezeichnet ⇒∗G die wiederholte Anwendung von ⇒G, die Sprache L(G) ist also dieMenge aller Worter, die keine Variablen enthalten und von S aus mittels G ableitbarsind.
Notation 1.6. Wir schreiben abkurzend, wenn es n Regeln mit der gleichen linken Seite` gibt, statt `→ r1, `→ r2, ..., `→ rn ublicherweise `→ r1 | r2 | ... | rn.
Schranken wir nun die Grammatiken formal ein, so erhalten wir eine Hierarchie derGrammatiken, die nach dem Linguisten Noam Chomsky benannt wurde, der sie ur-sprunglich aufgestellt hat.
Definition 1.7 (Chomsky-Hierarchie der Grammatiken). Es sei G = (V,Σ, P, S) eineGrammatik, dann nennen wir G eine Grammatik vom Typ
0 ohne, dass wir Einschrankungen an die Grammatik stellen.
1 falls gilt, dass fur alle Regeln ` → r gilt, dass |`| ≤ r, oder ` = S und fur alleRegeln ` → r gilt, dass S /∈ r. Regelanwendungen durfen also das Wort niemalsverkurzen, außer sie leiten S unmittelbar zum leeren Wort ab. Grammatiken diediese Bedingung erfullen, nennen wir auch kontextsensitiv.
2 falls G kontextsensitiv ist und zusatzlich fur alle Regeln ` → r gilt, dass ` ∈ V ,jede Regel also auf der linken Seite nur eine einzelne Variable enthalt. Wir nennenG in diesem Fall kontextfrei.
3 falls G kontextfrei ist und zusatzlich fur alle Regeln ` → r gilt, dass r = aA oderr = a, a ∈ Σ, A ∈ V . Wir nennen G in diesem Fall regular.
Auf diese Weise konnen Grammatiken in eine strenge Hierarchie eingeteilt werden.Jede Grammatikklasse enthalt alle Klassen mit hoherem Index, das bedeutet beispiels-weise, dass jede Grammatik vom Typ 3 ebenfalls vom Typ 2, vom Typ 1 und vom Typ0 ist. Weiterhin ist es offensichtlich, dass es fur i = 1, 2, 3 jeweils Grammatiken gibt, dievom Typ i − 1, aber nicht vom Typ i sind. Wir illustrieren dies an vier verschiedenenGrammatiken fur die Sprache L = aw | w ∈ a, b∗:
Beispiel 1.8. Die folgenden Grammatiken sind jeweils Grammatiken fur die SpracheL = aw | w ∈ a, b∗ uber dem Alphabet a, b. Es gilt also Gi = (A, S, a, b, Pi, Sfur i = 0, 1, 2, 3.
4
i = 0 P0 ist definiert gemaß: S → aA aA→ a | aAa | aAb.Die Grammatik ist vom Typ 0, da jede Grammatik vom Typ 0 ist. Allerdings istdie Grammatik nicht vom Typ 1, denn |aA| = 2, |a| = 1 und 2 6≤ 1. Also ist dieBedingung |`| ≤ r nicht fur alle Regeln `→ r erfullt.
i = 1 P1 ist definiert gemaß: S → aA | a aA→ aAa | aAb | aa | ab.Die Grammatik ist vom Typ 1, wie man einfach verifizieren kann: |S| = 1 ≤ 2 =|aA|, |S| = 1 = |a|, |aA| = 2 ≤ 3 = |aAa| = |aAb| und |aA| = 2 = |aa| = |ab|.Also ist |`| ≤ r fur alle Regeln ` → r erfullt. Als Grammatik vom Typ 1 ist dieseGrammatik automatisch auch von Typ 0. Allerdings ist die Grammatik nicht vomTyp 2, denn es gibt Regeln, bei denen die linke Seite nicht aus V stammt, namlichalle diejenigen Regeln, bei denen die linke Seite aA ist.
i = 2 P2 ist definiert gemaß: S → aA | a A→ Aa | Ab | a | b.Die Grammatik ist vom Typ 1, wie man analog zum vorherigen Fall verifizierenkann, und somit auch vom Typ 0. Zudem ist die Grammatik vom Typ 2, denn alslinke Seite tauchen nur A und S auf, die beide Variablen sind. Allerdings ist dieGrammatik nicht vom Typ 3, denn es gibt beispielsweise die Regel A→ Aa, die inregularen Grammatiken nicht erlaubt ist.
i = 3 P3 ist definiert gemaß: S → aA | a A→ aA | bA | a | b.Die Grammatik ist, wie man analog zum voherigen Fall verifizieren kann, vom Typ2 (und somit auch vom Typ 1, sowie vom Typ 0), obendrein ist die Grammatik auchvom Typ 3, denn es gibt nur Regeln, bei denen auf der rechten Seite entweder einAlphabetzeichen steht, oder aber einer der Ausdrucke aA oder bA, die jeweils dieForm haben, dass das erste Zeichen ein Alphabetzeichen und das zweite Zeicheneine Variable ist.
Der eigentliche Untersuchungsgegenstand in der Vorlesung sind aber ublicherweisenicht Grammatiken, sondern Sprachen. Die Chomsky-Hierarchie der Grammatiken kannauf naturliche Weise auf eine Hierarchie der Sprachen erweitert werden wie folgt:
Definition 1.9. Eine Sprache L ⊆ Σ∗ ist vom Chomsky-Typ i, i = 0, 1, 2, 3, falls eseine Grammatik G gibt, die den Chomsky-Typ i hat und L erzeugt, also gilt L(G) = L.
Es ist zu beachten, dass die Hierarchie der Sprachen, analog zur Hierarchie der Gram-matiken, aufeinander aufbaut, das bedeutet, dass jede Sprache vom Typ i, i > 0, auchvom Typ i− 1 ist. Das wird durch eine einfache Beobachtung deutlich: Ist eine SpracheL vom Typ i, so gibt es eine Grammatik G vom Typ i, die L erzeugt, nach Definitionder Sprachklassen. Da eine Grammatik vom Typ i stets auch vom Typ i− 1 ist, gibt esalso auch eine Grammatik – namlich gerade G – die vom Typ i− 1 ist und die Spracheerzeugt.
Um zu zeigen, dass eine Sprache von einem bestimmten Chomsky-Typ ist, reichtes aus, eine entsprechende Grammatik anzugeben. Um hingegen zu zeigen, dass eine
5
Sprache nicht von einem bestimmten Typ ist, sind weitere Anstrengungen notig. Im ein-fachsten Fall, den Typ 3-Sprachen, kann man hierzu ein passendes Automaten-Modellverwenden. Im Gegensatz zu Grammatiken, die als Erzeugersysteme fungieren – alsodergestalt sind, dass sie ermoglichen, Worter einer Sprache zu generieren – sind Auto-maten Akzeptoren. Das bedeutet, dass sie keine Worter generieren, sondern, ahnlich wieein Computer-Programm, eine Eingabe aus w ∈ Σ∗ erwarten und dann uberprufen, obdas Wort w in der Sprache liegt, die die Automaten generieren.
Definition 1.10. Ein deterministischer endlicher Automat ist ein FunftupelM = (Z,Σ, z0, δ, E) wobei Z und Σ endliche Mengen mit Z ∩Σ = ∅ sind und z0 ∈ Z derStartzustand, E ⊆ Z die Endzustandsmenge sind. δ : Z×Σ→ Z ist die Nachfolgerfunkti-on, die jedem Zustand und jedem Alphabetssysmbol einen eindeutigen Nachfolgerzustandzuordnet.
Die Menge der von einem Automat M akzeptierten Worter ist
L(M) = w = w1w2...wn | ∃z1, ..., zn ∈ Z, ∀0 ≤ i ≤ n− 1 : δ(zi, wi+1) = zi+1 ∧ zn ∈ E.
Wir schreiben abkurzend fur die obige Bedingung auch z0 →w zn. Wir nennen L(M) dievon M akzeptierte Sprache.
Es lasst sich relativ einfach einsehen, dass deterministische endliche Automaten exaktdie regularen Sprachen akzeptieren:
Satz 1.11. Die Menge der Sprachen, die von einem deterministischen endlichen Auto-maten akzeptiert werden, sind genau die regularen Sprachen.
Beweis. • Sei eine regulare Grammatik G = (V,Σ, P, S) gegeben, dann konnen wireinen deterministischen endlichen Automaten
M = (P(V ) ∪ E,Σ, S, δ, z ∈ P(V ) | ∃A ∈ z : A→ ε ∨ E ∈ z)
mit E /∈ V . Wir setzen
δ(z, a) = B | ∃A ∈ z : A→ aB ∪ E | ∃A ∈ z | A→ a
fur alle Zustande z ⊆ V und δ(E, a) = ∅. M akzeptiert die Sprache, die Gerzeugt.
• Sei nun umgekehrt ein deterministischer endlicher Automat M = (Z,Σ, z0, P, E)gegeben. Wir bilden, falls z0 kein Endzustand ist, die regulare Grammatik G =(Z,Σ, P, z0) mit z → az′ falls δ(z, a) = z′, z → a falls δ(z, a) = z′ und z′ ∈ E.Falls z0 ein Endzustand ist, mussen wir die Zustandsmenge um eine Kopie z′0 vonz0 erweitern, die die selben Produktionen erhalt wie z0, aber den Platz von z0 inallen Produktionen auf der rechten Seite einnimmt. Zusatzlich fuhren wir danndie Produktionsregel z0 → ε ein. Diese Grammatik erzeugt die Sprache, die derAutomat akzeptiert.
6
Wir geben nun ein Beispiel fur einen deterministischen endlichen Automaten, dergenau die Sprache aw | w ∈ a, b∗ akzeptiert, die wir zuvor betrachtet haben.
Beispiel 1.12. Wir betrachten den wie folgt definierten deterministischen endlichenAutomaten fur die Sprache L = aw | w ∈ a, b∗. M = (x, y, z, a, b, x, δ, y)wobei δ : x, y, z × a, b → x, y, z definiert ist gemaß
δ(x, a) = y δ(x, b) = zδ(y, a) = y δ(y, b) = yδ(z, a) = z δ(z, b) = z
Dieser Automat funktioniert wie folgt: Man startet im Zustand x. Ein Wort in L mussstets mit a beginnen, daher ist x nicht final – das leere Wort liegt nicht in der Sprache.Bei Eingabe eines as wechselt der Zustand zu y, einem Endzustand. Dort verbleibt derAutomat bei jeder weiteren Eingabe, da jedes Wort, das mit a beginnt, in der Spracheliegt. Gibt man in x hingegen ein b ein, so landet man im Zustand z, der die Funktioneines Fangzustandes hat. Egal, was man hier eingibt, man landet stets wieder in z undkann niemals einen Endzustand erreichen. Grafisch kann man den Automaten wie folgtdarstellen.
x y
z
a
b
a, b
a, b
Eine Beispielsaufgabe
Geben Sie einen deterministischen endlichen Automaten fur die Sprache L = (ab)n |n ∈ N0 an.
Denken Sie zunachst fur funf Minuten alleine uber diese Fragen nach. Besprechen Siesich anschließend (5 Minuten) mit Ihrem Partner um zu einer gemeinsamen Losung zugelangen. Im Anschluss werden die Ergebnisse dem Plenum prasentiert und gemeinsamdiskutiert.
Hinweis: Es ist moglich (aber nicht notwendig), einen Automaten mit drei Zustandenanzugeben.
Losungsskizze
M = (x, y, z, a, b, x, δ, y) wobei δ : x, y, z×a, b → x, y, z definiert ist gemaß
7
δ(x, a) = y δ(x, b) = zδ(y, a) = z δ(y, b) = xδ(z, a) = z δ(z, b) = z
Grafisch:
x y
z
a
b
b
a
a, b
Neben den deterministischen endlichen Automaten gibt es auch noch nicht-deterministischeendliche Automaten, bei denen nicht in jedem Zustand fur jedes Symbol ein Ubergang de-finiert sein muss und uberdies die Moglichkeit besteht, aus mehreren moglichen Ubergangenzu wahlen.
Definition 1.13. Ein nichtdeterministischer endlicher Automat ist ein FunftupelM = (Z,Σ, Z0, δ, E) wobei Z und Σ endliche Mengen mit Z∩Σ = ∅ sind und Z0 ⊆ Z dieMenge der Startzustande, E ⊆ Z die Endzustandsmenge sind. δ : Z ×Σ→ P(Z) ist dieNachfolgerfunktion, die jedem Zustand und jedem Alphabetssysmbol eine (moglicherweiseleere) Menge von Nachfolgerzustanden zuordnet.
Die Menge der von einem Automat M akzeptierten Worter ist
L(M) = w = w1w2...wn | ∃z1, ..., zn ∈ Z, ∀0 ≤ i ≤ n−1 : δ(zi, wi+1) 3 zi+1∧zn ∈ E∧z0 ∈ Z0.
Wir schreiben abkurzend fur die obige Bedingung auch z0 →w zn. Wir nennen L(M) dievon M akzeptierte Sprache.
Aus der Intuition uber nichtdeterministische endliche Automaten heraus ist bereitsoffensichtlich, dass es zu jeder regularen Sprache einen nichtdeterministischen endlichenAutomaten gibt, der sie akzeptiert. Umgekehrt ist es aber auch moglich, zu zeigen, dassjede Sprache, die von einem nichtdeterministischen Automaten akzeptiert wird, regularist. Hierzu muss man nur zeigen, dass die von einem nichtdeterministischen Automatenakzeptierte Sprache auch von einem deterministischen Automaten akzeptiert werdenkann.
Satz 1.14. Nichtdeterministische Automaten akzeptieren genau die regularen Sprachen
Beweis. Gegeben sei ein nichtdeterministischer Automat M = (Z,Σ, Z0, δ, E), wir kon-struieren einen deterministischen Automaten, der die gleiche Sprache akzeptiert. Es seihierzu M ′ = (P(Z), Z0, δ
′, ZE | ZE ∩ E 6= ∅). Dabei ist δ′(Z ′, a) = δ(z, a) | z ∈ Z ′.M ′ akzeptiert genau die Sprache, die M akzeptiert, denn wann immer es eine Folge vonUbergangen z0 →a1 z1 →a2 z2 →a3 ...→an zn mit z0 ∈ Z und zn ∈ E in M gibt, gibt esauch eine Folge von Ubergangen Z0 →a1 Z1 →a2 Z2 →a3 ... →an Zn, wobei zi ∈ Zi fur
8
alle 1 ≤ i ≤ n. Zudem ist Zn ein Endzustand des deterministischen Automaten vermogezn ∈ Zn. Analog kann der nichtdeterministische Automat gemaß der Definition von δ′
jede akzeptierende Ubergangssequenz simulieren, M und M ′ akzeptieren also die selbeSprache.
Wir betrachten nun auch ein Beispiel fur einen nichtdeterministischen endlichen Au-tomaten, wieder fur die Sprache aller Worter die mit a beginnen.
Beispiel 1.15. Wir betrachten den wie folgt definierten deterministischen endlichenAutomaten fur die Sprache L = aw | w ∈ a, b∗. M = (x, y, a, b, x, δ, y) wobeiδ : x, y × a, b → P(x, y) definiert ist gemaß
δ(x, a) = x, y δ(x, b) = ∅δ(y, a) = y δ(y, b) = y
Dieser Automat funktioniert wie folgt: Man startet im Zustand x. Ein Wort in L mussstets mit a beginnen, daher ist x nicht final – das leere Wort liegt nicht in der Sprache.Bei Eingabe eines as wechselt der Zustand zu y, einem Endzustand, oder verbleibt in x.Im Zustand y verbleibt der Automat bei jeder weiteren Eingabe, da jedes Wort, das mita beginnt, in der Sprache liegt. Gibt man in x hingegen ein b ein, so ist kein Folgezu-stand definiert und der Automat blockiert. Grafisch kann man den Automaten wie folgtdarstellen.
x ya
aa, b
Zudem konnen wir auch die Potenzmengenkonstruktion durchfuhren um diesen Auto-maten wiederum in einen deterministischen Automaten zu uberfuhren. Auf diese Weiseerhalten wir den Automaten M =′ (∅, x, y, x, y, a, b, x, δ′, y, x, y) wobeiδ : Px, y × a, b → P(x, y) definiert ist gemaß
δ(∅, a) = ∅ δ(∅, b) = ∅δ(x, a) = x, y δ(x, b) = ∅δ(y, a) = y δ(y, b) = yδ(x, y, a) = x, y δ(x, y, b) = ∅
Grafisch ist dieser Automat wie folgt darstellbar:
x y
x, y∅
ab
a
b
a, b
a, b
9
Da deterministische und nichtdeterministische Akzeptoren in Berechenbarkeit undKomplexitat eine wichtige Rolle spielen, haben wir an dieser Stelle gezeigt, dass dieAusdrucksmachtigkeit nichtdeterministischer Automaten und deterministischer Auto-maten gleich ist. Allerdings findet bei der Determinisierung mithilfe der Potenzmengeein exponentielles Wachstum des Zustandsraumes statt. Ein solches Phanomen werdenwir spater auch bei deterministischen und nichtdeterministischen Turingmaschinen – denAkzeptoren fur Typ 0-Sprachen – erleben und es ist ein entscheidender Motivator furdie Komplexitatstheorie im abschließenden Teil der Vorlesung. Es gibt noch eine Reiheweiterer Modelle fur regulare Sprachen, beispielsweise regulare Ausdrucke, diese findenaber keine Entsprechung in den Typ 0 Sprachen und sind daher fur Berechenbarkeit undKomplexitat nicht relevant.
Nun wollen wir untersuchen, wie man zeigen kann, dass eine Sprache nicht regularist. Hierzu werden oft zwei Techniken verwendet, das Pumping-Lemma fur regulareSprachen und die Myhill-Nerode Aquivalenzklassen. Wir konzentrieren uns hier auf dieMyhill-Nerode Aquivalenzklassen.
Definition 1.16 (Myhill-Nerode Aquivalenzklassen). Gegeben sei eine (nicht notwendi-gerweise regulare) Sprache L ⊆ Σ∗. Wir definieren fur jedes Wort w ∈ L die zugehorigeMyhill-Nerode Aquivalenzklasse
[w]L = u ∈ Σ∗ | ∀v ∈ Σ∗ : uv ∈ L⇔ wv ∈ L.
Die Myhill-Nerode Aquivalenzklassen definieren tatsachlich eine Aquivalenzrelation≡L, der einfache Beweis hierfur sei an dieser Stelle dem Leser uberlassen. Wir zeigenstattdessen das folgende entscheidende Resultat:
Satz 1.17. Es sei L ⊆ Σ∗. L ist regular genau dann, wenn ≡L endlich viele Aquivalenzklassenbesitzt.
Beweis. (Skizze) Wir zeigen die beiden Richtungen separat:
• Sei zunachst bekannt, dass ≡L nur endlich viele Aquivalenzklassen besitzt. Dannkonnen wir einen deterministischen endlichen Automaten definieren wie folgt:
M = ([w]L | w ∈ Σ∗,Σ, [ε]L, δ, [w]L | w ∈ L)
Dabei ist δ([w]L, a) = [wa]L.
• Sei nun andersherum L regular. Dann gibt es einen deterministischen endlichenAutomaten M = (Z,Σ, z0, δ, E) der L akzeptiert. Wir mussen nur zeigen, dasses endlich viele Aquivalenzklassen gibt. Wir definieren die Klassen [z]M = w ∈Σ∗ | z0 →w z, die fur jeden Zustand alle Worter w enthalt, mit denen manvom (eindeutigen) Startzustand z0 in den Zustand z gelangen kann. Die Klassen[z]M sind nicht notwendigerweise verschiedene Myhill-Nerode Aquivalenzklassen,allerdings ist – da der Automat deterministisch ist – jedes Wort in mindestenseiner dieser Klassen enthalten und jedes Paar von Wortern, das in einer Klasse[z]M liegt ist Myhill-Nerode aquivalent. Also gibt es maximal endlich viele Myhill-Nerode Aquivalenzklassen.
10
Mithilfe der Myhill-Nerode Aquivalenzklassen kann man beispielsweise zeigen, dassdie Sprache L = anbn nicht regular ist. Die Sprache besitzt namlich unendlich vieleAquivalenzklassen, namlich fur jedes n ∈ N0 die Aquivalenzklassen [an] (enthalt nur einElement) und [anb] (enthalt alle Worter der Form ambk mit m = k + 1 + n) sowie dieAquivalenzklassen [ab] = L \ ε und [b] (enthalt alle Worter, die nicht die Form anbm
mit m ≤ n haben).Wir wollen nun ein Beispiel zur eigenen Bearbeitung betrachten:
Eine Beispielsaufgabe
Nachdem wir gesehen haben, dass die Sprache L = anbn | n ∈ N0 nicht von einem de-terministischen endlichen Automaten akzeptiert werden kann, wollen wir nun den Blickauf ein etwas praktischeres Problem richten. Wir nennen einen geklammerten Audruckwohlgeformt, wenn die Zahl der offnenden und schließenden Klammern gleich ist undvon links nach rechts gelesen die Zahl der offnenden Klammern, die im Wort vorkommenstets großer oder gleich der Zahl der schließenden Klammern ist. Formal lasst sich dieseSprache schreiben als
L = w ∈ (, )∗ | #((w) = #)(w) ∧ ∀w′ v w : #((w′) ≥ #)(w
′)
Beispielsweise ist der Ausdruck ((())()) wohlgeformt, aber der Ausdruck (() ist nichtwohlgeformt – die Zahl der schließenden Klammern ist geringer als die Zahl der offnendenKlammern – und der Ausdruck )(() ist ebenfalls nicht wohlgeformt, weil vor der erstenschließenden Klammer keine offnende Klammer steht. Uberlegen Sie sich im Folgenden:
1. Gibt es unendlich viele verschiedene Aquivalenzklassen von Wortern bzgl L uber(, )?
2. Zeigen Sie, dass die von Ihnen gefundenen Aquivalenzklassen tatsachlich verschie-den sind.
3. Geben Sie fur jedes Wort aus (, )∗ an, in welcher Aquivalenzklasse es liegt.
Denken Sie zunachst fur zehn Minuten alleine uber diese Fragen nach. Besprechen Siesich anschließend (15 Minuten) mit Ihrem Partner um zu einer gemeinsamen Losung zugelangen. Im Anschluss werden die Ergebnisse dem Plenum prasentiert und gemeinsamdiskutiert.
Hinweis: Schauen Sie sich noch einmal die Aquivalenzklassenbildung der Spracheanbn | n ∈ N0 an, wenn Sie Schwierigkeiten haben, eine Idee zu entwickeln. Gegebe-nenfalls kann es auch hilfreich sein, sich fur die folgenden Beispielsworter zu uberlegen,ob sie paarweise zueinander aquivalent sind: w1 = (, w2 = ((, w3 = ()(, w4 =).
11
Losungsskizze
1. Fur jede naturliche Zahl n ∈ N0 gibt es eine Aquivalenzklasse [(n], die alle Aus-drucke enthalt, in denen von links nach rechts gelesen stets mehr offnende alsschließende Klammern vorkommen und insgesamt n offnende Klammern mehr vor-kommen als schließende Klammern. Zusatzlich gibt es eine Aquivalenzklasse [)] diealle Worter enthalt, die nicht mehr zu einem wohlgeformten Ausdruck fortgesezztwerden konnen, da es ein Prafix gibt, das eine geschlossene Klammer mehr enthaltals geoffnete Klammern.
2. [(n] 6≡ [(m)] falls n 6= m, weil fur jedes Wort w ∈ [(n] das Wort w)n ∈ L ist, aberfur jedes Wort w′ ∈ [(m] ist das Wort w′)n /∈ L.
3. Vgl. Aufgabenteil 1 fur die Zuordnung zu Aquivalenzklassen. Der Aufgabenteil istseparat gehalten, weil die Identifikation unendlich vieler Klassen in vollstandigerAnalogie zu dem Beispiel anbn | n ∈ N0 moglich ist, ohne fur jedes Wort anzu-geben in welcher Klasse es sich befindet.
Als nachstes wenden wir unseren Blick den kontextfreien Sprachen zu. Auch kon-textfreie Sprachen konnen durch einen Akzeptor charakterisiert werden, in diesem Fallvon einem (nichtdeterministischen) Kellerautomaten. Kellerautomaten funktionieren imGrunde genommen sehr ahnlich wie nichtdeterministische endliche Automaten, aller-dings verfugen sie zusatzlich uber einen (in der Tiefe unbeschrankten) Keller-Speicher,anhand dessen obersten Elements sie ihre Transitionsentscheidungen treffen konnen.Terminierung erfolgt in diesem Fall nicht uber das Erreichen eines Endzustandes, son-dern uber das Erreichen eines leeren Kellers – der automatisch ebenfalls zur Folge hat,dass keine weiteren Transitionen moglich sind. Formal ist ein Kellerautomat wie folgtdefiniert:
Definition 1.18. Ein nichtdeterministischer Kellerautomat ist ein 6-Tupel M = (Z,Σ,Γ, δ, z0,#)wobei
• Z eine endliche Menge von Zustanden ist
• Σ eine endliche Menge von Alphabetssysmbolen (Eingabealphabet) ist
• Γ eine endliche Menge von Kelleralphabetssymbolen ist
• z0 ∈ Z der Startzustand ist
• δ : Z × (Σ ∪ ε)× Γ→ Pe(Z × Γ∗) die Uberfuhrungsfunktion ist
• # ∈ Γ das Kellerbodenzeichen ist.
Pe(X) fur eine Menge X ist die Menge aller endlichen Teilmengen von X – beachte,dass der Keller in seiner Hohe nicht beschrankt ist und daher ohne diese Einschrankungkein endliches Modell garantiert werden kann.
12
Wie ein nichtdeterministischer Automat liest ein Kellerautomat ein Wort w = w1w2...wn
zeichenweise von links nach rechts ein und nimmt Zustandsanderung anhand des Zei-chens und des Kellerinhalts vor. Zusatzlich wird der Kellerinhalt modifiziert: Das obersteZeichen wird beim Lesen vom Stack entfernt und durch eine neue (nicht notwendiger-weise von dem alten Element an der Spitze des Stacks verschiedenen; moglicherweiseleeren) Sequenz von Elementen ersetzt. Auf Grund dessen, dass Ubergange nicht nurdurch Zustand und Alphabetssymbol, sondern auch durch den Kellerinhalt bestimmtwerden, ist die Definition der Sprache eines Kellerautomaten ein wenig komplizierterund bedarf des Begriffs der Konfiguration.
Definition 1.19 (Konfiguration eines Kellerautomaten). Eine Konfiguration eines Kel-lerautomaten ist ein Element k ∈ Z×Σ∗×Γ∗, wobei die erste Komponente den aktuellenZustand bezeichnet, in dem der Kellerautomat sich befindet, die zweite Komponente dennoch zu lesenden Teil des Wortes bezeichnet und die dritte Komponente den aktuel-len Kellerinhalt bezeichnet. Wir kennzeichnen den Ubergang von einer Konfiguration kzu einer Konfiguration k′ gemaß k ` k′. Gegeben eine Konfiguration k = (z, w,Aγ),z ∈ Z, w ∈ Σ∗, A ∈ γ und γ ∈ Γ∗, kann ein Konfigurationsubergang zur Konfigurationk′ = (z′, w′, γ′γ) gemacht werden, i.Z. k ` k′, falls es ein a ∈ Σ ∪ ε gibt, so dass gilt:
• w = aw′
• (z′, γ′) ∈ δ(z, a, A)
Wir schreiben k `∗ k′, wenn k durch mehrmalige (0-fache, einfache, zweifache, ...)Konfigurationsubergange zu k′ ubergehen kann.
Intuitiv kann man diese Definition so lesen: Wenn der Kellerautomat sich im Zustandz befindet und ein Zeichen a liest, sowie das oberste Element auf dem Stack A ist, dannkann der Kellerautomat A durch die Sequenz γ′ ersetzen und muss im Weiteren nochden Rest des Wortes w abarbeiten. Beachte hierbei, dass a = ε moglich ist, dass einKellerautomat also auch einen Ubergang vollziehen kann, ohne ein Alphabetssymbol zulesen.
Mithilfe des Begriffs des Konfigurationsubergangs kann man nun die Sprache einesKellerautomaten definieren.
Definition 1.20 (Sprache eines Kellerautomaten). Gegeben sei ein Kellerautomat M =(Z,Σ,Γ, δ, z0,#). Wir sagen ein Wort w wird von M akzeptiert, wenn es eine Konfigu-rationsfolge gibt, so dass
(z0, w,#) `∗ (z, ε, ε), z ∈ Z.
Die von M akzeptierte Sprache ist also
N(M) = w ∈ Σ∗ | (z0, w,#) `∗ (z, ε, ε), z ∈ Z
Beispiel 1.21. Wir haben bereits gesehen, dass die Sprache der korrekt geklammertenAusdrucke nicht regular ist (vgl. Beispielsaufgabe zum Thema Myhill-Nerode-Aquivalenzklassen.Die Sprache ist allerdings vom Typ 2, wie man einfach mit Hilfe der Grammatik (S,A, (, ), P, S),
13
S → A | ε, A → () | (A) | AA einsehen kann. Wir werden nun einen Kellerautomatenangeben, der ebendiese Sprache akzptiert. Es sei also M = (z0, (, ), a,#, δ, z0,#).Die Uberfuhrungsfunktion ist wie folgt definiert:
δ(z0, (, a) = (z0, aa) δ(z0, (,#) = (z0, a#)
δ(z0, ), a) = (z0, ε) δ(z0, ε,#) = (z0, ε)
Die ubrigen Ubergange δ(z0, ),#) und δ(z0, ε, a) bilden auf die leere Menge ab.Der Automat
”merkt“ sich mit Hilfe des Kellers, wie viele offnende Klammern bislang
gelesen wurden und nicht bereits wieder geschlossen wurden. Ein a auf dem Stack sym-bolisiert jeweils eine offnende Klammer. Ist der Stack mit Ausnahme des Kellerboden-zeichens leer, so bedeutet das, dass jede offnende Klammer auch geschlossen wurde undder Kellerautomat kann nichtdeterministisch den Keller leeren und akzeptieren. Wirdeine schließende Klammer gelesen, fur die es keine korrespondierende offnende Klam-mer gibt, so blockiert der Kellerautomat, wird hingegen eine offnende Klammer nichtvon einer schließenden beantwortet, so kann der Automat niemals seinen Keller leeren.
Auch im Falle der Kellerautomaten gibt es ein deterministisches Modell, das aller-dings, anders als im Fall der endlichen Automaten und auch der (nicht linear bandbe-schrankten) Turingmaschinen nicht aquivalent zum nichtdeterministischen Modell ist:
Definition 1.22. Ein deterministischer Kellerautomat ist ein 7-Tupel M = (Z,Σ,Γ, δ, z0,#, E)wobei
• Z eine endliche Menge von Zustanden ist
• Σ eine endliche Menge von Alphabetssysmbolen (Eingabealphabet) ist
• Γ eine endliche Menge von Kelleralphabetssymbolen ist
• z0 ∈ Z der Startzustand ist
• δ : Z × (Σ ∪ ε)× Γ→ Pe(Z × Γ∗) die Uberfuhrungsfunktion ist
• # ∈ Γ das Kellerbodenzeichen ist
• E ⊆ Z die Menge von Endzustanden ist.
Zusatzlich muss die Uberfuhrungsfunktion deterministisch sein, das heißt sie muss diefolgende Bedingung fur alle z ∈ Z, a ∈ σ, A ∈ Γ erfullen:
|δ(z, a, A)|+ |δ(z, ε, A)| ≤ 1
Konfigurationsubergange sind fur deterministische Kellerautomaten genauso definiertwie fur nichtdeterministische, die Sprache N(M) ist allerdings definiert zu
N(M) = w ∈ Σ∗ | (z0, w,#) `∗ (z, ε,X), z ∈ E,X ∈ Γ∗
14
Ein Wort w wird also von einem deterministischen Kellerautomaten akzeptiert, wenndie (eindeutig definierte) Konfiguration, die nach Einlesen von w erreicht wird, einenEndzustand enthalt, der Kellerinhalt ist unerheblich. Anders als bei deterministischenAutomaten muss bei einem deterministischen Kellerautomaten nicht fur jedes Einga-bezeichen ein Folgezustand definiert sein. Der Grund hierfur ist, dass es moglich seinsoll, den Keller teilweise abzubauen, ohne weitere Zeichen zu lesen. Damit Konfigurati-onsubergange weiterhin eindeutig durch die vorhergehende Konfiguration bestimmt sind,darf es dann aber keine Ubergange mehr geben, die ein Alphabetssymbol lesen. Es gibtalso zwei zwei verschiedene Arten von Paaren (z, A) ∈ Z × Γ:
• Paare (z, A), die genau einen ε-Ubergang haben.
• Paare (z, A), die keinen ε-Ubergang haben und die fur jedes Alphabetsymbol ma-ximal einen Ubergang haben.
Nichtdeterministische Kellerautomaten konnte man alternativ ebenfalls mithilfe vonEndzustanden definieren, ohne das Akzeptanzverhalten zu andern. Gegeben einen nicht-deterministischen Kellerautomaten M der mit leerem Keller akzeptiert sei o.B.d.A dasKellerbodenzeichen stets das untere Symbol auf dem Stack1. Dann kann die Akzeptanzmir leerem Keller simuliert werden, indem ein zusatzlicher Endzustand (ohne ausgehendeKanten) eingefuhrt wird, der immer dann erreicht wird, wenn das Kellerbodenzeichenentfernt wird. Umgekehrt, wenn ein Kellerautomat mit Endzustand akzeptiert, dannkann von diesem Zustand aus ein ε-Ubergang zu einem neuen Zustand z hinzugefugtwerden, von dem aus nur noch ε-Ubergange moglich sind um den gesamten Keller ab-zubauen.
Im Falle deterministischer Kellerautomaten andert sich die Menge der akzeptiertenSprachen allerdings, wenn man statt der Akzeptanz uber Endzustande bei leerem Kel-ler akzeptiert. Deterministische Kellerautomaten, die Worter mit leerem Keller stattmit einem Endzustand akzeptieren, konnen keine Sprache akzeptieren, die zwei Worterenthalt, die in Prafix-Beziehung zueinander stehen: Angenommen, eine Sprache enthaltdie Worter w und ww′ und M sei ein deterministischer Kellerautomat, der uber leerenKeller akzeptiert. Dann gilt (z0, w,#) `∗ (z, ε, ε). Da der Kellerautomat deterministischist, gilt aber auch (z0, ww
′,#) `∗ (z, w′, ε) 6`, also kann der Automat ww′ nicht akzep-tieren. Andersherum konnen deterministische Kellerautomaten mit Endzustanden alleSprachen akzeptieren, die auch durch deterministische Kellerautomaten, die mit leeremKeller akzeptieren, akzeptiert werden konnen, die Argumentation ist vollig analog zunichtdeterministischen Kellerautomaten.
Beispiel 1.23. Wir betrachten abermals die Sprache der korrekt geklammerten Aus-drucke und zeigen durch Angabe eines deterministischen Kellerautomaten, der die Spra-che akzeptiert, dass diese Sprache auch deterministisch kontextfrei ist. Wir definieren
1Anderenfalls wird das Kellerbodenzeichen in einer oder mehreren Regeln des Automaten entfernt unddurch eine neue Sequenz ersetzt. Fur jedes Zeichen A, das am Ende einer solchen Sequenz stehenkann, fuhren wir ein neues Zeichen A ein, das anstatt des letzten A auf den Stack gelegt wird. AlleRegeln, die A auf der linken Seite stehen haben, werden dupliziert und in der Kopie A auf der linkenSeite durch A ersetzt.
15
M = (z0, ze, (, ), a,#, δ, ze,#, ze). Unter Berucksichtigung der Bedingung desNichtdeterminismus ist ein zweiter Zustand notwendig.
δ(z0, (, a) = (z0, aa) δ(z0, ), a) = (z0, ε) δ(z0, ε,#) = (ze,#)
δ(ze, (,#) = (z0, a#) δ(ze, ε,#) = (ze,#)
In allen anderen Fallen, insbesondere allen solchen, bei denen in ze ein a auf dem Stackliegt, bildet die Uberfuhrungsfunktion auf die leere Menge ab.
Der Automat merkt sich, wie der nichtdeterministische Kellerautomat zuvor, auf demStack mittels a-Zeichen, wie viele offnende Klammern bereits gelesen, aber noch nichtbeantwortet wurden. Wannimmer eine offnende Klammer gelesen wird, wird ein a aufden Stack gelegt und in den Zustand z0 ubergegangen, denn das Wort kann nicht miteiner offnenden Klammer enden. Nur in Zustand z0 ist es moglich, eine schließendeKlammer zu lesen. Sobald das Kellerbodenzeichen zu oberst auf dem Keller liegt, mussallerdings zwingend ein Ubergang in den Zustand ze erfolgen.Wird im Zustand z0 eineschließende Klammer eingelesen, ohne, dass ein a auf dem Stack liegt, blockiert derAutomat, ebenso, falls in ze eine schließende Klammer gelesen wird.
Deterministische Kellerautomaten akzeptieren allerdings nicht die gleiche Sprachklas-se wie nichtdeterministische Kellerautomaten. Sie akzeptieren also eine Menge an Spra-chen, die echt großer als die Menge der regularen, aber echt kleiner als die Menge derkontextfreien Sprachen ist.
Beispiel 1.24. Wir betrachten die Sprache L = ww−1 | w ∈ a, b∗, wobei w−1 dieUmkehrung eines Wortes w ist, in Zeichen (aw)−1 = wa−1 und ε−1 = ε. Diese Spra-che ist kontextfrei, sie wird beispielsweise von der folgenden kontextfreien Grammatikerzeugt:
S → ε | aAa | bAb A→ aa | bb | aAa | bAbEin deterministischer Kellerautomat kann L allerdings nicht akzeptieren. Ein formalerBeweis wird an dieser Stelle nicht gefuhrt, intuitiv liegt das allerdings daran, dass es fureine beliebige Eingabe ohne Kenntnis der weiteren Zeichen nicht moglich ist, festzustel-len, an welcher Stelle sich die Mitte des Wortes befindet, wann also begonnen werdenkann, den Keller abzubauen. Genauer lasst sich das wie folgt einsehen:
• Es gibt nur endliche viele Paare (z, A) ∈ Z × Γ.
• Daher gibt es ein n ∈ N, so dass in einem Paar (z, A) ∈ Z×Γ Informationen uberhochstens n verschiedene Zeichen codiert sein konnen.
• Daher kann jeder Ubergang nur von n verschiedenen Zeichen der Eingabe abhangen.
• Die Akzeptanz eines Wortes ww−1 hangt von jedem Zeichen in w ab. Wenn whinreichend lang ist kann – auf Grund der monotonen Beareitungsweise des Kellers– die Entscheidung zum Ubergang zum Endzustand nur getroffen werden, indemder Keller so weit abgebaut wird, dass nur noch zu n < |w| Zeichen Informationenim Keller enthalten sind.
16
• Dann sind aber nicht mehr genugend Informationen im Stack enthalten um zuentscheiden, ob die Fortsetzung w−1w ein Wort in der Sprache ergibt.
Ein nichtdeterministischer Kellerautomat kann bedingt durch die nichtdeterministischeVerzweigung einfach
”raten“, an welcher Stelle die Mitte des Wortes ist und benotigt
in diesem Fall beim Durchlaufen des angenommen w−1 Informationen uber bereits ge-spiegelte Buchstaben nicht mehr. Sollte der nichtdeterministische Kellerautomat
”falsch
geraten“ haben, so ist das kein Problem fur das Akzeptanzverhalten, weil es ausreicht,dass ein einzelner akzeptierender Pfad im Automaten existiert.
Zum Abschluss des Ruckblicks auf Automaten und formale Sprachen werden wir nunnoch kurz skizzieren, wie man nachweisen kann, dass eine Sprache nicht den Typ 2hat. Hierfur verwenden wir das Pumping Lemma fur kontextfreie Sprachen. Das Pum-ping Lemma fur kontextfreie Sprachen stellt eine notwendige Bedingung dar, damit eineSprache von einer kontextfreien Grammatik erzeugt werden kann, es ist aber kein not-wendiges Krierium. Das bedeutet, dass eine Sprache, die die Bedingung des PumpingLemmas nicht erfullt, nicht kontextfrei sein kann, andersherum ist es aber nicht moglich,aus dem Umstand, dass die Bedingungen des Pumping Lemmas erfullt sind, zu schließen,dass die Sprache kontextfrei ist.
Das Pumping-Lemma fur kontextfreie Sprachen
Um das Pumping-Lemma fur kontextfreie Sprachen aufstellen zu konnen, stellen wirzunachst fest dass ohne Beschrankung der Allgemeinheit die Grammatikregeln fur Typ2-Grammatiken auf die zwei Formen A → a und A → BC, A,B,C ∈ V , a ∈ Σeingeschrankt werden konnen. Regeln mit mehr Zeichen auf der rechten Seite konnendurch Hilfsvariablen, die sich ihrerseits in zwei Variablen ableiten lassen, ersetzen undzusatzliche Alpabetsymbole konnen mittels weiterer Hilfsvariablen, die unmittelbar zumjeweiligen Alphabetsymbol abgeleitet werden konnen, ersetzt werden. Diese spezielleForm kontextfreier Grammatiken wird auch die Chomsky Normalform genannt. JedeAbleitung eines Wortes vom Startsymbol S lasst sich dann als Binarbaum mit WurzelS darstellen, die Alphabetsymbole tauchen in diesem Baum (ausschließlich) als Blatterauf.
Sei ein Binarbaum gegeben, der n Blatter hat, so muss die Tiefe – das heißt die Langedes langsten gerichteten Pfades von der Wurzel zu einem Blatt – mindestens log2(n) be-tragen. Der Grund hierfur ist, dass auf jeder Ebene jeder Knoten maximal zwei Kinderhaben kann, eine Ebene mit k Knoten kann also maximal 2 · k Nachfolgerknoten besit-zen. Also gilt: Ein Binarbaum der Tiefe t hat maximal 2t−1 Blatter2. Bezogen auf dieFeststellung, dass jede Ableitung eines Wortes einer Typ 2 Grammatik G = (V,Σ, P, S)(in CNF) einem Binarbaum entspricht, konnen wir beobachten: Wenn ein Wort von
2Induktiv: Die Aussage stimmt fur t = 1, in dem Fall gibt es nur ein Blatt, namlich den Wurzelknoten.Ein Baum der Tiefe t habe nun gemaß Induktionsannahme maximal 2t−1 Blatter, dann kann, wennman den Baum um eine Ebene fortsetzt, also einen Baum der Tiefe t+1, bildet, jeder dieser Knotenmaximal zwei Nachfolger haben, die dann im neuen Baum die Blatter bilden. 2 · 2t−1 = 2t, womitder Induktionsschluss gefuhrt ware
17
mehr als 2|V | Zeichen enthalt, so hat der zugehorige Ableitungsbaum mindestens dieTiefe |V | + 1. Das Taubenschlag- oder Schubfachprinzip liefert demnach, dass mindes-tens eine Variable A auf dem Pfad doppelt vorgekommen sein muss. Es lassen sich dannalso weitere Worter der Grammatik erzeugen, indem man den Teilbaum, der beim zwei-ten Vorkommen von A beginnt, direkt an das erste Vorkommen von A anhangt, oderaber, indem man die Ableitungsschritte, die vom ersten zum zweiten Vorkommen von Agefuhrt haben, mehrfach durchfuhrt. Die so erzeugten Worter haben die Form uviwxiy,wobei u den Teil des Wortes reprasentiert, der von Variablen weiter links auf der Ebenedes ersten As erzeugt wird und analog y den Teil des Wortes reprasentiert, der von denVariablen rechts von A auf der gleichen Ebene erzeugt wird. Somit ist vwx derjenigeTeil des Wortes, der von dem ersten Vorkommen von A erzeugt wird. Hierbei bezeichnetw denjenigen Teil des Wortes, der vom zweiten Vorkommen von A erzeugt wird und vsowie w diejenigen Teile des Wortes, die von Variablen links und rechts auf der gleichenEbene wie das zweite A im Teilbaum des ersten As erzeugt werden. v und w konnennicht beide leer sein, da das erste Vorkommen von A – dank der CNF – zwei Nachfolge-knoten besitzen muss, die wiederum Wurzel eines Teilbaums sind, der jeweils mindestenseinen Knoten und somit auch mindestens ein Blatt enthalt. Wir konnen also die folgendeAussage festhalten:
Satz 1.25. Es sei L eine kontextfreie Sprache. Dann gibt es eine Zahl n ∈ N, so dasssich alle Worter z ∈ L, die mindestens die Lange n haben, also |z| ≥ n, zerlegen lassenin Teilworter z = uvwxy, wobei
• |vx| ≥ 1, v und x konnen nicht beide leer sein.
• Fur alle i = 0, 1, 2... gilt: uviwxiy ∈ L.
In diesem Satz konnte man zusatzlich (zur einfacheren Anwendung) fordern, dass|vwx| ≤ n, indem man einfach im obigen Argument die von unten an betrachtet ersteDopplung Variable auf einem Pfad von dem Blatt zur Wurzel wahlt.Die Bedingung |vx| ≥ 1 wird an der visuellen Aufteilung des Wortes z in funf Teilworteru, v, w, x, y klarer:
• w wird aus dem unteren A abgeleitet: A⇒∗ w
• vwx wird aus dem oberen A abgeleitet: A⇒∗ vwx
18
u v w x y
S
A
A
Entweder ist mindestens |v| ≥ 1 oder |x| ≥ 1. Sofern z.B. das zweite Aufkommen vonA aus dem rechten Ableitungsschritt A → BC des ersten A′s stammt, sodass |x| = 0,muss zumindest der Linke Teil in mindestens einem Terminsalzeichen enden.
Den Satz 1.25 kann man zum Beweis dessen, dass eine Sprache nicht kontextfrei ist,heranziehen. Wenn man zeigt, dass zu einer Sprache L kein n existiert, so dass die zweiBedingungen des obigen Satzes erfullt sind, dann kann die Sprache nicht kontextfreisein. Ist umgekehrt gezeigt, dass es ein solches n gibt, so muss die Sprache aber nichtnotwendigerweise kontextfrei sein. Also indem wir die Aussage negieren: Also, wenn
• Fur alle Zahlen n ∈ N0
• ein Wort z ∈ L existiert, so dass
• fur alle Zerlegungen z = uvwxy mit |vx| ≥ 1, |vwx| ≤ n
• ein i ∈ N0 exitiert, so dass uviwxiy /∈ L
dann ist L nicht kontextfrei.Anmerkung: Wie auch beim Pumping-Lemma fur regulare Sprachen gilt die Implikationnur in die angegebene Richtung, wenn die Pumping-Eigenschaft fur eine Sprache L erfulltist, muss L nicht zwingend kontextfrei sein.
19
2 Berechnungsmodelle
Turingmaschinen
Das vorrangige Berechnungsmodell, das wir in Berechenbarkeit und Komplexitat verwen-den, ist die Turingmaschine. Konzeptuell ist eine Turingmaschien ein Automat, der aufeinem unendlichen Band operiert. In jedem Berechnungsschritt liest die Turingmaschineein Zeichen auf dem Band, modifiziert dieses Zeichen und wechselt abhangig von demaktuellen Zustand und dem gelesenen Zeichen den Zustand. Anschließend bewegt dieTuringmaschine ihren Lese- / Schreibekopf auf dem Band nach links, nach rechts, oderbleibt an der gleichen Stelle stehen. Formal sind Turingmaschinen wie folgt definiert,wir betrachten sowohl die Definition einer deterministischen, als auch einer nichtdeter-ministischen Turingmaschine:
Definition 2.1. Eine Turingmaschine mit k Bandern ist ein 7-Tupel
M = (Z,Σ,Γ, δ, z0,, E)
wobei
• Z die endliche Menge der Zustande
• Σ eine endliche Menge, genannt das Eingabealphabet
• Γ ⊃ Σ eine endliche Menge, genannt das Bandalphabet
• z0 ∈ Z der Startzustand
• ∈ Γ \ Σ das Leerzeichen
• E ⊆ Z die Menge der Endzustande ist.
Falls M deterministisch ist, so hat δ die Form δ : Z × Γ → Z × Γ × L,R,N, ist Mnichtdeterministisch, so hat δ die Form δ : Z × Γ→ P(Z × Γ× L,R,N).
Beide Maschinenmodelle sind, ahnlich wie im Fall der endlichen Automaten aquivalentin Hinblick auf ihre Berechnungsfahigkeiten. Wir werden zunachst die Konfigurationenund Konfigurationsubergange einer Turingmaschine definieren, um anschließend die ak-zeptierte Sprache und die berechnete Funktion einer Turingmaschine angeben zu konnen.
Definition 2.2. Es sei M = (Z,Σ,Γ, δ, z0,, E) eine Turingmaschine, dann ist eineKonfiguration von M eine Sequenz
a1a2...anzb1b2...bm
wobei a1, ..., an, b1, ...bm ∈ Γ und z ∈ Z. Zur Definition von Konfigurationsubergangen be-darf es einer Fallunterscheidung (wir definieren hier Konfigurationsubergange fur nicht-deterministische Turingmaschinen, im Falle deterministischer Turingmaschinen ist beider Unterscheidung der Uberfuhrungsfunktion stets ein = statt eines ∈ zu setzen, an-sonsten ist die Definition analog):
20
1. Falls es einen Ubergang (z′, b, R) ∈ δ(z, a) gibt, so gilt a1a2...anzab1b2...bm `a1a2...anbz
′b1b2...bm.
2. Falls es einen Ubergang (z′, b, L) ∈ δ(z, a) gibt, so gilt a1a2...anzab1b2...bm ` a1a2...z′anbb1b2...bm.Fur den Fall n = 0 gilt zab1b2...bm ` z′bb1b2...bm.
3. Falls es einen Ubergang (z′, b, N) ∈ δ(z, a) gibt, so gilt a1a2...anzab1b2...bm `a1a2...anz
′bb1b2...bm.
In dem Sonderfall, dass m = 0 ist zunachst ein am Ende der Konfiguration zuerganzen.
Wie ublich schreiben wir k1 `∗ k2 falls ein Ubergang von Konfiguration k1 zu Konfi-guration k2 in beliebig vielen Konfigurationsubergangen moglich ist.
Definition 2.3. Es sei M = (Z,Σ,Γ, δ, z0,, E) eine Turingmaschine
• Die von M akzeptierte Sprache ist die Menge
T (M) = x ∈ Σ∗ | z0f `∗ αzβ, α, β ∈ Γ∗, z ∈ E
Wichtig ist, dass bei einer nichtdeterministischen Turingmaschine nur eine Ubergangsfolgeexistieren muss, die einen Endzustand erreicht, es muss nicht jede Ubergangsfolgeden Endzustand erreichen.
• Wenn M deterministisch ist, sagen wir M berechnet eine Funktion f : Σ∗ → Σ∗
falls z0x `∗ zf(x) mit z ∈ E. Eine analoge Definition fur nichtdeterministischeTuringmaschinen muss in diesem Fall verlangen, dass jede Konfigurationsfolge, diein den Endzustand gelangt, die selbe Endkonfiguration ergibt, anderenfalls ware dievon der Turingmaschine berechnete Funktion nicht wohldefiniert.
Es ist moglich zu zeigen, dass deterministische Turingmaschinen und nichtdeterminis-tische Turingmaschinen gleich machtig sind, allerdings ist dieser Beweis außerst tech-nisch, weswegen wir im Folgenden nur eine Skizze des Beweises angeben.
Satz 2.4. Jede durch eine nichtdeterministische Turingmaschine akzeptierte Sprachewird auch von einer deterministischen Turingmaschine akzeptiert.
Beweisskizze: Gegeben sei eine nichtdeterministische TuringmaschineM = (Z,Σ,Γ, δ, z0,, E).Wir wollen eine deterministische Turingmaschine M ′ angeben, die die gleiche Sprache Lakzeptiert wie M . Wir verwenden hierzu eine Breitensuche uber die moglichen Konfigu-rationsfolgen. Es sei n = max|δ(z, a)| | z ∈ Z, a ∈ A. Eine deterministische Turingma-schine, die L akzeptiert, konnte sich das Band beispielsweise wie folgt einteilen:
w#s#s′#k
Dabei ist w die Eingabe, s ⊆ 0, 1, ..., n − 1∗ der Entscheidungsstring, s′ w s einSuffix von s und k die aktuelle Konfiguration der simulierten Turingmaschine M . DieTuringmaschine operiert nun wie folgt:
21
• Zu Beginn stellt die Turingmaschine den Bandzustand w#0#0#z0w her.
• Falls die aktuelle Konfiguration die Form w#s#ε#k hat, so interpretiere s als |s|-stellige n−1-nare Zahl und addiere 1 auf die Zahl, setze s′ = s und k = z0w. Hierzubenotigt es einer Reihe von Zustanden, die der Kopie von w und s dienen. Da dieZahl der moglichen Zeichen auf jeder Stelle endlich ist, reichen hierzu allerdingsendlich viele Zustande.
• Falls die aktuelle Konfiguration die Form w#s#is′#k und in k i oder mehr Ent-scheidungsmoglichkeiten fur die Nachfolgekonfiguration existieren, wahle die i-teNachfolgekonfiguration. Wird hierbei in der simulierten Konfiguration ein End-zustand erreicht, gehe in den Endzustand der deterministischen Maschine uber.Ansonsten ersetze is′ durch s′.
• Falls die aktuelle Konfiguration die Form w#s#is′#k und in k weniger als i Ent-scheidungsmoglichkeiten fur die Nachfolgekonfiguration existieren, ersetze is′ durchε.
Jede dieser Operationen benotigt eine verhaltnismaßig hohe, aber endliche Zahl vonZustanden, um die notwendigen Verschiebe- und Kopieroperationen durchzufuhren. Zen-tral ist, dass jede Konfigurationsfolge, die die nichtdeterministische Turingmaschine aufder gegebenen Eingabe vollziehen kann, irgendwann simuliert wird, daher ist es not-wendig, diese Konstruktion in Form einer Breitensuche unter den Konfigurationsfolgenumzusetzen.
Mehrband-Turingmaschinen
In der Vorlesung haben wir gesehen, dass neben den einfachen deterministischen undnichtdeterministischen Turingmaschinen ein weiteres Maschinenmodell fur semientscheid-bare Sprachen existiert, dass zu deterministischen und nichtdeterministischen Turingma-schinen aquivalent ist: Die Mehrband-Turingmaschinen. Wir mochten im Folgenden nocheinmal die Definition rekapitulieren und ein Beispiel fur eine Mehrband-Turingmaschineangeben.
Definition 2.5. Eine Mehrband-Turingmaschine mit k Bandern ist ein 7-Tupel
M = (Z,Σ,Γ, δ, z0,, E)
wobei
• Z die endliche Menge der Zustande
• Σ eine endliche Menge, genannt das Eingabealphabet
• Γ ⊃ Σ eine endliche Menge, genannt das Bandalphabet
• z0 ∈ Z der Startzustand
22
• ∈ Γ \ Σ das Leerzeichen
• E ⊆ Z die Menge der Endzustande ist.
Falls M deterministisch ist, so hat δ die Form δ : Z × Γk → Z × Γk × L,R,Nk, istM nichtdeterministisch, so hat δ die Form δ : Z × Γk → P(Z × Γk × L,R,Nk).
Intuitiv bedeutet das, dass eine Mehrband-Turingmaschine bei jedem Ubergang dasaktuelle Zeichen auf jedem ihrer k Bander ausliest, hiervon abhangig in einen Nachfol-gezustand wechselt und dabei auf jedem Band das gelesene Zeichen ersetzt und in einenpassenden Nachfolgezustand wechselt.
Wir betrachten im Folgenden ein Beispiel fur eine Zwei-Band-Turingmaschine.
Beispiel 2.6. Es sei
M = (z0, za, zbze, 0, 1, 0, 1,, δ, z0,, ze)
und wir definieren δ : Z × Γ2 → Z × Γ2 × L,R,N2 gemaß
δ(z0,, 0) = (z0,, 0, N,N) δ(z0,, 1) = (z0,, 1, N,N) δ(z0,,) = (ze,,, N,N)δ(z0, 0, 0) = (z0, 0, 0, N,N) δ(z0, 0, 1) = (z0, 0, 1, N,N) δ(z0, 0,) = (za, 0, 0, R,R)δ(z0, 1, 0) = (z0, 1, 0, N,N) δ(z1, 0, 1) = (z0, 1, 1, N,N) δ(z0, 1,) = (zb, 1, 1, R,R)δ(za,, 0) = (za,, 0, N,N) δ(za,, 1) = (za,, 1, N,N) δ(za,,) = (z0,, 0, N,R)δ(za, 0, 0) = (za, 0, 0, N,N) δ(za, 0, 1) = (za, 0, 1, N,N) δ(za, 0,) = (z0, 0, 0, N,R)δ(za, 1, 0) = (za, 1, 0, N,N) δ(za, 1, 1) = (za, 1, 1, N,N) δ(za, 1,) = (z0, 1, 0, N,R)δ(zb,, 0) = (zb,, 0, N,N) δ(zb,, 1) = (zb,, 1, N,N) δ(zb,,) = (z0,, 1, N,R)δ(zb, 0, 0) = (zb, 0, 0, N,N) δ(zb, 0, 1) = (zb, 0, 1, N,N) δ(zb, 0,) = (z0, 0, 1, N,R)δ(zb, 1, 0) = (zb, 1, 0, N,N) δ(zb, 0, 1) = (zb, 1, 1, N,N) δ(zb, 1,) = (z0, 1, 1, N,R)
und δ(ze, x, y) = (ze, x, y,N,N) fur alle x, y ∈ Γ. Die Turingmaschine kopiert das Wortauf dem Eingabeband auf das zweite Band und verdoppelt dabei jedes Zeichen, aus ababwird also beispielsweise aabbaabb auf dem zweiten Band.
Anhand des Beispiels kann man ebenfalls ersehen, wieso man Mehrband-Turingmaschinenuberhaupt verwenden sollte, wenn sie doch aquivalent zu Einband-Turingmaschinen sind:Die Aufgabe, jedes Zeichen einer Eingabe zu verdoppeln ist in einer klassischen Turing-maschine bedeutend schwieriger umzusetzen. Das gleiche gilt fur viele andere Aufgaben,bei denen die Eingabe vergroßert werden soll oder bei der wiederholt auf die Eingabezugegriffen werden soll.
LOOP-Programme
Wir haben in der Vorlesung die LOOP-Programme kennen gelernt. Syntaktisch bestehenLOOP-Programme aus den folgenden Komponenten:
• Variablen: x0 x1 x2...
23
• Konstanten: 0 1 2...
• Trennsymbole: ; :=
• Operatorsymbole: + −
• Schlusselworter: LOOP DO END
Ein LOOP-Programm hat (induktiv) die Form:
• Wertzuweisung: xi := xj + c oder xi := xj − c
• Sequentielle Komposition: P1;P2, dabei sind P1 und P2 LOOP-Programme
• LOOP: LOOP xi DO P END, dabei ist P ein LOOP-Programm
Die Besonderheiten der Semantik sind:
• xi := xj − c ist die modifizierte Subtraktion, wenn also c > xj, so hat xi nach derOperation den Wert 0, anderenfalls den Wert xj − c im klassischen Sinne.
• LOOP xi DO P END nimmt den Wert n von xi bei Erreichen des Befehls undfuhrt dann P exakt n-Mal aus. Der Wert von xi wird durch die LOOP-Schleifenicht verandert, außer es gibt eine Zuweisung an xi in dem Schleifenkorper P . Einesolche Veranderung des Wertes von xi verandert aber nicht die Zahl der Durchlaufedurch P . Dadurch ist sichergestellt, dass jedes LOOP-Programm terminiert.
Wir wollen nun ein Beispiel fur ein LOOP-Programm angeben, das die Modulo-Funktionberechnet. Hierzu benotigen wir zwei Makros, die wir anschließend in weiteren LOOP-Programmen wie neue Befehle verwenden konnen.
Makro fur x := x− y:
LOOP y DO
x := x− 1;
END
Makro fur IF x ≥ y THEN P END:Es seien x1, x2 frische Variablen.
x1 := x+ 1;
x1 := x1 − y;
x2 := 0;
LOOP x1 DO
x2 := 1;
END
LOOP x2 DO
P
END
24
Programm fur x1 MOD x2:
x0 := x1;
LOOP x1 DO
IF x0 ≥ x2 THEN
x0 := x0 − x2;END
END
Primitiv rekursive und µ-rekursive Funktionen
Wir betrachten zwei Formen der Rekursion, die primitive Rekursion und die µ-Rekursion.Wir definieren zunachst, was primitiv rekursive Funktionen sind:
Definition 2.7. • Alle konstanten Funktionen der Form c : N0 → N0 mit c(n) = m(fur ein festes m ∈ N0) sind primitiv rekursiv.
(Auch 0-stellige konstante Funktionen sind zugelassen.)
• Alle Projektionen der Form πki : Nk
0 → N0 mit πki (n1, . . . , nk) = ni sind primitiv
rekursiv.
• Die Nachfolgerfunktion s : N0 → N0 mit s(n) = n+ 1 ist primitiv rekursiv.
• Jede Funktion, die durch Einsetzung/Komposition von primitiv rekursiven Funk-tionen entsteht, ist primitiv rekursiv.
• Jede Funktion f , die durch primitive Rekursion aus primitiv rekursiven Funktionenentsteht, ist primitiv rekursiv.
Das heißt f : Nk+10 → N0 muss folgende Gleichungen erfullen (fur primitiv rekursive
Funktionen g : Nk0 → N0, h : Nk+2
0 → N0):
f(0, n1, . . . , nk) = g(n1, . . . , nk)
f(n+ 1, n1, . . . , nk) = h(f(n, n1, . . . , nk), n, n1, . . . , nk)
µ-rekursive Funktionen werden nun aufbauend auf den primitiv rekursiven Funktionenwie folgt definiert:
Definition 2.8. µ-rekursive Funktionen konnen wiederum rekursiv wie folgt definiertwerden:
• Jede primitiv rekursive Funktion ist µ-rekursiv
25
• Sei f : Nk+10 → N0 eine µ-rekursive Funktion, dann ist auch die partielle Funk-
tion µf : Nk0 → N0. Dabei ist der µ-Operator wie folgt definiert: Der µ-Operator
verwandelt eine Funktion f : Nk+10 → N0 in eine Funktion µf : Nk
0 → N0 mit
µf(x1, . . . , xk) = minn | f(n, x1, . . . , xk) = 0
und fur alle m < n ist f(m,x1, . . . , xk)
definiert
Dabei gilt min ∅ = undefiniert.
Die primitiv rekursiven Funktionen sind exakt die LOOP-berechenbaren Funktionen,die µ-rekursiven Funktionen sind exakt die Turing-berechenbaren.
Wir betrachten nun einige Beispiele fur primitiv rekursive und µ-rekursive Funktionen:
Beispiel 2.9. • Die Funktion add : N20 → N0 mit add(n,m) = n + m ist primitiv
rekursiv.
add(0,m) = m
add(n+ 1,m) = s(add(n,m))
Fur das Rekursionsschema gilt: g = π11 : N0 → N0, h = s π3
1 : N30 → N0
• Die Funktion mult : N20 → N0 mit mult(n,m) = n ·m ist primitiv rekursiv.
mult(0,m) = 0
mult(n+ 1,m) = add(mult(n,m),m)
Hier gilt: g ist die (einstellige) konstante Nullfunktion und h : N30 → N0 ist definiert
als h(x, n,m) = add(π31(x, n,m), . . . , π3
3(x, n,m)).
• Die Funktion dec : N0 → N0 mit dec(n) = n − 1 (modifizierte Subtraktion) istprimitiv rekursiv.
dec(0) = 0
dec(n+ 1) = n
Hier gilt: g ist die (nullstellige) konstante Nullfunktion und h = π22 : N2
0 → N0.
• Die Funktion binom2: N0 → N0 mit binom2(n) =(n2
)ist primitiv rekursiv.
binom2(0) = 0
binom2(n+ 1) = add(binom2(n), n)
26
• Die Funktion max : N20 → N0 mit max (n,m) =
n falls n ≥ m
m sonstist primitiv
rekursiv.
max (n,m) = add(sub(n,m),m)
In diesem Fall reicht es also, bekannte primitiv rekursive Funktionen ineinandereinzusetzen. Dass die modifizierte Subtraktion primitiv rekursiv ist, wird in denUbungen gezeigt.
• Die Funktion Ω: N0 → N0 mit Ω(n) = undefiniert fur alle n ∈ N0 ist µ-rekursiv.
Verwende die 2-stellige Funktion f : N20 → N0 mit f(x, y) = 1 fur alle x, y. Es gilt
f = k π21, wobei k die konstante 1-stellige Funktion ist, die alles auf 1 abbildet.
Dann gilt Ω = µf .
• Die Funktion sqrt : N0 → N0 mit sqrt(n) = d√ne ist µ-rekursiv.
(Dabei rundet d. . . e eine reelle Zahl auf die nachstgroßere (oder gleiche) ganzeZahl auf.)
Sei f(m,n) = n−m ·m. (Die Multiplikationsfunktion ist primitiv rekursiv und dieSubtraktionsfunktion kann durch iterierte Anwendung der Dekrementierungsfunk-tion erhalten werden.)
Eine Beispielsaufgabe
In dieser Aufgabe durfen Sie davon ausgehen, dass die modifizierte Subtraktion primitivrekursiv ist (vgl. Ubungsaufgabe). Zeigen Sie
1. die Fakultatsfunktion ist primitiv rekursiv.
2. die Funktion f(n) =
1 falls n gerade
0 sonstprimitiv rekursiv ist
3. die Funktion g(x) = bx2c primitiv rekursiv ist.
4. die Funktion d(x, y) = dxye µ-rekursiv ist.
5. die Divisionfunktion div(x, y) = bxyc µ-rekursiv ist.
27
Losungsskizze
1. 0! = 1, n! = (n − 1)! · n, also definiere fak(0) = 1 (konstante Funktion) undfak(n+ 1) = mult(fak(n), s(n)) (Multiplikation ist primitiv rekursiv, Nachfolger-funktion ist primitiv rekursiv, Einsetzen von primitiv rekursiven Funktionen inprimitv rekursive Funktionen ergibt primitiv rekursive Funktionen)
2. Wir definieren f(0) = 0, f(n + 1) = 1 − f(n) = sub(1, π21(f(n), n)), hier haben
wir Einsetzung, die primitive Rekursivitat der modifizierten Subtraktion und derkonstanten 1-Funktion verwendet.
3. Wir definieren g(0) = 0 und g(n) = g(n) + f(n) = add(g(n), f(n))
4. Die Funktion h(z, x, y) = x − z · y is primitiv rekursiv, denn sie entsteht durchEinsetzen von sub und mult, von denen wir bereits wissen, dass sie primitiv rekursivsind: h(z, x, y) = sub(π3
2(z, x, y),mult(π31(z, x, y), π3
3(z, x, y)))
Nun gilt, unter Beachtung der modifizierten Subtraktion:
µh(x, y) = minz | x− z · y = 0 = minz | x ≤ z · y =
⌈x
y
⌉5. Es gilt ⌊
x
y
⌋=
⌈x
y+
1
y
⌉− 1 =
⌈x+ y − 1
y
⌉also gilt
div(x, y) = d(x+ y − 1, y) = d(add(π21(x, y), add(π2
2(x, y), 1)), π22(x, y))
Diagonalisierung
Wir betrachten nun das Beweisverfahren der Diagonalisierung. Dafur mussen wir zunachstdefinieren, was der Begriff der
”Abzahlbarkeit“ ist.
Definition 2.10. Es sei M eine beliebige Menge. Dann nennen wir M abzahlbar genaudann, wenn es eine surjektive Funktion f : N→M gibt.
Es folgt unmittelbar, dass jede endliche Menge, die naturlichen Zahlen und jede Teil-menge der naturlichen Zahlen abzahlbar ist. Wir werden nun zwei weniger offensichtlicheBeispiele betrachten:
Beispiel 2.11. • Die Menge der naturlichen Zahlen N0 ist abzahlbar, wie man vermogeder Funktion f : N → N0 mit f(x) = x − 1 einsehen kann. Fur jede Zahl x ∈ N0
existiert die Zahl x+ 1 ∈ N und f(x+ 1) = x+ 1− 1 = x. Also ist f surjektiv.
• Die Menge der ganzen Zahlen Z ist abzahlbar. Wir konnen das einsehen, indemwir die Aufzahlungsfunktion f : N → Z mit f(x) = (−1)xdx
2e betrachten. Es
gilt beispielsweise f(5) = (−1)5d52e = −1 · d2, 5e = −3 und f(8) = (−1)8d8
2e =
1 · d4e = 4. Wir zeigen nun, dass die Funktion tatsachlich surjektiv ist. Sei hierzuein beliebiges y ∈ Z gegeben.
28
– Falls y = 0, so ist y das Bild von x = 0, denn f(0) = (−1)0d02e = 1 · 0 = 0.
– Falls y > 0, so ist y das Bild von x = 2 · y, denn f(2 · y) = (−1)2·yd2·y2e =
1 · dye = y.
– Falls y < 0, so ist y das Bild von x = 2 · |y| − 1, denn f(2 · |y| − 1) =
(−1)2·|y|−1d2·|y|−12e = (−1) · d|y| − 1
2e = (−1) · |y| = y.
Ein wesentlich komplexeres Beispiel sind die positiven rationalen Zahlen Q+. Um zuzeigen, dass Q+ abzahlbar ist, verwendet man ein Diagonal-Argument:
Satz 2.12. Die Menge der positiven rationalen Zahlen Q+ ist abzahlbar.
Beweis. Das lasst sich auf eine komplizierte und eine einfache Weise zeigen. Beginnenwir mit der komplizierten: Wir definieren die Funktionen g : N → N und h : N → Nrekursiv wie folgt:
g(1) = 1 h(1) = 1
g(n+ 1) =
g(n) + 1 falls h(n) > 1
1 sonsth(n+ 1) =
h(n)− 1 falls h(n) > 1
g(n) + h(n) sonst
Wir behaupten, dass die Funktion f : N→ Q+ mit f(x) = g(x)h(x)
surjektiv ist.
Wir zeigen zunachst: fur jedes n ∈ N\1 gibt es ein m ∈ N so dass g(m) +h(m) = nund g(m) = 1.
Induktionsanfang (n = 2): Wir wahlen m = 1, dann ist nach Definition g(1) + h(1) =1 + 1 = 2 und g(1) = 1.
Induktionsvoraussetzung :Fur jedes k < n gibt es ein m ∈ N so dass g(m) + h(m) = kund g(m) = 1.
Induktionsschritt : Es gibt ein m ∈ N so dass g(m)+h(m) > n und g(m) = 1. Dann isth(m) = n−1 und demnach h(m+1) = n−2, h(m+2) = n−3... h(m+(n−2)) = n−1−n+2 = 1, also ist h(m+(n−1)) = h(m+(n−2))+g(m+(n−2)) = ... = h(m)+g(m) = nund g(m+ (n− 1)) = 1, wie behauptet.
Sei nun ein beliebiges pq∈ Q+ gegeben, gibt es einm ∈ N so dass g(m)+h(m) = p+q−1
und g(m) = 1. Dann ist g(m+p−1) = g(m+p−2)+1 = ... = g(m)+p−1 = 1+p−1 = pund h(m+ p− 1) = h(m+ p− 2)− 1 = ... = h(m)− (p− 1) = p+ q − 1− (p− 1) = q.
Also ist f(m+ p− 1) = g(m+p−1)h(m+p−1) = p
q. Da alle positiven rationalen Zahlen sich als Bruch
pq
schreiben lassen, folgt, dass f surjektiv und somit Q+ abzahlbar ist.Dieser Beweis ist allerdings recht kompliziert. Anschaulicher, aber inhaltlich aquivalent
kann man sich vorstellen, dass man die Bruchzahlen in einer (unendlichen) Tabelle ein-tragt:
29
1 2 3 4 5 6 ...1 1
112
13
14
15
16
...2 2
122
23
24
25
26
...3 3
132
33
34
35
36
...4 4
142
43
44
45
46
...5 5
152
53
54
55
56
...6 6
162
63
64
65
66
......
......
......
......
. . .
Diese Tabelle enthalt notwendigerweise alle positiven rationalen Zahlen, da jede positiverationale Zahl sich als Bruch naturlicher Zahlen darstellen lasst. Wenn man nun die Ta-belle nach dem folgenden Schema durchlauft: (1, 1), (1, 2), (2, 1), (3, 1), (2, 2), (1, 3), (1, 4), (2, 4), ...,so wird man jedes Element der Tabelle mindestens ein Mal treffen und somit ist auf dieseWeise eine Aufzahlung aller positiver rationaler Zahlen definiert.
Eine Beispielsaufgabe
Zeigen Sie
1. Die Menge der positiven rationalen Zahlen mit 0, Q+ ∪ 0 ist abzahlbar.
2. Die Menge der rationalen Zahlen Q ist abzahlbar.
Losungsskizze
1. Die Menge der nicht-negativen rationalen Zahlen Q+ ∪0 ist abzahlbar, wie manvermoge der Funktion f : Q+ → Q+∪0 mit f(x) = x−1 einsehen kann. Fur jedeZahl x ∈ Q+∪0 existiert die Zahl x+1 ∈ Q+ und f(x+1) = x+1−1 = x. Alsoist f surjektiv. Die Verknupfung der Funktion aus dem Beweis, dass Q+ abzahlbarist und f ergibt die Abzahbarkeit von Q+ ∪ 0.
2. Die Menge der rationalen Zahlen Q ist abzahlbar. Wir konnen das einsehen, in-dem wir die Aufzahlungsfunktion f aus Teil 1 verwenden und auf dieser Basis dieFunktion g : N0 → Q definieren gemaß g(x) = (−1)x · dx
2e.
Motiviert durch diesen Beweis, dass Q+ abzahlbar ist, konnen wir umgekehrt einBeweisprinzip definieren um zu zeigen, dass eine Menge M uberabzahlbar ist. Wir ver-wenden dazu die folgenden Schritte:
1. Wir setzen voraus, dass es fur Elemente in m ∈M eine unendlich lange Darstellungm1m2m3... gibt. Das kann beispielsweise die Dezimaldarstellung einer Zahl oderdie Funktionswerte einer Funktion sein.
2. Nimm an M sei abzahlbar.
3. Dann gibt es eine surjektive Funktion f : N→M .
30
4. Wir konnen demnach eine Tabelle erstellen, in der an erster Stelle f(1), an zweiterStelle f(2)... an i-ter Stelle f(i) steht.
5. In der i-ten Spalte stehen dann die Elemente f(1)(i), f(2)(i), ... f(j)(i)....
6. Wir betrachten nun die Diagonale dieser Tabelle, f(1)(1)f(2)(2)...f(n)(n)....
7. Wir verandern nun jedes Element f(i)(i), so dass wir ein Element m′i erhalten, sodass m′i 6= f(i)(i).
8. Wir zeigen dann, dass m′1m′2... ∈M
9. Gelingt dies, so entsteht ein Widerspruch wie folgt: Da m′1m′2... ∈ M , muss es
einen Index n ∈ N geben, so dass f(n) = m′1m′2.... Dann steht m′1m
′2... also in der
n-ten Zeile der Tabelle. Demnach ist f(n)(n) = m′n. Allerdings ist per Definitionm′n 6= f(n)(n). Also entsteht ein Widerspruch und eine Aufzahlungsfunktion f :N→M kann nicht existieren.
Das Diagonalisierungsverfahren ist ein Beweis durch Widerspruch und daher nicht injedem Axiomensystem zulassig. Das Axiom des ausgeschlossenen Dritten, das besagtdass fur jede logische Aussage P die Aussage P ∨ ¬P gultig ist, muss angenommenwerden, damit das Beweisverfahren korrekt ist. In der konstruktivistischen Mathematikist ein Beweis per Widerspruch – und somit auch ein Diagonalisierungsbeweis – nichtzulassig. Dies ist allerdings nur ein Einwurf, im Kontext der Vorlesung Berechenbarkeitund Komplexitat kann das Axiom des ausgeschlossenen Dritten als gegeben angenommenwerden.
Beispiel 2.13. Als Beispiel zum Diagonalisierungsbeweis fuhren wir (erneut) den Be-weis durch, dass die Menge M der totalen Funktionen f : N → N nicht abzahlbar ist.Wir folgen dazu genau dem obigen Schema:
1. Wir stellen eine Funktion f ∈ M als Sequenz der Funktionswerte f(1)f(2)f(3)...dar.
2. Wir nehmen an, es gabe nur abzahlbar viele totale Funktionen, M sei also abzahlbar.
3. Dann gibt es eine surjektive Funktion F : N→M .
4. Wir konnen demnach eine Tabelle erstellen, in der an erster Stelle F (1), an zweiterStelle F (2)... an i-ter Stelle F (i) steht. Es steht also in der ersten Zeile die erstetotale Funktion F (1) = f1, in der zweiten Zeile die zweite totale Funktion F (2) =f2, ... in der i-ten Zeile die i-te totale Funktion F (i) = fi.
5. In der i-ten Spalte stehen dann die Elemente F (1)(i) = f1(i), f2(i), ... f(j)(i)....
6. Wir betrachten nun die Diagonale dieser Tabelle, F (1)(1)F (2)(2)...F (n)(n)..., dieihrerseits naturlich eine totale Funktion f : N → N darstellt mit der Funktions-vorschrift f(i) = F (i)(i) = Fi(i).
31
7. Wir verandern nun jedes Element F (i)(i), so dass wir ein Element m′i erhalten,so dass m′i 6= F (i)(i). Dafur konnen wir die totale Funktion f verwenden unddefinieren mit ihr die totale Funktion g : N→ N gemaß g(i) = f(i)+1 = F (i)(i)+1.
8. g ∈M , denn g ist eine totale Funktion und bildet von N auf N ab.
9. Es entsteht ein Widerspruch wie folgt: Da g ∈ M , muss es einen Index n ∈ Ngeben, so dass F (n) = g. Dann steht g(1)g(2)... also in der n-ten Zeile der Ta-belle. Demnach ist F (n)(n) = g(n). Allerdings Ist per Definition g(n) = f(n)+1 =F (n)(n)+1 6= F (n)(n). Also entsteht ein Widerspruch und eine AufzahlungsfunktionF : N→M kann nicht existieren.
Ein besonders wichtiger Beweisschritt ist hierbei der zu zeigen, dass das modifizierteDiagonalelement selbst Teil der Aufzahlung sein muss. Wir betrachten nun ein Bei-spiel fur einen fehlerhaften Diagonalisierungsbeweis und diskutieren, wieso der Beweistatsachlich fehlerhaft ist:
Beispiel 2.14. Wir betrachten folgenden fehlerhaften Beweis fur die Aussage, dass dieMenge Q der rationalen Zahlen im Intervall [0, 1] uberabzahlbar sind:
1. Jede rationale Zahl im Intervall [0, 1] lasst sich als Dezimalzahl darstellen. Manbeachte hierbei, dass 1 = 0, 9, die Aussage gilt also insbesondere auch fur 1.
2. Nimm an Q sei abzahlbar.
3. Dann gibt es eine surjektive Funktion f : N→ Q.
4. Wir konnen demnach eine Tabelle erstellen, in der an erster Stelle f(1), an zweiterStelle f(2)... an i-ter Stelle f(i) steht, jeweils rerparsentiert als Dezimalzahl.
5. In der i-ten Spalte stehen dann die Elemente f(1)(i), f(2)(i), ... f(j)(i)... wobeif(i)(j) die j-te Dezimalstelle der i-ten Zahl in Q darstellt.
6. Wir betrachten nun die Diagonale dieser Tabelle, f(1)(1)f(2)(2)...f(n)(n)....
7. Wir setzen nun fur jedes Element f(i)(i), den Wert m′i := f(i)(i) + 1 mod 10,dann gilt m′i 6= f(i)(i).
8. m′1m′2... ∈ Q, denn es handelt sich wiederum um eine Dezimaldarstellung einer
Zahl zwischen 0 und 1.
9. Es entsteht ein Widerspruch wie folgt: Da m′1m′2... ∈ Q, muss es einen Index n ∈ N
geben, so dass f(n) = m′1m′2.... Dann steht m′1m
′2... also in der n-ten Zeile der
Tabelle. Demnach ist f(n)(n) = m′n. Allerdings ist per Definition m′n 6= f(n)(n).Also entsteht ein Widerspruch und eine Aufzahlungsfunktion f : N → Q kannnicht existieren.
32
Wo liegt nun der Fehler in der Argumentation? Wir haben nicht grundlich genug ar-gumentiert, dass m′1m
′2... uberhaupt eine rationale Zahl reprasentiert. Es stimmt zwar,
dass jede rationale Zahl eine Dezimaldarstellung besitzt, allerdings ist umgekehrt ergibtnicht jede Dezimaldarstellung einer rationalen Zahl, sondern nur solche Dezimaldarstel-lungen, die periodisch werden (oder abbrechen, in diesem Fall kann man dies allerdingsals 0-Periode bezeichnen). Wir mussten also zeigen, dass m′1m
′2... periodisch wird, was
allerdings nicht moglich ist, da wir bereits gezeigt haben, dass Q ⊃ Q abzahlbar ist.
3 Berechenbarkeitstheorie
Nachdem wir uns mit verschiedenen Berechnungsmodellen befasst haben, wollen wiruns nun den Grenzen der Berechenbarkeit zuwenden. Zentrale Fragestellungen diesesKapitels sind: Gibt es Probleme, fur die es kein Entscheidungsverfahren gibt? Gibt esProbleme, die nicht einmal semientscheidbar sind? Wie beweist man, dass ein Problemnicht entscheidbar ist?
Zunachst wollen wir den bereits in der Vorlesung besprochenen Beweis, dass es Proble-me gibt, die unentscheidbar sind, noch einmal rekapitulieren. Wir zeigen hierzu, analogzur Vorlesung, dass es nicht entscheidbar ist, ob eine Turingmaschine, angesetzt auf ihrereigenen Codierung, terminiert. Wir betrachten in der Folge drei Probleme, die bereitsaus der Vorlesung bekannt sind:
Definition 3.1 (Halteprobleme). • Das allgemeine Halteproblem H erhalt eine Co-dierung w einer Turingmaschine Mw und eine Eingabe x und das Paar (w, x) ist inder Menge H genau dann wenn Mw auf der Eingabe x irgendwann anhalt. Formal:
H = w#x |Mw angesetzt auf x halt
• Das spezielle Halteproblem K erhalt eine Codierung w einer Turingmaschine Mw
als Eingabe. Ein Wort w ist in der Menge K enthalten, genau dann wenn Mw aufder Eingabe w – also seiner eigenen Codierung – irgendwann anhalt. Formal:
K = w |Mw angesetzt auf w halt
• Das Halteproblem auf leerem Band H0 erhalt eine Codierung w einer Turingma-schine Mw als Eingabe. Ein Wort w ist in der Menge H0 enthalten, genau dannwenn Mw auf der Eingabe ε – also dem leeren band – irgendwann anhalt. Formal:
H0 = w |Mw angesetzt auf ε halt
Wahrend K vorrangig als Hilfsproblem dient, um zeigen zu konnen, dass das allgemei-ne Halteproblem unentscheidbar ist, erweisen sich H und H0 als flexible Hilfsmittel inReduktionsbeweisen.
Im Folgenden werden wir nun zunachst mit einem Widerspruchsbeweis zeigen, dass Knicht entscheidbar ist und anschließend dieses Ergebnis verwenden, um das Beweisprinzipder Reduktion zu verdeutlichen und zu zeigen, dass auch die anderen beiden vorgestelltenHalteprobleme unentscheidbar sind.
33
Satz 3.2. Das spezielle Halteproblem K ist unentscheidbar, das heißt es existiert keineTuringmaschine M , so dass die von M berechnete Funktion die charakteristische Funk-tion χK von K ist.
Beweis. Wir zeigen dies mit einem Widerspruchsbeweis, nehmen also zunachst das Ge-genteil der Aussage an. Sei hierzu M gegeben, so dass die von M berechnete Funktiongerade die charakteristische Funktion χK ist. Das bedeutet, dass
χK(w) =
1 falls w ∈ K
0 sonst
Die Turingmaschine terminiert also auf allen Eingaben und gibt eine 1 oder 0 aus,abhangig davon, ob die Eingabe w die Codierung einer Turingmaschine Mw ist, die aufder Eingabe w terminiert (in diesem Fall ist die Ausgabe 1) oder nicht (in diesem Fallist die Ausgabe 0).
Wir konstruieren nun mittels M eine Turingmaschine M ′ wie folgt:
• Gegeben eine Eingabe w simuliert M ′ zunachst M auf w. M terminiert in jedemFall und gibt eine 1 aus, falls Mw angesetzt auf w terminiert und eine 0 falls Mw
auf der Eingabe w nicht terminiert.
• Falls die Ausgabe von M 1 ist, geht M ′ anschließend in eine Endlosschleife (rea-lisierbar beispielsweise mithilfe eines Fangzustandes) und terminiert nicht – gehtalso niemals in einen Endzustand uber.
• Falls die Ausgabe von M hingegen 0 ist, geht M ′ in einen Endzustand uber.
Es sei nun w die Codierung von M ′, es gilt also M ′ = Mw. Wir wollen nun ermitteln,wie sich M ′ angesetzt auf der Eingabe w verhalt. Nach Konstruktion von M ′ gibt es nurzwei mogliche Verhaltensweisen:
• M ′ terminiert auf der Eingabe w. In diesem Fall muss M , angesetzt auf w dieAusgabe 0 ergeben haben. Das bedeutet, dass – man beachte, dass M χK berechnet– dass M ′ = Mw auf der Eingabe w nicht terminiert. Es ergibt sich also einWiderspruch. M ′ kann also nicht terminieren.
• M ′ terminiert auf der Eingabe w nicht. Wir beachten, dass M eine totale Funktionberechnet, das bedeutet, dass M angesetzt auf w sicher terminiert. Damit M ′ nachder Simulation von M nicht terminiert, muss die Ausgabe von M angesetzt auf wgerade 1 sein. Das bedeutet – abermals unter Beachtung des Umstandes, dass Mdie Funktion χK berechnet – dass M ′ = Mw auf der Eingabe w terminiert. Das istaber ein Widerspruch zur Annahme, dass M ′ auf w nicht terminiert. Also mussM ′ terminieren.
Nun haben wir gesehen, dass M ′ nicht terminieren kann, ohne einen Widerspruch zuerzeugen und dass im Fall der nicht-Terminierung ebenfalls ein Widerspruch entsteht.Also kann es eine Maschine wie M ′ uberhaupt nicht geben. Da zur Konstruktion von
34
M ′ nur angenommen wurde, dass es die Maschine M gibt, kann es also insbesondere dieMaschine M nicht geben und somit also keine Maschine existieren, die die Funktion χK
berechnet.
Der Beweis besitzt starke Parallelen zu einem Diagonalisierungsbeweis. In diesem Fallwissen wir, dass die Menge aller Turingmaschinen abzahlbar ist – wir konnen einfach ihreCodierungen in langenlexikografischer Reihenfolge aufzahlen. Wenn wir das Schema ausdem vorherigen Kapitel betrachten, andern sich nur Punkte 2 und 9. In Punkt 2 wissenwir bereits, dass die Menge der Turingmaschinen abzahlbar ist, stattdessen nehmen wiran, dass eine Turingmaschine M die eine bestimmte Funktion berechnet, existiert (alsoin der Aufzahlung vorkommt). In Punkt 9 entsteht entsprechend kein Widerspruch gegendie Abzahlbarkeit, sondern gegen die Annahme, dass M existiert. In Anlehnung unseresNeun-Schrittes zur Diagonalisierung kann man also den Beweis also alternativ wie folgtstrukturieren:
1. Wir beachten, dass jede Turingmaschine sich binar codieren lasst und jede Binarcodierungder Codierung einer Turingmaschine entspricht. Weiterhin konnen wir Binarcodierungenmit naturlichen Zahlen in 1:1 Beziehung setzen und tragen charakterisieren Turing-maschinen gemaß ihres Terminierungsverhaltens auf jeder moglichen Binarcodierung.Wir schreiben fur eine Turingmaschine M also die unendliche Sequenz TM :=tM(w0)tM(w1)tM(w2)..., wobei
tM(w) =
1 falls M auf der Eingabe w halt
0 sonst
2. Wir wissen dass die Menge aller Turingmaschinen abzahlbar ist, wir nehmen zusatzlichan, dass eine Turingmaschine (oben M genannt) existiert, die χK berechnet (sieist dann ubrigens uber die Sequenz 111... charakterisiert).
3. Es gibt eine surjektive Funktion f : N→ Mw | w ∈ 0, 1∗.
4. Wir konnen demnach eine Tabelle erstellen, in der an erster Stelle f(1), also dieerste Turingmaschine, charakterisiert durch ihre Sequenz TM1 , an zweiter Stellef(2), also die zweite Turingmaschine, charakterisiert durch ihre Sequenz TM2 ... ani-ter Stelle f(i), also die i-te Turingmaschine, charakterisiert durch ihre SequenzTMi
, steht.
5. In der i-ten Spalte stehen dann die Elemente tM1(wi), tM2(wi), ... tMj(wi)....
6. Wir betrachten nun die Diagonale dieser Tabelle, tM1(w1)tM2(w2)...tMn(wn)....
7. Wir verandern nun jedes Element tMi(wi), so dass wir ein Element m′i erhalten,
so dass m′i 6= tMi(wi), die Turingmaschine M ′ terminiert also genau dann auf wi,
wenn Mwiauf wi nicht terminiert.
35
8. Um nun zu zeigen, dass es die Turingmaschine M ′ geben muss, mussen wir dieAnnahme verwenden, dass es M gibt. Mithilfe von M konnen wir M ′ aber wie imobigen Beweis konstruieren.
9. Gelingt dies, so entsteht ein Widerspruch wie folgt: Da m′1m′2... eine Turingma-
schine ist, muss es einen Index n ∈ N geben, so dass f(n) = m′1m′2.... Dann steht
m′1m′2... also in der n-ten Zeile der Tabelle. Demnach ist tMn(wn) = m′n. Allerdings
ist per Definition m′n 6= tMn(wn). Also entsteht ein Widerspruch und die zuvorangenommene Maschine M kann nicht existieren.
Wollen wir nun weitere Probleme als unentscheidbar charakterisieren, mussen wir abernicht immer einen so komplexen Widerspruchsbeweis verwenden, sondern konnen aufbestehende Resultate zuruckgreifen. Da wir bereits ein unentscheidbares Problem Kgefunden haben, konnen wir weitere unentscheidbare Probleme P wie folgt als solchenachweisen: Angenommen P ware entscheidbar. Dann konnten wir K mithilfe eines Ent-scheiders fur B entscheiden. Da wir aber bereits wissen, dass K nicht entscheidbar ist,kann auch B nicht entscheidbar sein. Formell kann man das Reduktionsbeweisverfahrenwie folgt beschreiben:
Definition 3.3 (Reduktion). Gegeben seien Sprachen A ⊆ Σ∗ und B ⊆ Γ∗. Dann ist Aauf B reduzierbar genau dann wenn es eine totale und berechenbare Funktion f : Σ∗ → Γ∗
gibt, so dass fur alle x ∈ Σ∗ gilt:
x ∈ A⇔ f(x) ∈ B
Das allgemeine Vorgehen bei der Reduktion um zu zeigen, dass ein Problem unent-scheidbar ist, ist also das Folgende:
1. Es ist unser Ziel, zu zeigen, dass B ⊆ Γ∗ unentscheidbar ist.
2. Dazu suchen wir ein unentscheidbares Problem U ⊆ Σ∗ heraus, von dem im Vorfeldbereits gezeigt wurde, dass es unentscheidbar ist.
3. Wir zeigen nun, dass A ≤ B, intuitiv: A ist hochstens so schwer zu losen wie B.
4. Hierzu suchen wir eine Funktion f : Σ∗ → Γ∗, die die Eigenschaft hat, dass f(w) ∈B genau dann wenn w ∈ A.
5. Unsere Beweisverpflichtungen sind also:
• f ist total, das heißt fur jedes w ∈ Σ∗ existiert ein w′ ∈ Γ∗, so dass f(w) = w′.
• f ist berechenbar, es gibt also eine Turingmaschine M so dass M die Funktionf berechnet. Dieser Beweisschritt wird oft informell durchgefuhrt, indem manbekannte berechenbare Funktionen verknupft oder informell erklart wie eineTuringmaschine gebaut werden kann, die diese Funktion berechnet.
• Es gilt f(w) ∈ B ⇔ w ∈ A
36
6. Per Widerspruch folgt dann, dass B nicht entscheidbar sein kann: Angenommen Bsei berechenbar, es gabe also eine Turingmaschine, die χB berechnet. Dann konnenwir auch χB f berechnen, indem wir zunachst die Maschine fur f simulieren undanschließend die Ausgabe in die Maschine fur χB ubergeben. Da wir wissen, dassχA nicht berechenbar ist, allerdings gilt χA = χB f , entsteht ein Widerspruch.
Wir fuhren nun beispielhaft die Beweise, dass das allgemeine Halteproblem H und dasHalteproblem auf leerem Band H0 unentscheidbar sind und folgen dabei genau demobigen Verfahren.
Satz 3.4. Das Halteproblem auf leerem Band H ist unentscheidbar.
Beweis. 1. Es ist unser Ziel, zu zeigen, dass H unentscheidbar ist.
2. Dazu verwenden wir das unentscheidbare Problem K, von dem im Vorfeld bereitsgezeigt wurde, dass es unentscheidbar ist.
3. Wir zeigen nun, dass K ≤ H, intuitiv: K ist hochstens so schwer zu losen wie H.
4. Hierzu verwenden wir die Funktion f(w) = (w,w), die die Eigenschaft hat, dassf(w) ∈ H genau dann wenn w ∈ K.
5. Unsere Beweisverpflichtungen sind also:
• f ist total, denn fur alle Worter w existiert das Paar (w,w).
• f ist berechenbar, denn eine Turingmaschine kann, gegeben eine Eingabe wdas Ende der Eingabe mit einem Komma markieren und dann zeichenweisew hinter das Komma kopieren, indem fur jedes Zeichen a ∈ Σ ein neues Zei-chen a′ ∈ Σ in das Alphabet der Turingmaschine eingefuhrt wird, das dazudient, zu markieren, welches Zeichen als letztes kopiert wurde. Im Zustandder Turingmaschine kann diese dann stets festhalten, welches Zeichen geradezu kopieren ist, in diesem Zustand an das Ende des Wortes auf dem Bandlaufen und das zu kopierende Zeichen dort ablegen. Anschließend lauft dieTuringmaschine zuruck bis sie ein Zeichen vom Typ a′ findet, ersetzt diesesZeichen wieder durch a, markiert das darauf folgende Zeichen und wieder-holt diesen Vorgang, bis die gesamte Eingabe kopiert ist. Anschließend mussnur noch das Ende der Eingabe mit einer schließenden und der Anfang derEingabe mit einer offnenden Klammer versehen werden, hierzu bedarf es nurzweier weiterer Zustande.
• Es gilt f(w) ∈ H⇔ (w,w) ∈ H⇔Mw halt auf w ⇔ w ∈ K
6. Per Widerspruch folgt dann, dass H nicht berechenbar sein kann: Angenommen Hsei entscheidbar, es gabe also eine Turingmaschine, die χH berechnet. Dann konnenwir auch χH f berechnen, indem wir zunachst die Maschine fur f simulieren undanschließend die Ausgabe in die Maschine fur χH ubergeben. Da wir wissen, dassχK nicht berechenbar ist, allerdings gilt χK = χH f , entsteht ein Widerspruch.Also ist H unentscheidbar.
37
Analog lasst sich auch die Unentscheidbarkeit von H0 beweisen:
Satz 3.5. Das Halteproblem auf leerem Band H0 ist unentscheidbar.
Beweis. 1. Es ist unser Ziel, zu zeigen, dass H0 unentscheidbar ist.
2. Dazu verwenden wir das unentscheidbare Problem H, von dem im Vorfeld bereitsgezeigt wurde, dass es unentscheidbar ist.
3. Wir zeigen nun, dass H ≤ H0, intuitiv: H ist hochstens so schwer zu losen wie H0.
4. Hierzu verwenden wir die Funktion f(w, x) = w′, wobei w′ die Codierung derfolgenden Turingmaschine ist: Auf dem leeren Band wird zunachst das Wort x vonrechts nach links auf das Band geschrieben und anschließend die Turingmaschinew auf der aktuellen Eingabe (die nun gerade x ist) simuliert.
5. Unsere Beweisverpflichtungen sind also:
• f ist total, denn fur alle Worter w existiert eine zugehorige TuringmaschineMw, es gibt eine Turingmaschine, die x auf das Band schreibt und es istmoglich, eine beliebige andere Turingmaschine in einer Turingmaschine zusimulieren, also gibt es eine Turingmaschine M ′, die genau das tut. Da jedeTuringmaschine eine Codierung besitzt, existiert also auch eine Codierung w′
von M ’.
• f ist berechenbar, denn wir haben bereits gezeigt, dass die Codierung einerjeden Turingmaschine berechenbar ist und eine Turingmaschine, die x vonrechts nach links auf das Band schreibt ist mit |x| vielen Zustanden (wobeijeweils der i-te Zustand das i-te Zeichen auf das Band schreibt) offensichtlichkonstruierbar, die anschließende Simulation von Mw ist umsetzbar, indemman schlicht die Zustande, die notig sind, um |x| auf das Band zu schreiben,als neue Zustande zu M hinzufugt, den |x|-ten neuen Zustand zum neuenStartzustand erklart und vom 1-ten neuen Zustand beim Schreiben des 1-tenZeichens von x in den Startzustand von Mw ubergeht.
• Es gilt f(w, x) ∈ H0 ⇔Mf(w,x) halt auf ε⇔Mw halt auf x⇔ (w, x) ∈ H
6. Per Widerspruch folgt dann, dass H0 nicht entscheidbar sein kann: Angenommen H0
sei entscheidbar, es gabe also eine Turingmaschine, die χH0 berechnet. Dann konnenwir auch χH0 f berechnen, indem wir zunachst die Maschine fur f simulieren undanschließend die Ausgabe in die Maschine fur χH0 ubergeben. Da wir wissen, dassχH nicht berechenbar ist, allerdings gilt χH = χH0 f , entsteht ein Widerspruch.Also ist H0 unentscheidbar.
Diese Familie von Halteproblemen legt bereits nahe, dass Aussagen uber die von einerTuringmaschine berechneten Funktionen in vielen Fallen nicht algorithmisch getroffenwerden konnen. Wie weitreichend die nicht-Entscheidbarkeit ist, zeigt der Satz von Rice.
38
Satz 3.6 (Satz von Rice). Es sei R die Klasse aller Turing-berechenbaren Funktionenund ∅ ⊂ S ⊂ R eine beliebige Teilemenge, abgesehen von der leeren Menge und R selbst.Dann ist die Sprache
C(S) = w |Mw berechnet eine Funktion aus S
unentscheidbar.
Beweis. Wir zeigen dies durch Reduktion. Sei hierzu ein ∅ ⊂ S ⊂ R beliebig, festgewahlt. Wir fuhren eine Fallunterscheidung durch: Ist Ω ∈ S? Falls nein, setze S = S.Anderenfalls gilt: C(S) ist entscheidbar genau dann wenn C(R \ S) entscheidbar ist,setze in diesem Fall S = R \ S.
1. Es ist unser Ziel, zu zeigen, dass C(S) unentscheidbar ist.
2. Dazu verwenden wir das unentscheidbare Problem H0, von dem im Vorfeld bereitsgezeigt wurde, dass es unentscheidbar ist.
3. Wir zeigen nun, dass H0 ≤ C(S), intuitiv: H0 ist hochstens so schwer zu losen wieC(S).
4. Hierzu definieren wir die folgende Vorverarbeitungsfunktion: Gegeben ein beliebi-ges Wort w, baue eine Zwei-Band-Turingmaschine M die wie folgt agiert:
• Wahle eine beliebige Funktion g aus S. Eine solche Funktion g muss es nachDefinition geben und sie ist auf keinen Fall Ω.
• Es gibt also eine TuringmaschineM ′, die g berechnet, da g Turing-berechenbarist.
• M simuliert beim Start zunachst Mw auf dem leeren Band.
• Wird ein Endzustand von Mw erreicht, wird anschließend M ′ auf dem erstenBand simuliert.
• Wird ein Endzustand von M ′ erreicht, terminiert M .
Es existiert eine zu M aquivalente Ein-Band-Turingmaschine, deren Codierung wirw′ nennen. Gib w′ aus.
5. Unsere Beweisverpflichtungen sind also:
• f ist total, das heißt fur jedes w existiert ein w′, so dass f(w) = w′: Wir wis-sen, dass Turingmaschinen von Zwei-Band-Turingmaschinen simuliert wer-den konnen und dass es die Turingmaschine M ′ geben muss, weil L Turing-berechenbar ist. Wir haben zudem gesehen, dass man Zwei-Band-Turingmaschinenin Ein-Band-Turingmaschinen ubersetzen kann und dass die Codierung einerjeden Ein-Band-Turingmaschine existiert. Also ist f total.
• f ist zudem berechenbar, denn die notwendigen Schritte, Simulation zweierTuringmaschinen, Transformation einer Zwei-Band-Turingmaschine in eineEin-Band-Turingmaschine und Codierung einer Turingmaschine sind bere-chenbar.
39
• Es gilt f(w) ∈ C(S) ⇔ w ∈ H0: Angenommen, w ∈ H0, dann terminiert dieSimulation von Mw auf dem leeren Band immer und nach Definition berechnetMw′ dann die Funktion g. Ist w /∈ H0, so terminiert Mw′ auf keiner Eingabe,die von Mw′ berechnete Funktion ist also gerade Ω. Nach Voraussetzung giltaber dass Ω /∈ S, also ist dann w′ /∈ C(S).
6. Per Widerspruch folgt dann, dass C(S) nicht entscheidbar sein kann: AngenommenC(S) sei berechenbar, es gabe also eine Turingmaschine, die χC(S) berechnet. Dannkonnen wir auch χC(S) f berechnen, indem wir zunachst die Maschine fur fsimulieren und anschließend die Ausgabe in die Maschine fur χC(S) ubergeben. Dawir wissen, dass χH0 nicht berechenbar ist, allerdings gilt χH0 = χC(S) f , entstehtein Widerspruch.
Der Satz von Rice kann insbesondere dazu verwendet werden, zu zeigen, dass jedenicht-triviale Eigenschaft einer Funktion (nicht der Turingmaschine!), die eine Turing-maschine berechnet unentscheidbar ist. Nicht-trivial ist eine Eigenschaft dann, wenn sienicht von jeder oder gar keiner Turing-berechenbaren Funktion erfullt wird. Beispielehierfur wurden in der Vorlesung bereits genannt:
• Die Eigenschaft total zu sein, denn es gibt sowohl totale (z. B. die konstante 0-Funktion) als auch nicht-totale Funktionen (z. B. Ω), die Turing-berechenbar sind.
• Die Eigenschaft, genau eine fest gewahlte Turing-berechenbare Funktion f (bei-spielsweise Ω) zu sein, denn es gibt mehr als eine Turing-berechenbare Funktion
• Die Eigenschaft, eine konstante Funktion zu sein, denn es gibt konstante Turing-berechenbare Funktionen (z. B. die konstante 0-Funktion), aber auch nicht kon-stante Turing-berechenbare Funktionen (z. B. die Nachfolgerfunktion).
Ein haufig vorkommendes Missverstandnis ist allerdings die Annahme, dass auch bei-spielsweise Aussagen uber die Zahl der Zustande oder die Zahl der Endzustande ei-ner Turingmaschine mithilfe des Satzes von Rice als unentscheidbar klassifiziert werdenkonnen.
Beispiel 3.7. Wenngleich wir das bereits auf andere Weise gezeigt haben, wollen wireinmal betrachten, wie mit Hilfe des Satzes von Rice das allgemeine Halteproblem alsunentscheidbar nachgewiesen werden konnte. Wir wollen die Frage beantworten, ob, ge-geben ein Wort w#x die Maschine Mw bei Eingabe von x irgendwann anhalt. Wenn dasder Fall ist, dann ist die Funktion f , die Mw berechnet, an der Stelle x definiert. Wirbetrachten also
S = g | g ist auf x definiert.und beobachten, dass S nicht die Menge aller turingberechenbarer Funktionen ist: Dieuberall undefinierte Funktion Ω ist sicherlich nicht in S enthalten. Zudem ist S nichtleer, denn die konstante 0-Funktion ist beispielsweise in S enthalten. Also folgt nach demSatz von Rice, dass unentscheidbar ist, ob Mw eine Funktion in S berechnet und somit,dass das allgemeine Halteproblem unentscheidbar ist.
40
Ein weiteres Problem, von dem in der Vorlesung gezeigt wurde, dass es unentscheidbarist, ist das Schnittproblem fur kontextfreie Grammatiken:
Definition 3.8 (Schnittproblem fur kontextfreie Grammatiken). Gegeben seien zweikontextfreie Grammatiken G1 und G2. Das Schnittproblem fur diese Grammatiken istdann die Frage, ob L(G1) ∩ L(G2) leer ist. Formal:
S = (G1, G2) | G1, G2 sind kontextfreie Grammatiken und L(G1) ∩ L(G2) = ∅
Der Schnitt zweier Typ 2 Sprachen ist in jedem Fall vom Typ 1, aber nicht zwingendvom Typ 2. In der Vorlesung Automaten und formale Sprachen wurde ein Verfahrenvorgestellt, um zu entscheiden, ob ein gegebenes Wort w in einer Typ 1 Sprache liegt,daher ist das Komplement von S semientscheidbar: Man zahlt die Worter uber demAlphabet der Lange nach auf und uberpruft fur jedes Wort, ob es in L(G1) ∩ L(G2)liegt. Falls man ein Wort findet, das in der Sprache liegt, gibt man 1 aus. Allerdings istS selbst nicht semientscheidbar. Das hier vorgestellte Semientscheidungsverfahren furdas Komplement von S ist kein Entscheidungsverfahren, denn im Falle dessen, dass einPaar von Grammatiken in der Sprache S liegt, bricht das Verfahren niemals ab.
Zum Abschluss betrachten wir noch einmal, was Reduktion fur die Entscheidbarkeitbedeutet. Seien hierzu Probleme A ⊆ Σ∗ und B ⊆ Γ∗ gegeben und sei f : Σ∗ → Γ∗ eineReduktionsfunktion von A nach B, also A ≤ B. Dann gilt:
• Falls A unentscheidbar ist, dann muss auch B unentscheidbar sein, da anderenfallsdas Entscheidungsverfahren fur B zusammen mit f verwendet werden kann, umA zu entscheiden.
• Falls B entscheidbar ist, dann muss auch A entscheidbar sein, denn mithilfe derReduktionsfunktion f und dem Entscheidungsverfahren fur B kann man A ent-scheiden.
Das bedeutet insbesondere, dass die folgende Konstellation nicht auftreten konnen:
• A ist unentscheidbar und B ist entscheidbar, also ein unentscheidbares Problemwird auf ein entscheidbares Problem reduziert.
4 Komplexitatstheorie
Im Folgenden wollen wir uns mit der Laufzeit von Algorithmen, sowie mit der Schwierig-keit von Problemen beschaftigen. Bekanntlich gibt es fur entscheidbare Probleme stetsmehr als einen Entscheidungsalgorithmus – eine Turingmaschine, die ein Problem ent-scheidet, kann beispielsweise schlicht um einige neue Zustande erweitert werden undvom Startzustand aus zunachst durch alle neuen Zustande hindurchwechseln, sich an-schließend wie die ursprungliche Turingmschine verhalten. Auf diese Weise erhalt maneine zweite, von der ursprunglichen Turingmaschine verschiedene Turingmaschine, diedas gleiche Akzeptantverhalten aufweist. Daher muss man zur Bestimmung dessen, wie
41
”schwer“ ein Problem ist, auf einen konkreten Entscheidungsalgorithmus Bezug neh-
men. Sinnvoll erscheint in dieser Hinsicht die Existenzquantifizierung: Ein Problem Akann in einer durch eine Funktion f : N0 → N0 beschrankte Laufzeit entschieden wer-den, wenn es jedenfalls einen Algorithmus gibt, der A entscheidet und dessen Laufzeitin Abhangigkeit von der Eingabe durch f beschrankt ist. Auf diese Weise wollen wirProbleme der Schwierigkeit nach klassifizieren.
Daruber hinaus interessiert uns nicht die exakte Laufzeit, sondern eine moglichst kom-pakt formulierte obere Schranke. Konkret interessiert uns das asymptotische Wachstums-verhalten der Laufzeit, das heißt, wie sich die Laufzeit bei immer weiter wachsenderEingabegroße entwickelt. Deswegen betrachten wir nicht etwa Laufzeitbeschrankungendurch Funktionen, sondern durch Funktionenklassen, die wir als aquivalent auffassen.Zu diesem Zweck verwenden wir die Landau-Notation.
Definition 4.1 (Landau-Notation). Gegeben seien zwei Funktionen f und g (f, g : R→R), dann ist die Klasse O(g) wie folgt definiert:
f ∈ O(g)⇔ ∃C > 0 ∃N ∀x > N : |f(x)| ≤ C · |g(x)| N,C ∈ R
Wir werden im Folgenden oft eine Funktion mit ihrer Funktionsvorschrift identifizie-ren, also beispielsweise einfach x2 fur die Funktion f : R→ R, f(x) = x2 schreiben. ZurWiderholung des Begriffs werden wir im Folgenden zeigen, dass ax2 + bx + c ∈ O(x2)und x2 ∈ O(2x).
Beispiel 4.2. • Wir zeigen, dass ax2 + bx + c ∈ O(x2). Wir seten N = 1 undbeobachten, dass dann fur alle x > N gilt: |b|x ≥ bx, |c| ≥ c, wir konnen alsoo.B.d.A annehmen, dass b, c ≥ 0. Dann beobachten wir weiterhin, dass bx < bx2
und c < cx2 und konnen daher rechnen ax2+bx+c < ax2+bx2+cx2 = (a+b+c)x2.Wir setzen also C = a + b + c und haben somit gezeigt, dass Cx2 ≥ ax2 + bx + cfur alle x > N , also ax2 + bx+ c ∈ O(x2).
• Wir zeigen x2 ∈ O(2x). Wir setzen N = 4 und beobachten, dass fur x = N giltx2 = 42 = 16 = 16 = 2x. Zudem steigt 2x − x2 monoton fur x ≥ 4, denn die ersteAbleitung dieses Ausdrucks ist ln4 · 2x − 2x. Fur x = 4 gilt aber ln4 · 2x − 2x =ln4 · 16− 8 und ln4 > 1. Weiterhin steigt ln4 · 2x− 2x monoton fur x > 4, denn dieerste Ableitung dieses Terms ist (ln4)2 · 2x − 2, was wiederum fur x > 4 positiv istund monoton steigt, weil 2x monoton steigt. Also ist, mit C = 1, N = 4 gezeigt,dass x2 ∈ O(2x).
Basierend auf dieser Notation teilen wir Algorithmen in Schwierigkeitsklassen wieO(2n), O(n2) oder O(n) ein. Besonders interessant sind in dieser Hinsicht diejenigenProbleme, die einen Algorithmus besitzen, der sie in polynomieller Zeit entscheidet, furdie also ein Algorithmus existiert, dessen Laufzeit in O(p) liegt, wobei p ein Polynomin der Lange der Eingabe ist. Wir definieren dementsprechend die Aquivalenzklassen Pund NP wie folgt:
Definition 4.3 (P und NP). • Ein Problem A liegt in der Klasse P, falls es k ∈N0 und eine deterministische Turingmaschine gibt, die A entscheidet und derenLaufzeit in Abhangigkeit von der Lange Eingabe n in O(nk) beschrankt ist.
42
• Ein Problem A liegt in der Klasse NP, falls es k ∈ N0 und eine nichtdeterminis-tische Turingmaschine gibt, die A entscheidet und deren Laufzeit in Abhangigkeitvon der Lange Eingabe n in O(nk) beschrankt ist.
Offensichtlich ist jedes Problem der Klasse P auch ein Problem der Klasse NP. We-niger offensichtlich ist allerdings die Fragestellung, ob umgekehrt auch jedes Problemder Klasse NP ein Problem der Klasse P ist. In der Tat ist dieses unter dem NamenP 6= NP-Problem bekannte Problem bis heute nicht gelost. Um sich der Losung diesesProblems zu nahern und eine genauere Analyse der Schwierigkeit der Probleme in NP zuermoglichen, wurde das Verfahren der polynomiellen Reduktion entwickelt. Intuitiv kannman ein Problem A auf ein Problem B reduzieren, wenn es hochstens (deterministisch)polynomiell viel Zusatzaufwand benotigt, Instanzen des Problems A auf aquivalente In-stanzen des Problems B zuruckzufuhren.
Definition 4.4 (Reduktion). Gegeben seien Sprachen A ⊆ Σ∗ und B ⊆ Γ∗. Dann istA auf B reduzierbar genau dann wenn es eine totale und von einer deterministischenTuringmaschine in Polynomzeit berechenbare Funktion f : Σ∗ → Γ∗ gibt, so dass fur allex ∈ Σ∗ gilt:
x ∈ A⇔ f(x) ∈ B
Wir schreiben A ≤p B.
Auf dieser Basis lassen sich die Problemklassen der NP-harten und NP-vollstandigenProbleme definieren:
Definition 4.5. Es sei B ∈ Σ∗ ein beliebiges Entscheidungsproblem.
• Falls fur alle Probleme A ∈ NP gilt, dass A ≤p B, dann ist B ein NP-hartesProblem.
• Falls B NP-hart ist und zusatzlich in der Klasse NP liegt, so ist B in der Klasseder NP-vollstandigen Probleme.
Wie bereits die gewohnliche Reduktion lasst sich auch die polynomielle Reduktion ineinem mehrschrittigen Verfahren beschreiben. Das allgemeine Vorgehen um mit einerReduktion zu zeigen, dass ein Problem NP-hart ist, ist also das Folgende:
1. Es ist unser Ziel, zu zeigen, dass B ⊆ Γ∗ NP-hart ist.
2. Dazu suchen wir ein NP-hartes Problem A ⊆ Σ∗ heraus, von dem im Vorfeld bereitsgezeigt wurde, dass es NP-hart ist.
3. Wir zeigen nun, dass A ≤p B, intuitiv: A ist hochstens so schwer zu losen wie B.
4. Hierzu suchen wir eine Funktion f : Σ∗ → Γ∗, die die Eigenschaft hat, dass f(w) ∈B genau dann wenn w ∈ A.
5. Unsere Beweisverpflichtungen sind also:
43
• f ist total, das heißt fur jedes w ∈ Σ∗ existiert ein w′ ∈ Γ∗, so dass f(w) = w′.
• f ist in Polynomzeit von einer deterministischen Turingmaschine berechenbar,es gibt also eine Turingmaschine M so dass M die Funktion f berechnet undderen Laufzeit durch ein Polynom beschrankt ist. Dieser Beweisschritt wirdoft informell durchgefuhrt, indem man bekannte in Polynomzeit berechenbareFunktionen verknupft oder informell erklart wie eine Turingmaschine gebautwerden kann, die diese Funktion in Polynomzeit berechnet.
• Es gilt f(w) ∈ B ⇔ w ∈ A
6. Mithilfe der Transitivitat von polynomieller Reduktion folgt dann, dass B NP-hartsein muss: Gegeben irgendein Problem P ′ ∈ NP, dann lasst sich P ′ polynomiell aufP reduzieren: Da U bereits als NP-vollstandig bekannt ist, gibt es eine polynomielleReduktionsfunktion g von P ′ auf U . Es sei q das Polynom das die Laufzeit desAlgorithmus, der g berechnet, beschrankt und p das Polynom, das die Laufzeitdes Algorithmus, der f berechnet, beschrankt. Gegeben eine Eingabe w fur dasProblem P ′, ist |g(w)| ≤ q(|w|) und somit f g beschrankt durch p(q(|w|))+q(|w|),was wiederum ein Polynom ist.
Konnte man fur ein NP-vollstandiges Problem B zeigen, dass es in P liegt, so waredamit gezeigt, dass P = NP. Sei die Laufzeit eines Algorithmus, der B entscheidetbeschrankt durch das Polynom p und irgendein anderen Problem A ∈ NP gegeben.Dann gibt es eine Reduktionsfunktion f die sich in einer Zeit berechnen lasst, die durchein Polynom q beschrankt ist und A ≤p B beweist. Dann kann auch A in polynomiellerZeit mit einem deterministischen Algorithmus gelost werden, denn χA = χB f undχB f kann in Zeit p(q(|w|))+q(|w|) berechnet werden. Wie bereits zuvor argumentiert,ist das wiederum ein Polynom.
44
