Skript FSK
skript.txt
—
Plain Text,
131 KB (135013 bytes)
Dateiinhalt
Skriptum zur Vorlesung "Formale Sprachen und Komplexitaet" Martin Hofmann SS 2011 Das Skriptum dient der Orientierung und wird im Laufe der Vorlesung u.U. erweitert und verbessert. Massgeblich ist die Literatur (Schoening) und die Tafelanschrift. 0: Inhalt: ========== I Formale Sprachen und Automaten: - Chomsky Grammatiken - Regulaere Sprachen - Endliche Automaten - Nichtdeterminismus - Abschlusseigenschaften - Kontextfreie Sprachen - Abschlusseigenschaften - Pumpinglemma - Wortproblem, CYK-Algorithmus - Kellerautomaten - Kontextsensitive Sprachen - Linear beschraenkte Automaten II Berechenbarkeit: - Turingmaschinen - Loop Programme - While Programme - Church-Turing These - Primitive Rekursion - mu-Rekursion - Ackermannfunktion - Halteproblem und Unentscheidbarkeit III Komplexitaetstheorie: - Zeit- / Platzkomplexitaet - Die Klasse P (polynomiale Zeit) - Beispiele nichttrivialer Algorithmen in P - Die Klasse NP - Charakterisierung mithilfe von Advice - NP Vollstaendigkeit - Satz von Cook - Beispiele NP vollst. Probleme IV Logik - Goedels Unvollstaendigkeitssatz. Literatur: U Schoening: Theoretische Informatik kurzgefasst. (Vorlesungslehrbuch) Aho-Hopcroft-Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley, 1979. ************************************ *I. Formale Sprachen und Automaten.* ************************************ 1 Einfuehrung und Allgemeines ============================= 1.1 Alphabete und Woerter ------------------------- Definition: Sei Sigma eine endliche Menge. Sigma* bezeichnet die Menge aller endlichen Woerter ueber Sigma. Das leere Wort wird mit epsilon (manchmal auch lambda) bezeichnet. {a,b}* = {epsilon, a, b, aa, ab, ba, bb, aaa, aab, ... } Die Hintereinanderschreibung von Woertern bezeichnet man als Konkatenation oder Verkettung. Sie wird (wie die Multiplikation) durch Infixpunkt notiert, welcher auch weggelassen werden kann. aab.bab = aabbab Falls w = ababa und t = bbb, dann wt=abababbb Stets gilt epsilonw=wepsilon=w Sigma* bildet mit der Konkatenation und epsilon ein Monoid, das freie Monoid ueber Sigma. (Frei, weil keine Gleichungen ausser den zwingend erforderten Monoidgleichungen gelten) Fuehrt man etwa die Gesetze ab=ba=epsilon ein, so erhaelt man ein anderes Monoid, in dem z.B. abbb = bbabba gilt. Dieses Monoid ist zu einem wohlbekannten Monoid isomorph. Welchem? Gilt w=uv, so ist u ein Praefix von w und v ein Suffix von w. Das Wort aabba hat die Praefixe epsilon, a, aa, aab, aabb, aabba. Weitere Notation Sigma+ = Sigma* \ {epsilon} Eine Teilmenge U von Sigma* heisst Sprache ueber Sigma. Sind U, V Sprachen ueber demselben Alphabet, so bezeichnet UV die Sprache UV = {uv | u:U, v:V} = {w | es ex u:U, v:V so dass w=uv} Potenzschreibweise: w^n = wwwww...w (n Faktoren), U^n = UUUUU...U (n Faktoren) Die Vereinigung U u V von Sprachen U, V wird gern auch U+V geschrieben. Die Sprache U* besteht aus allen Woertern der Form w1w2...wk wobei wi:U und k:N. Bei einelementige Sprachen laesst man gern die Mengenklammern weg. Also ist z.B. a(a+b)* die Menge aller Woerter ueber {a,b}, die mit einem a anfangen. 1.2 Chomsky Grammatiken ----------------------- Definition: Eine Grammatik ist ein 4-Tupel G = (V,Sigma,P,S) wobei: V endliche Menge (Nichtterminalsymbole) Sigma endliche Menge (Terminalsymbole, Alphabet) P <= (V u Sigma)+ * (V u Sigma)* (Produktionen) S:V (Startsymbol) Die Elemente (x,y):P werden in der Regel als x->y geschrieben und heissen Produktionen Sei u,v : (V u Sigma)*. Wir definieren u=>v durch u=>v <=> es ex Produktion y->y', sowie Woerter x,z so dass u=xyz und u=>v=xy'z. Mit =>* bezeichnen wir die reflexive, transitive Huelle von =>, d.h. u =>* v wenn existieren w1, w2, ..., wk wobei u=w1 w1=>w2 ... wk-1=>wk wk=v Spezialfall: k=1, dann einfach u=v. Definition: Die von einer Grammatik G erzeugte Sprache L(G) <= Sigma* ist definiert durch L(G) = {w:Sigma* | S=>*w} Eine Folge von Worten S=w0, w1, w2, ..., wk=w wobei wi=>wi+1 heisst Ableitung von w:L(G) Beispiel einer Typ-0 Grammatik: S -> A1QE Z1 -> 11Z ZE -> QE RE -> QE 1Q -> Q1 AQ -> AZ AQ1 -> AR R111 -> 1R RE -> epsilon ZE -> epsilon AZ -> Z AR -> R Beispielableitung: A -> A1QE -> AQ1E -> AZ1E -> A11ZE -> A11QE -> AQ11E -> AZ11E -> A1111QE -> AQ1111E -> AQ1111 1111 1111 1111E -> AR 111 1111 1111 1111E -> R 111 1111 1111 1111E -> 1 R 1111 1111 1111E -> 11111RE -> 11111 Die Frage, ob L(G) = {1}* ist ein bekanntes offenes Problem. Definition: Alle Grammatiken sind automatisch vom Typ 0. Eine Typ-0 Grammatik ist vom Typ 1, wenn fuer jede Produktion x->y gilt: Entweder ist |x|<=|y| oder x=S und y=epsilon. In letzterem Fall darf S nicht auf der rechten Seite einer Produktion erscheinen. Typ-1 Grammatiken heissen auch kontextsensitiv. Eine Typ-1 Grammatik ist vom Typ 2, wenn fuer jede Produktion x->y gilt x:V. Typ-2 Grammatiken heissen auch kontextfrei. Eine Typ-2 Grammatik ist vom Typ 3, wenn fuer jede Produktion A->w gilt: w:Sigma u SigmaV Beispiel einer Typ-3 Grammatik: S -> a S -> aS L(G) = {a^n | n:N} = a* Beispiel einer Typ-2 Grammatik, die nicht auch Typ-3 ist: S -> ab S -> aSb L(G) = {a^nb^n | n:N} Anderes Beispiel: arithmetische Ausdruecke. V = {E,T,F} Sigma = {+, *, (, ), a} Startsymbol E. E -> T E -> E + T T -> F T -> T * F F -> a F -> (E) a*a*(a+a)+a : L(G) Beispiel einer Typ-1 Grammatik, die nicht auch Typ-2 ist: S -> aSBC S -> aBC CB -> BC aB -> ab bB -> bb bC -> bc cC -> cc L(G) = {a^nb^nc^n | n:N} Beispiel einer Typ-0 Grammatik, die nicht Typ-1 ist, s.o. Bemerkung: Bei Typ-2 und Typ-3 Grammatiken kann man Produktionen der Form A->epsilon fuer beliebige Nichtterminalsymbole erlauben, da solche stets systematisch eliminiert werden koennen. Beispiel: S -> bA A -> epsilon A -> aA kann ersetzt werden durch S -> bA S -> b A -> a A -> aA 1.3 Backus-Naur-Form: --------------------- Formalismus zur Abkuerzung von Typ-2 Grammatiken Statt A -> beta1 ... A -> betan schreibt man A -> beta1 | beta2 | ... | betan Statt A -> alpha.gamma A -> alpha.beta.gamma schreibt man A -> alpha[beta]gamma Statt A -> alpha.gamma | alphaBgamma B -> beta | betaB schreibt man A -> alpha{beta}*gamma (oder auch je nach Autor alpha{beta}gamma) Statt A -> alphaBgamma B -> beta | betaB schreibt man A -> alpha{beta}+gamma 1.4 Wortproblem --------------- Definition: Wortproblem. Das Wortproblem fuer eine Grammatik besteht darin, zu gegebenem Wort w:Sigma* zu entscheiden, ob w:L(G), oder nicht. Satz 1: Fuer kontextsensitive Sprachen ist das Wortproblem entscheidbar, d.h. es gibt einen Algorithmus, der bei vorgelegter Grammatik G und Wort w entscheidet, ob w:L(G) oder nicht. Beweis: Man erzeugt systematisch Ableitungen solange bis entweder das gewuenschte Wort erzeugt ist, oder bis nur noch laengere Woerter erzeugt werden. Etwas detaillierter: In einer Ableitung eines Wortes der Laenge n koennen nur Woerter der Laenge <=n vorkommen. Es gibt also auch nur endlich viele Ableitungen mit diesen Woertern, die kann man alle durchprobieren. Noch detaillierter: Man tabuliert iterativ die Mengen T^n_i aller Woerter der Laenge <=n, die in <=i Schritten ableitbar sind. Nachdem jede dieser Mengen Teilmenge der endlichen Menge der Woerter der Laenge <=n ist, muss irgendwann gelten T^n_i=T^n_i+1 (also formal: es existiert ein i0 sodass fuer alle i>=i0 gilt: T_i=T^n_i+1=T_i0) Beispiel: Sei n=4 und G wie in obigem Beispiel. T^n_0 = {S} T^n_1 = {S,aSBC,aBC} etc pp. 1.5 Syntaxbaeume ---------------- Ableitungen in Typ-2 (oder Typ-3) Grammatiken lassen sich als Baeume darstellen. Hierbei wird die Reihenfolge der Ersetzung gleichzeitig vorhandener Nichtterminalsymbole verwischt. Die auftretenden Nichtterminalsymbole befinden sich an den inneren Knoten. Die Kinder eines inneren Knotens werden jeweils mit den Symbolen (Terminal und Nichtterminal) beschriftet, zu denen die Knotenbeschriftung ersetzt wird. Beispiel: a*a*(a+a)+a (arithmetischer Ausdruck). Zu einem Ableitungsbaum gibt es i.a. mehrere Ableitungen. Diejenige, die immer das am weitesten links stehende Symbol ersetzt, bezeichnet man als Linksableitung (analog Rechtsableitung). Es kann auch vorkommen, dass ein Wort mehrere Ableitungsbaeume gestattet: Beispiel: E -> E + E | E * E | (E) | a Es war gerade der Zweck der Nichtterminalsymbole T, F diese Art der Mehrdeutigkeit aufzuloesen. Mehrdeutigkeiten sind nicht wuenschenswert, da die Semantik einer Phrase haeufig ausgehend vom Ableitungsbaum definiert wird. Syntaxanalyse: Eingabe: Wort, Ausgabe: zugehoeriger Ableitungsbaum oder Fehlermeldung. Syntaxanalyse kann fuer bestimmte Spezialfaelle der Typ-2 Grammatiken (LR(1)) besonders effizient durchgefuehrt werden und es existieren Spezialprogramme, die zu gegebener Grammatik ein Syntaxanalyseprogramm ("Parser") in C, Java, oder ML automatische erzeugen. Definition: Eine Grammatik G heisst mehrdeutig, wenn es ein Wort w:L(G) gibt, welches zwei verschiedene Ableitungsbaeume besitzt. 1.6 Sprachklassen ----------------- Eine Sprache, die von einer Typ-i Grammatik erzeugt werden kann heisst Typ-i Sprache. Die Sprache {a^nb^n | n:N} ist Typ-2 aber nicht Typ-1 Die Sprache {a^nb^nc^n | n:N} ist Typ-3 aber nicht Typ-2 Die Sprache aller terminierenden Java Programme ist Typ-0 aber nicht Typ-1 Eine Typ-2 Sprache heisst inhaerent mehrdeutig, wenn jede Grammatik fuer diese Sprache mehrdeutig ist. Inhaerente Mehrdeutigkeit ist eher eine Kuriositaet; ein Beispiel bildet die Sprache {a^ib^jc^k | i=j oder j=k} 2. Regulaere Sprachen und endliche Automaten ============================================ 2.1 Deterministische endliche Automaten --------------------------------------- Definition: Ein deterministischer endlicher Automat (DEA) ist gegeben durch ein 5-Tupel M = (Z, Sigma, delta, z0, E) wobei - Z (Zustaende), Sigma (Alphabet) sind endliche (disjunkte) Mengen. - delta : Z*Sigma -> Z ist die Zustandsueberfuehrungsfunktion. - z0:Z ist der Anfangszustand - E <= Z ist die Menge der Endzustaende. Automaten lassen sich anschaulich durch ihren Uebergangsgraphen darstellen. Dessen Knoten sind die Zustaende. Wenn delta(z,a)=z', so zeichnet man eine mit a beschriftete Kante von z nach z' ein. Beispiel: Z = {z0, z1, z2, z3} Sigma = {a,b} E = {z3} delta(z(i),x) = z(i+1) mod 4 falls x=a delta(z(i),x) = z(i-1) mod 4 falls x=b Man erweitert die Zustandsuebergangsfunktion auf Woerter durch delta(z,epsilon) = z delta(z,wx) = delta(delta(z,w),x) Definition: Die vom Automaten M erkannte Sprache L(M) ist definiert durch L(M) = {w:Sigma* | delta(z0,w) : E} Im Beispiel gilt L(M) = {w | |w|a - |w|b = 3 mod 4} Englisch: Deterministic Finite Automaton (DFA). Plural: Automata. DEA modellieren Berechnungen, die mit endlichem Speicher vonstatten gehen und bei denen die Eingabedaten einmal eingegeben werden, also nicht mehrfach gelesen werden koennen. Man kann sich also vorstellen, dass die Eingabedaten durch sequentielles Eintreten von Ereignissen (Knopfdruck, Sensorereignis) praesentiert werden. Beispiel: Drei Knoepfe "Schliessen" (s), "Aufmachen" (a), "Ruehren" (r). Man konstruiere einen Automaten, der alle Woerter erkennt, in denen mit offenem Deckel geruehrt wird. Wir brauchen drei Zustaende: "Zu" (z0), "Auf" (z1), "Fehler" (z2). Wir nehmen z1 als Anfangszustand und legen folgende Uebergaenge fest: delta(z0,s) = z0 delta(z1,s) = z0 delta(z2,s) = z2 delta(z0,a) = z1 delta(z1,a) = z1 delta(z2,a) = z2 delta(z0,r) = z0 delta(z1,r) = z2 delta(z2,r) = z2 E = {z2} Satz 2: Jede durch einen DEA erkennbare Sprache ist regulaer, also Typ 3. Beweis: Wir nehmen o.B.d.A an, dass der Startzustand z0 spaeter nicht mehr angenommen wird. Also delta(z,a) =/= z0 fuer alle z,a. Man kann einen Automaten stets so umbauen, dass diese Bedingung erfuellt ist. Wir nehmen nun die Zustaende des DEA als Nichtterminalsymbole. Das Startsymbol ist dann der Anfangszustand. Wenn delta(z,a) = z', so fuehren wir eine Produktion z -> az' ein. Ausserdem noch eine Produktion z -> a falls z':E. Ist w=a1a2a3...an in L(M), so gibt es eine Zustandsfolge z0,z1,...,zn wobei delta(z(i-1),ai) = zi und zn:E und z0=Anfangszustand. Dann ist aber z0 => a1z1 => a1a2z2 => ... => a1a2...an-1zn-1 => a1...an eine Ableitung von w. Liegt umgekehrt eine Ableitung vor, so muss diese von der o.a. Form sein und man liest den akzeptierenden Lauf im Automaten ab. 2.2 Nichtdeterministische endliche Automaten (NEA) -------------------------------------------------- Im folgenden werden wir "Automaten" betrachten, bei denen es zu gegebenem Zustand z und Symbol a eine (endliche) Menge moeglicher Folgezustaende gibt. Ist z.B. delta(z,a) = {z', z''}, so soll das folgendes bedeuten: Befindet sich der Automat im Zustand z und wird das Symbol a gelesen, so kann er entweder in den Zustand z' oder aber in den Zustand z'' uebergehen. Ein Wort w gilt als akzeptiert, wenn es moeglich ist, diese nichtdeterministischen Auswahlen bei der Abarbeitung von w so zu treffen, dass ein Endzustand erreicht wird. Zunaechst ein Beispiel: folgender nichtdeterministischer Automat erkennt alle Woerter, die mit 00 enden: delta(z0,1) = z0 delta(z0,0) = {z0,z1} delta(z1,0) = z2 E = {z2} Fuer diese Sprache gibt es auch einen deterministischen endlichen Automaten, der ist aber komplizierter. Definition: Ein nichtdeterministischer endlicher Automat (DEA) ist gegeben durch ein 5-Tupel M = (Z, Sigma, delta, S, E) wobei - Z (Zustaende), Sigma (Alphabet) sind endliche (disjunkte) Mengen. - delta : Z*Sigma -> Pow(Z) ist die Zustandsueberfuehrungsfunktion. - S <= Z ist die Menge der Startzustaende. - E <= Z ist die Menge der Endzustaende. Sei ein Wort w = a1..an gegeben. Ein Lauf M auf w ist gegeben durch eine Zustandsfolge z0,z1,...,zn wobei z0:S und zi:delta(zi-1,ai). Solch ein Lauf ist akzeptierend, wenn zn:E gilt. Der Automat akzeptiert ein Wort w, wenn es einen akzeptierenden Lauf des Automaten auf w gibt. Die Sprache L(M) des Automaten ist definiert als die Menge aller akzeptierten Woerter. 2.3 Determinisierung von NEA ---------------------------- Satz 3: Jede von einem NEA akzeptierte Sprache ist auch durch einen DEA akzeptierbar. Beweis: Durch Potenzmengenkonstruktion. Sei ein NEA M=(Z_M, Sigma, delta_M, S_M, E_M) vorgegeben. Wir konstruieren einen DEA M', dessen Zustaende die Mengen von Zustaenden von M ist, also Z_M' = Pow(Z_M). Als Anfangszustand waehlen wir S, die Menge der Startzustaende, die ja nunmehr ein Element von Z_M' ist. Die Uebergangsfunktion von M wird wie folgt festgelegt: delta(Z,a) = {z' | es existiert Zustand z:Z sodass z':delta(z,a)} Endzustaende von M' sind alle Zustandsmengen Z, die einen Endzustand enthalten. Wir moechten nun zeigen, dass L(M') = L(M). Sei w=a1a2...an ein Wort und S=Z0,Z1,...,Zn die Folge der "Zustaende" in M', die bei der Abarbeitung von w auftreten, also Zi = delta(Z(i-1),ai). Falls z0,z1,...,zn ein Lauf von M ist, also w:L(M), dann ist zi:Zi. Dies beweist man durch Induktion ueber i. Somit ist dann auch zn:Zn und damit Zn ein Endzustand. Es folgt L(M) <= L(M'). Nehmen wir nun umgekehrt an, dass w:L(M'), also dass ein Endzustand zn:Zn existiert. Wir konstruieren nun sukzessive eine Folge von Zustaenden zi:Zi, sodass schliesslich die Gesamtfolge z0,...,zn einen akzeptierenden Lauf bildet. Ist zi bereits konstruiert, so waehlen wir fuer z(i-1) ein Element von Z(i-1) derart dass zi:delta(z(i-1),a). Ein solches muss es nach Definition der Uebergangsfunktion von M' geben. Nachdem dann aber z0:S, ist klar, dass diese Folge einen akzeptierenden Lauf bildet und somit w:L(M) gilt. Als Beispiel konstruieren wir den DEA, der dem Beispielautomaten mit 3 Zustaenden fuer (0+1)*00 entspricht. Weiteres Beispiel: Lk = {w:{0,1}* | das k-letzte Zeichen von w ist 0} Ein NEA mit k+1 Zustaenden ist schnell angegeben, jedoch es gilt: Satz 4: Jeder DEA, der die Sprache Lk erkennt hat mindestens 2^k Zustaende. Beweis: Sei M ein Automat mit < 2^k Zustaenden. Es gibt zwei Woerter w1, w2 aus {0,1}^k, sodass delta(z0,w1) = delta(z0,w2). Sei nun i die erste Position, an der sich w1 und w2 unterscheiden, also o.B.d.A. w_1 = u0v_1 w_2 = u1v_2 wobei aber v_1 und v_2 die gleiche Laenge haben. Jetzt waehlen wir w beliebig, so dass |v_1w|=|v_2w|=k-1 sodass also w_1w : L_k aber w_2w nicht in L_k ist. Andererseits gilt aber delta(z0,w1w) = delta(delta(z0,w1),w) = delta(delta(z0,w2),w)=delta(z0,w2w). Hieraus folgt, dass L(M) nicht gleich Lk sein kann. 2.4 Aequivalenz von Typ-3 Grammatiken und Automaten --------------------------------------------------- Wir wissen bereits, dass jedem DEA eine aequivalente Typ-3 Grammatik zugeordnet werden kann (Satz 2). Ausserdem entspricht jedem NEA ein DEA (Satz 3). Fuer die Aequivalenz der drei Konzepte NEA, DEA, regulaere Sprachen genuegt es daher folgendes zu zeigen: Satz 5: Fuer jede regulaere (Typ-3) Grammatik G gibt es einen NEA M mit L(G)=L(M). Beweis: Sei die Grammatik G=(V,Sigma,P,S) gegeben. Wir konstruieren M=(Z,Sigma,delta,S',E) wie folgt: Z = V u {X} wobei X nicht in V. S' = {S} E = {S,X}, falls S->epsilon E = {X}, sonst. delta(A,a) = {B | A->aB} u {X | A->a} Sei w = a1..an =/= epsilon. Wenn w : L(G) vermoege einer Ableitung S=A1 => a1A2 => a1a2A3 => ... =>a1a2...an-1An => a1...an wobei also die Produktionen Ai->aiAi+1, sowie An->an benutzt wurden. Es ist dann S=A1,...,An,X ein Lauf von M auf w der in E endet, somit ist w:L(M). Ist umgekehrt w:L(M) vermoege des Laufs S=A1...An,X, dann muss gelten Ai->aiAi+1, sowie An->an und es ergibt sich eine Ableitung von w. Man beachte, dass S nicht auf der rechten Seite einer Produktion auftritt, falls S:E. Ist epsilon:L(G) so hat man eine Produktion S->epsilon und S:E. Ist umgekehrt epsilon:L(M), so ist X:E und wir haben eine Produktion S->epsilon, also epsilon:L(G). 2.5 Regulaere Ausdruecke ------------------------ Sei Sigma ein Alphabet. Die regulaeren Ausdruecke ueber Sigma sind durch die folgende BNF gegeben: <RegExp> ::= 0 | epsilon | (<RegExp>+<RegExp>) | (<RegExp><RegExp>) | a /* wobei a:Sigma */ | (<RegExp>)* Statt A+B schreibt man auch A|B. Man laesst Klammern weg unter der Massgabe, dass * staerker bindet als die Juxtaposition und diese wiederum staerker bindet als + und dass Juxtaposition und + nach links assoziieren. Zum Beispiel kuerzt man (((((a)*b)a)b)(a+b) + a) zu a*bab(a+b)+a ab. Jeder regulaere Ausdruck A bezeichnet eine Sprache L(A) ueber Sigma, die wie folgt rekursiv definiert ist: L(0) = 0 L(epsilon) = {epsilon} L(a) = {a} L(AB) = L(A)L(B) L(A+B) = L(A) u L(B) L(A*) = L(A)* = {w1...wn | wi:L(A), n>=0} Beispiel: Der regulaere Ausdruck 0 + (0+1)*00 bezeichnet die Sprache der Woerter, die mit 00 aufhoeren vereinigt mit dem Wort 0. Satz 6: Sei A ein regulaerer Ausdruck. Die Sprache L(A) ist regulaer. Beweis: Durch Induktion ueber A konstruieren wir einen NEA M mit L(M) = L(A). Fall a: A = 0 oder epsilon oder a. Das ist leicht. Fall b: A=B+C. Seien nach Induktionsannahme MB und MC Automaten mit L(MB)=B, L(MC)=C. Wir vereinigen die beiden Automaten disjunkt miteinander und erhalten so einen Automaten fuer A. Etwas detaillierter: Sei MB = (ZB,Sigma,deltaB,SB,EB) und MC = (ZC,Sigma,deltaC,SC,EC) und o.B.d.A. seien ZB und ZC disjunkt. Der gesuchte Automat fuer L(A) ist dann (ZB+ZC,Sigma,deltaB+deltaC,SB+SC,EB+EC). Fall c: A=BC. Wir moechten die Automaten in Serie schalten. Hierzu platzieren wir zwei disjunkte Kopien von MB und MC nebeneinander, d.h. wie im vorhergehenden Fall sind die Zustaende des neuen Automaten die Zustaende von MB und MC zusammen. Endzustaende sind diesmal nur die Endzustaende von MC, Anfangszustaende sind diesmal nur die Anfangszustaende von MB. Fuer jeden a-Uebergang von einem Zustand z:ZB in einen Zustand aus EB fuehren wir jeweils eine a-Kante von z in jeden der Anfangszustaende von MC ein. Ist epsilon:L(B), so werden zusaetzlich noch alle Startzustaende von MC zu Startzustaenden erklaert. Fall d: A=B*. Wir beginnen mit dem Automaten MB. Zunaechst fuehren wir einen neuen Zustand ein, der sowohl Anfangs- als auch Endzustand ist. Dadurch ist schonmal epsilon erkannt. Sodann fuehren wir fuer jeden a-Uebergang von einem Zustand z in einen Endzustand a-Uebergaenge von z in jeden Anfangszustand ein. Satz 7: Sei U regulaer. Dann existiert ein regulaerer Ausdruck A mit L(A)=U. Beweis: Sei U=L(M), wobei M ein DEA ist. OBdA sei ZM={1,2,...,n}. Fuer i,j,k <= n fuehren wir die folgende Sprache ein: R(i,j,k) = {a1...al | es gibt eine Zustandsfolge i=z0,z1,...,zl=j und fuer 1<t<l gilt zt <= k und delta(zi,ai+1)=zi+1} In R(i,j,k) sind also alle Woerter enthalten, die, wenn im Automaten ausgehend von i abgearbeitet nach j fuehren und ausserdem zwischendrin nur Zustaende <= k auftreten. Behauptung: Fuer R(i,j,k) gibt es einen regulaeren Ausdruck. Beweis durch Induktion ueber k. Induktionsanfang k=0. Hier ist R(i,j,k) endlich, da ueberhaupt keine Zwischenzustaende erlaubt sind. Induktionsschritt. Es gilt R(i,j,k+1) = R(i,j,k) + R(i,k+1,k)R(k+1,k+1,k)*R(k+1,j,k). Hiermit folgt die Behauptung. Nun ist aber L(M) = U_{j:E} R(z0,j,n). Beispiel: Sei L die Sprache aller Woerter ueber {0,1}, die eine ungerade Zahl von Einsen enthalten. Aus dem offensichtlichen DEA mit zwei Zustaenden kann man mithilfe des Beweises des Satzes folgenden regulaeren Ausdruck fuer L ableiten: 0*1 + 0*1(10*1 + epsilon + 0)* Eine manchmal effizientere Konstruktion verwendet die Ardensche Regel: Satz 8 (Ardensche Regel): Seien A, B Sprachen ueber Sigma, wobei epsilon nicht in A. Dann hat die Gleichung X = AX+B die eindeutige Loesung X = A*B. Beispiel: LE = 0.LE + 1.LO LO = 0.LO + 1.LE + epsilon LO = 0*(1.LE + epsilon) LE = 0.LE + 1.(0*(1.LE + epsilon)) = (0 + 10*1)LE + 10* Also LE = (0+10*1)* 10* LO = ... Beweis der Ardenschen Regel: Sei epsilon nicht in A. Sei X=A*B. Falls w:A*B, so ist auch w:AA*B, also auch AA*B+B. Ist umgekehrt w:AX+B, so folgt w:X. Sei nun X eine beliebige Loesung der Gleichung X=AX+B. Seien u1..un Woerter aus A und v:B. Wir zeigen durch Induktion ueber n, dass w=u1...unv:X. Falls n=0, so ist w=v:B, also w:X, da ja B<=X. Anderenfalls ist mit Induktionshypothese u2..unv:X, somit w:AX, somit w:X, da ja AX<=X. Sei nun schliesslich w:X beliebig. Nachdem epsilon nicht in A ist, muss entweder w:B sein, oder aber ein Praefix aus A haben, sich also in der Form uw' schreiben lassen mit u:A, w':X und |w'|<|w|. Induktion ueber die Wortlaenge zeigt w':A*B und somit auch w:A*B. 2.6 Pumping Lemma ----------------- Mit dem Pumping Lemma kann man beweisen, dass eine gegebene Sprache nicht regulaer ist. Beginnen wir mit einem Beispiel. Satz 9: Die Sprache L={a^nb^n | n>=1} ist nicht regulaer. Beweis: Waere L regulaer, so gaebe es einen DEA M mit L(M)=L. Sei n groesser als die Zahl der Zustaende von M. Sei w=a^nb^n. Sicherlich ist w:L, also muss gelten delta(z0,w):E. Da nun aber weniger als n Zustaende vorhanden sind, muss schon beim Verarbeiten des a-Blockes von w' ein Zustand zweimal angefahren worden sein, d.h. es existieren i<j <= n mit delta(z0,a^i) = z1 delta(z1,a^j)) = z2 delta(z2,a^(n-j+i)b^n) : E Wir setzen jetzt w_k := a^(n-d+kd)b^n wobei d=j-i und k>=0. Es gilt delta(z0,w_k)=delta(z0,w):F, somit werden alle w_k von M akzeptiert, andererseits sind aber w_0, w_2, w_3, ... nicht in L, weswegen also L(M) nicht gleich L sein kann. Damit ist gezeigt, dass kein DEA die Sprache L erkennen kann. W.z.b.w. Intuitiv ist klar, dass L nicht regulaer sein kann; ein DEA hat ja nur einen endlichen Speicher; um zu testen, ob ein gegebenes Wort in L ist, muss man sich aber die potentiell unbeschraenkte Zahl der a's merken, die bis zum ersten b gegeben wurden. Das Pumping Lemma verpackt diese Argumentationsweise in eine allgemein verwendbare Form: Satz 10 (Pumping Lemma): Sei L regulaere Sprache. Dann existiert eine Zahl n:N mit der folgenden Eigenschaft: Fuer alle Woerter w:L mit |w|>=n gibt es eine Zerlegung w=uxv so dass |ux|<=n und fuer alle k>=0 ist ux^kv:L Beweis: Sei L regulaer und folglich M ein DEA fuer L. Sei weiter n eine natuerliche Zahl groesser als die Zustandszahl von M. Wir behaupten, dass mit dieser Wahl von n die Aussagen des Pumping Lemma erfuellt werden koennen. Sei hierfuer also w:L. Bei der Abarbeitung der ersten n Buchstaben von w muss ein Zustand, sagen wir z1, doppelt verwendet werden. Wir koennen also w zerlegen als w=uxv mit |ux|<=n, sodass delta(z0,u)=z1 delta(z1,x)=z1 delta(z1,v):E Hiermit folgt aber, dass auch delta(z0,ux^kv)=delta(z1,v):E, somit ux^kv:L, w.z.b.w. 2.7 Aequivalenzrelationen und Minimalautomaten ---------------------------------------------- Sei ein DEA M=(Z,Sigma,delta,z0,E) gegeben. Wir definieren eine Aequivalenzrelation R_M auf Sigma* wie folgt: w1 R_M w2 <==> delta(z0,w1) = delta(z0,w2) Es gelten also zwei Woerter als gleich, wenn der Automat sie nicht voneinander unterscheiden kann. Insbesondere gilt: Beobachtung: Falls w1 R_M w2, so gilt fuer alle v:Sigma*: w1v : L(M) genau dann wenn w2v : L(M) Weiterhin kann man beobachten, dass die Aequivalenzklassen dieser Relation in 1-1 Beziehung zu den von z0 aus erreichbaren Zustaenden des Automaten sind: ist z:Z, so bildet man die Aequivalenzklasse k_z = {w | delta(z0,w)=z}. Diese Menge ist nichtleer genau dann wenn z erreichbar ist. Hat man umgekehrt eine Aequivalenzklasse durch einen Repraesentanten w gegeben, so assoziiert man den Zustand delta(z0,w). Dieser Zustand ist von der Wahl des Repraesentanten unabhaengig. Es liegt nun nahe, die erste Beobachtung zur Definition zu erheben: Definition: Sei L <= Sigma* eine beliebige Sprache. Die mit L assoziierte Aequivalenz R_L<=Sigma* x Sigma* ist wie folgt definiert: w1 R_L w2 <==> fuer alle v:Sigma*.w1v:L <=> w2v:L Die obige Beobachtung impliziert nun den folgenden Satz: Satz 11: Sei M DEA und L=L(M) die von M erkannte regulaere Sprache. Die Aequivalenz R_M ist feiner als R_L. Es gilt R_M <= R_L, also w1 R_M w2 => w1 R_L w2. Gilt fuer Aequivalenzrelationen R1 und R2 dass R1 <= R2, so sind die Aequivalenzklassen von R2 Vereinigungen von Aequivalenzklassen von R1. Daraus ergibt sich Satz 12: Eine Sprache L <= Sigma* ist genau dann regulaer, wenn die Aequivalenz R_L endlich viele Aequivalenzklassen hat. Beweis: Ist L regulaer, so gibt es einen DEA M fuer L, der endlich viele Zustaende hat. Diese Zustaende sind aber (bis auf Isomorphie) gerade die Aequivalenzklassen von R_M. Letztere Relation hat also auch endlich viele Aequivalenzklassen. Nach dem R_L eine Vergroeberung von R_M ist, folgt insbesondere, dass auch R_L endlich viele Aequivalenzklassen hat. Hat umgekehrt R_L endlich viele Aequivalenzklassen, so kann man diese als Zustaende eines Automaten nehmen: Wir definieren einen DEA M durch M = (Sigma* / R_L, Sigma, delta, [epsilon], E) wobei delta([w], a) = [wa] und E = { [w] | w:L} Wir schreiben hier [w] fuer die Aequivalenzklasse des Wortes w. Hierzu ein paar Anmerkungen: 1) Es gilt w1 R_L w2 ==> w1a R_L w2a, somit ist delta auf Aequivalenzklassen wohldefiniert. 2) Es gilt w1 R_L w2 ==> w1:L<=>w2:L, somit ist die Menge E der Endzustaende wohldefiniert. Nun sieht man sofort durch Induktion ueber |v|, dass delta([u],v) = [uv] und somit delta(z0,w) = [w]. Damit folgt L(M)=L. QED Hat eine Aequivalenzrelation endlich viele Aequivalenzklassen, so sagt man auch, sie sei von endlichem Index. Der im Beweis verwendete Aequivalenzklassenautomat fuer eine regulaere Sprache L hat die minimale Zustandszahl unter allen Automaten M mit L(M)=L, da ja seine Zustaende Vereinigungen von Aequivalenzklassen von R_M, also Verschmelzungen von Zustaenden von M sind. Mit folgendem Algorithmus kann man ausgehend von einem DEA M den Aequivalenzklassenautomaten M' fuer L(M) berechnen. Zustaende, die nicht erreichbar sind, entfernen. Aequivalente Zustaende verschmelzen. Hierbei sind zwei Zustaende z1, z2 aequivalent, wenn gilt delta(z1,w):E <==> delta(z2,w):E Um dies effektiv auszurechnen, betrachtet man stattdessen die Inaequivalenz: Zwei Zustaende z1, z2 werden auseinandergehalten, i.Z. z1 # z2, wenn eine der folgenden Bedingungen erfuellt ist: *) z1:E und z2 nicht in E, *) z1 nicht in E und z2 in E, *) es existiert a:Sigma, sodass delta(z1,a)#delta(z2,a). Legt man nun eine Tabelle an mit einem Eintrag fuer jedes Zustandspaar (z1,z2), so kann man durch sukzessives Anwenden der drei Regeln alle Paare (z1,z2) markieren, fuer die gilt z1#z2. Alle Zustandspaare, die nicht markiert worden sind, koennen nunmehr verschmolzen werden. Aufgrund der ersten beiden Regeln wird niemals ein End- mit einem Nichtendzustand verschmolzen. 2.8 Abschlusseigenschaften -------------------------- Satz 13: Sind A, B regulaere Sprachen ueber einem Alphabet Sigma, so sind auch die folgenden Sprachen regulaer: 1) A + B (Vereinigung) 2) AB (Konkatenation) 3) A* 4) Sigma* \ A (Komplement) 5) A geschnitten mit B 6) A \ B Beweis: 1,2,3) Dies wurde schon im Beweis von Satz 6 gezeigt: Aus NEA's fuer A und B konstruiert man NEA's fuer die unter 1, 2, 3 genannten Sprachen. 4) Um einen Automaten fuer Sigma* \ A zu erhalten geht man von einem DEA M=(Z,Sigma,delta,z0,E) fuer A aus. Nun ist aber M'=(Z,Sigma,delta,z0,Z\E) ein Automat fuer Sigma*\A, da ja alle Woerter aus Sigma*\A in einen Nicht-Endzustand, also einen Zustand in Z\E fuehren. Man beachte, dass dies nur bei deterministischen Automaten funktioniert. Will man also eine durch einen NEA gegebene Sprache komplementieren, so muss der NEA zunaechst determinisiert werden. 5) Dies folgt aus 1, 4 mit dem de Morganschen Gesetz A geschnitten B = ~(~A+~B). Alternativ kann aus NEA M1=(Z1,Sigma,delta1,S1,E1) und M2=(Z2,Sigma,delta2,S2,E2) ein NEA M3 fuer A geschnitten mit B wie folgt konstruiert werden: M3=(Z1*Z2,Sigma,delta3,S1*S2,E1*E2) wobei delta3((z1,z2),a) = delta3(z1,a)*delta3(z2,a). Es gibt also eine mit a beschriftete Kante von (z1,z2) nach (z1',z2'), wenn z1-a->z1' und z2-a->z2'. 6) Dies folgt aus 4,5. 2.9 Entscheidbarkeitsfragen --------------------------- Die folgenden Probleme sind entscheidbar, d.h. es existieren Algorithmen. 1) Leerheitsproblem: Sei M ein NEA. Ist L(M)=0? 2) Aequivalenzproblem: Seien M1, M2 NEA. Ist L(M1)=L(M2)? 3) Aequivalenzproblem fuer regulaere Ausdruecke: Seien A1, A2 regulaere Ausdruecke. Ist L(A1)=L(A2)? 4) Universalitaetsproblem: Sei M ein NEA: Ist L(M)=Sigma*? 3. Kontextfreie Sprachen ======================== Wdh.: Typ-2 Grammatik (= kontextfreie Grammatik): Chomsky Grammatik so dass: 1) Alle Produktionen sind von der Form X -> alpha wobei alpha : (V u Sigma)* 2) Hat man eine Produktion X -> epsilon, so muss gelten X=S und ausserdem darf dann S nicht auf den rechten Seiten auftauchen. Eine Grammatik, die der Bedingung 1 genuegt kann in eine aequivalente kontextfreie Grammatik ueberfuehrt werden. Hierzu bestimmt man systematisch die Menge V1 aller Nichtterminalsymbole X fuer die gilt X->* epsilon. Fuer jede Produktion Y->alphaXbeta mit X:V1 fuehrt man dann eine zusaetzliche Produktion Y->alphabeta ein. Anschliessend kann man alle Produktionen der Form X->epsilon entfernen und hoechstens, falls epsilon:L(G), eine Produktion S->epsilon einfuehren. Typisches Beispiel einer kontextfreien Grammatik: V = {E,T,F} Sigma = {+, *, (, ), a} Startsymbol E. E -> T E -> E + T T -> F T -> T * F F -> a F -> (E) a*a*(a+a)+a : L(G) 3.1: Chomsky Normalform: ------------------------ Def.: Eine Typ-2 Grammatik G mit epsilon nicht in L(G) ist in Chomsky Normalform, wenn jede Produktion eine der folgenden beiden Formen besitzt: 1) X -> YZ 2) X -> a wobei X,Y,Z:V und a:Sigma. Satz 14: Zu jeder Typ-2 Grammatik G mit epsilon nicht in L(G) existiert eine Grammatik G' in Chomsky NF mit L(G)=L(G'). Beweis: 1.) Eliminieren von Produktionen der Form X->Y 2.) Einfuehren kuenstlicher Nichtterminalsymbole, dadurch erhalten alle Produktionen die Form 1) oder 2'): X->Y1Y2...Yl. 3.) Durch weiteres Einfuehren zusaetzlicher NT erhaelt man die CNF. Beispiel: S->AB, A->ab|aAb, B->c|cB In CNF: S->AB, A->CD|CF, B->c|EB, C->a 3.2 Pumping Lemma ----------------- Satz 15: Pumping Lemma: Sei L eine Typ-2 Sprache. Dann existiert eine Zahl n:N, die Pumpingzahl zu L, sodass jedes Wort z:L mit |z| >= n eine Zerlegung der Form z = uvwxy mit den folgenden Eigenschaften gestattet: *) |vx| >= 1 *) |vwx| <= n *) Fuer alle i>=0 gilt: uv^iwx^iy : L Beweis: Sei G eine Grammatik in CNF mit L(G)=L und sei m die Zahl der Nichtterminalsymbole von G. Wir setzen n = 2^m. Sei z ein Wort in L mit |z| >= 2^m = n. Ein Ableitungsbaum von z hat |z| also >= 2^m Blaetter, wobei hier ein Blatt aus einer (1-Schritt) Ableitung X->a besteht, sodass sich in den Blaettern jeweils ein Nichtterminal- und ein Terminalsymbol befindet. Daher muss es einen Pfad der Laenge mindestens m von S zu einem solchen Blatt geben, auf welchem sich also mindestens m+1 Nichtterminalsymbole befinden muessen. Beispiel: S->X2->X3->a ist ein Pfad der Laenge 2, auf dem sich 3 Nichtterminalsymbole befinden. Nachdem es nur m Nichtterminalsymbole gibt, muss auf diesem Pfad mindestens ein Symbol doppelt auftreten. Sei X dieses Symbol. Man hat also Ableitungen S =>* uXy, X =>* vXx, X=>*w, wobei z=uvwxy und |vx|>=1. Waehlt man X als die erste Wdh eines Nichtterminalsymbols von unten gesehen, so gilt |uwx|<=n. Es ist nun aber klar, dass auch uv^iwx^iy fuer alle i>=0 herleitbar sind. QED Anwendungsbeispiel: Die Sprache L = {a^nb^nc^n | n>= 0} ist nicht kontextfrei. Falls doch, so gaebe es die Pumpinglemmazahl n. Waehlt man z=a^nb^nc^n, so bekommt man eine Zerlegung z=uvwxy mit |vwx|<=n. Daher sind in vwx nicht alle drei Buchstaben a,b,c, vorhanden. Ein Aufpumpen wird daher die Balance der drei Buchstabenarten zerstoeren und Woerter produzieren, die nicht in der Sprache L sind. Ein Widerspruch. Satz 16: Eine Typ-2 Sprache L ueber einelementigem Alphabet {a} ist regulaer. Beweis: Siehe Schoening. Man beachte, dass ein Wort ueber einelementigem Alphabet nichts anderes als eine natuerliche Zahl ist. Sei n die Pumpingzahl zu L. Ist a^m:L, so gibt es eine Zerlegung m = k+l sodass auch a^(k+il) : L fuer alle i. 3.3 Abschlusseigenschaften, siehe unten --------------------------------------- 3.4 Der CYK Algorithmus ----------------------- Benannt nach den Erstbeschreibern Cocke-Younger-Kasami. Sei G = (V,Sigma,P,S) eine Typ-2 Grammatik in Chomsky Normalform. Um festzustellen, ob ein gegebenenes Wort w in L(G) liegt, kann man folgendes rekursives Verfahren probieren: Fuer i<=j<=|w| und X:V definieren wir | true, falls X ->* w_i,...,w_j Abl(X,i,j) = < | false, sonst Klarerweise ist w:L(G), falls Abl(S,1,|w|) = true. Die Funktion Abl kann nun wie folgt rekursiv definiert werden: Fall i=j: Es ist Abl(X,i,j) = true genau dann wenn die Produktion X=>w_i in P vorhanden ist. Fall i<j: Es ist Abl(X,i,j) = true genau dann wenn es eine Produktion X => YZ gibt und ausserdem ein Index k mit i<=k<j existiert, sodass Abl(Y,i,k) und Abl(Z,k+1,j) gilt. Es gibt nun insgesamt nur O(|V|*|w|*|w|) viele moegliche Aufrufe der Funktion Abl, sodass es sich wieder (wie schon bei der Berechnung eines regulaeren Ausdrucks aus einem DEA) anbietet, bereits berechnete Abl-Werte in einer Merktabelle abzuspeichern und aus dieser bei abermaliger Verwendung abzurufen. Hierdurch wird die Rechenzeit auch auf O(|V|*|n|*|n|) abgesenkt. Eine besonders effiziente Version fuellt die Merktafel ohne jede Rekursion gleich iterativ von unten aus; das ist der CYK Algorithmus benant nach seinen Entdeckern Cocke, Younger und Kasami. CYK Algorithmus: Eingabe: eine Grammatik G = (V,Sigma,P,S) in CNF und ein Wort w. Ausgabe: true, falls w:L(G), false sonst. Sei n = |w|. Lege ein Array T der Groesse n^2 an, dessen Eintraege Mengen (oder Listen) von Nichtterminalsymbolen sind. Initialisiere T[i,j] = {} fuer i,j=1..n. Fuer i = 1..n Setze T[i,i] = {X | X->w_i in P} Fuer d=1..n-1 Fuer i=1..n-d Setze j = i+d Setze T[i,j] = {X | es existiert k mit i<=k<j und Y in T[i,k] und Z in T[k+1,j] mit X=>YZ in P} Falls S:T[1,n]: Ausgabe true Ansonsten: Ausgabe false. Beispiel aus Wikipedia: Sei G die folgende Grammatik: S->AB|BC, A->BA|a, B->CC|b, C->AB|a Ausserdem w = bbabaaa. ------ j ------> b b a b a a a 1 2 3 4 5 6 7 | b 1 B - A S,C B S,A B | b 2 B S,A S,C B S,A B | a 3 A,C S,C B S,A B i b 4 B S,A - S,A,C | a 5 A,C B S,A,C V a 6 A,C B a 7 A,C Man liest ab: w ist nicht in L, aber B =>* w. Ausserdem gilt S =>* bbabaa. 3.5 Kellerautomaten ------------------- Das den Typ-2 Grammatiken (und Sprachen) entsprechende Automatenmodell ist der Kellerautomat. Ein solcher hat zusaetzlich zum beschraenkten (von der Eingabelaenge unabhaengigen) Speicher eines DEA oder NEA einen unbeschraenkten Keller zur Verfuegung auf dem er nach Massgabe der Eingabe und des Zustands schreiben und lesen kann. Wie bei Kellern ueblich, darf nur das oberste Kellersymbol gelesen werden. Wie die endlichen Automaten sind die Kellerautomaten im allgemeinen nichtdeterministisch. Definition: Ein Kellerautomat (PDA) ist ein Sextupel M=(Z,Sigma,Gamma,delta,z0,#) wobei folgendes gilt: Z, Sigma, Gamma sind endliche Mengen Z ist die Menge der Zustaende z0:Z ist der Anfangszustand Sigma ist das Eingabealphabet (der Automat erkennt Woerter ueber Sigma) Gamma ist das Kelleralphabet (die Symbole aus Gamma koennen auf dem Keller abgelegt werden) delta : Z * (Sigma u {epsilon}) * Gamma -> Pfin(Z * Gamma*) ist die Uebergangsrelation. Hierbei ist Pfin(X) die Menge der endlichen Teilmengen der Menge X. # : Gamma ist der initiale Kellerinhalt. Intuitiv bedeutet (z',alpha) : delta(z,a,X), dass der Automat im Zustand z, bei oberstem Kellersymbol X und bei naechstem Eingabesymbol a die Moeglichkeit hat, in den Zustand z' ueberzugehen und das oberste Kellersymbol X durch das Wort alpha zu ersetzen. Ist dagegen (z',alpha) : delta(z,epsilon,X), so bedeutet das, dass bei oberstem Kellersymbol X und Zustand z spontan in den Zustand z' uebergegangen werden kann wobei gleichzeitig das Symbol X durch alpha ersetz wird. Zu Beginn enthaelt der Keller nur das Symbol #; ist der Keller leer und gleichzeitig die Eingabe aufgebraucht, so gilt die Eingabe als akzeptiert. Kann kein weiterer Uebergang getaetigt werden, oder ist die Eingabe aufgebraucht ohne dass der Keller leer ist, so gilt die Eingabe als verworfen. Die erkannte Sprache L(M) ist die Menge aller Woerter, fuer die es einen akzeptierenden Lauf des Automaten gibt. Dies wollen wir nunmehr formalisieren. Definition. Sei M=(Z,Sigma,Gamma,delta,z0,#) ein PDA. Eine Konfiguration ist ein Tripel (z,w,alpha), wobei z:Z, w:Sigma*, alpha:Gamma*. Die binaere Relation |- auf Konfigurationen wird wie folgt definiert: (z,w,gamma) |- (z',w',gamma') <====> es existieren a:Sigma u {epsilon}, alpha : Gamma*, X : Gamma, beta : Gamma* sodass (z',alpha) : delta(z,a,X) und w = aw', gamma = Xbeta, gamma'=alpha.beta Nun definieren wir L(M) = {w | (z0,w,#) |-* (z,epsilon,epsilon) fuer ein z:Z} Ende der Definition. Intuitiv beschreibt eine Konfiguration (z,w,gamma) den momentanen globalen Zustand des PDA durch den Zustand z seiner endlichen Kontrolleinheit, die verbleibende Eingabe w und den Inhalt seines Kellers gamma. Der PDA akzeptiert ein Wort, wenn er ausgehend von der zu diesem Wort gehoerenden Anfangskonfiguration den leeren Keller erreicht und dabei die Eingabe ganz verarbeitet. Satz 19: Sei G=(V,Sigma,P,S) eine Typ-2 Grammatik. Es existiert ein PDA M = (Z,Sigma,Gamma,delta,z0,#) mit L(M)=L(G). Beweis: Wir waehlen Z={z0} alos nur ein Zustand und Gamma = Sigma u V. Nunmehr setzen wir delta(z0,epsilon,X) = {(z0,alpha) | X->alpha : P} delta(z0,a,b) = if a=b then {(z0,epsilon)} else {} # = S Man zeigt nun leicht, dass L(M) = L(G) unter Verwendung der folgenden Invariante: von der Konfiguration (z0,w,alpha) kann der Automat akzeptieren genau dann, wenn alpha =>* w. QED Wir wollen uns die Funktionsweise des Kellerautomaten noch einmal intuitiv veranschaulichen. Zu Beginn legen wir also Startsymbol S in den Keller. Solange der Keller nicht leer ist, tun wir folgendes: Ist das oberste Kellersymbol ein Nichtterminalsymbol X, so waehlen wir (nichtdeterministisch) eine Produktion X->alpha und ersetzen X durch alpha (man entfernt X und legt dann der Reihe nach die Symbole von alpha in den Keller). Ist das oberste Kellersymbol ein Terminalsymbol, so wird das naechste Eingabezeichen gelesen. Stimmt es mit diesem ueberein, so wird es entfernt. Stimmt es nicht ueberein, so wird die Eingabe verworfen. Ist der Keller leer und gleichzeitig die Eingabe aufgebraucht, so ist diese akzeptiert. In allen anderen Faellen wird die Eingabe verworfen. Beispiel: S -> ab|aSb Eingabe aaabbb. Kellerinhalt noch zu verarbeitende Eingabe S aaabbb aSb aaabbb Sb aabbb aSbb aabbb Sbb abbb abbb abbb bbb bbb bb bb b b Der Keller ist leer; die Eingabe auch: Die Eingabe wird akzeptiert. Natuerlich haette bei weniger geschickter Wahl der nichtdeterministischen Entscheidungen die Eingabe auch verworfen werden koennen. Wie bei den NEA gilt aber eine Eingabe als vom Automaten akzeptiert, wenn es einen akzeptierenden Lauf gibt. In diesem Fall koennte auch ein deterministischer Kellerautomat die Sprache erkennen: man liest einfach von der Eingabe a's und packt sie in den Keller. Wenn dann b's kommen, so entfernt man vom Keller entsprechend die a's. Es gibt aber Typ-2 Sprachen, die nicht durch einen deterministischen Kellerautomaten erkannt werden koennen. Satz 20: Sei M=(Z,Sigma,Gamma,delta,z0,#) ein PDA. Es existiert eine Typ-2 Grammatik mit L(G)=L(M). Beweis: Wir koennen o.B.d.A. annehmen, dass (z',alpha):delta(z,a,X) impliziert |alpha|<=2. Fuer z,z':Z und X:Gamma definieren wir L(z,X,z') = {w:Sigma* | (z,w,X) |-* (z',epsilon,epsilon)} Die so definierte Sprache L(z,z',X) besteht also aus allen Woertern, die der Automat ausgehend vom Zustand z und Kellerinhalt X akzeptiert mit der zusaetzlichen Massgabe, dass am Ende neben dem leeren Keller der Zustand z' erreicht ist. Es gilt L(M) = U_(z:Z) L(z0,#,z). Die Sprachen L(z,X,z') erfuellen aber eine Rekurrenz, die sich unmittelbar in eine Typ-2 Grammatik uebersetzen laesst: L(z,X,z') = {a | (z',epsilon):delta(z,a,X)} + {aw | (z1,Y):delta(z,a,X), w:L(z1,Y,z')} + {aw1w2 | (z1,YZ):delta(z,a,X), w1:L(z1,Y,z2), w2:L(z2,Z,z')} In allen Klauseln ist a:Sigma u {epsilon}. Zur letzten Klausel: Um YZ vom Keller wegzukriegen muss zunaechst Y und anschliessend Z entfernt werden. Aus dieser Definition ergibt sich unmittelbar, dass alle L(z,X,z') kontextfrei sind. Hier ist der Vollstaendigkeit halber eine Grammatik. Als Nichtterminalsymbole waehlen wir die L(z,X,z') und zusaetzlich ein Startsymbol S. Die Produktionen sind wie folgt: S -> L(z0,#,z) fuer jeden z:Z. L(z,X,z') -> a fuer alle a sodass (z',epsilon):delta(a,z). L(z,X,z') -> aL(z1,Y,z') fuer alle a,z1,Y mit (z1,Y):delta(a,z). L(z,X,z') -> aL(z1,Y,z2)L(z2,Z,z') fuer alle a,z1,z2,Y,Z mit (z1,YZ):delta(a,z) QED 3.3 Abschlusseigenschaften -------------------------- Satz 17: Seien A, B kontextfreie Sprachen. Es sind auch A u B, AB, A* kontextfreie Sprachen. Beweis: Durch explizite Angabe von Grammatiken (leicht). Satz 18: Die kontextfreien Sprachen sind weder unter Durchschnitt, noch unter Komplement abgeschlossen. Beweis: Seien L1 = {a^ib^jc^j | i,j>0}, L2 = {a^ib^ic^j | i,j>0}. Wir wissen, dass L1 geschnitten mit L2 nicht kontextfrei ist. Andererseits sieht man leicht, dass L1 und L2 fuer sich genommen kontextfrei sind. Somit sind die Typ-2 Sprachen also nicht unter Durchschnitt abgeschlossen. Nun ist aber der Durchschnitt aus Vereinigung und Komplement definierbar mithilfe der de Morgan'schen Regel. Da aber die kontextfreien Sprachen unter Vereinigung abgeschlossen sind, koennen sie nicht gleichzeitig auch unter Komplement abgeschlossen sein. Wir bemerken noch, dass diejenigen Sprachen, die von deterministischen Kellerautomaten erkannt werden, das sind die deterministischen kontextfreien Sprachen, unter Komplement abgeschlossen sind (wie das in der Regel bei deterministischen Automaten der Fall ist) und in den Typ-2 Sprachen echt enthalten sind. Z.B. ist die Sprache der Palindrome nicht deterministisch kontextfrei. Deterministisch kontextfreie Sprachen sind praktisch relevant, da ein deterministischer Kellerautomat ein effizientes Erkennungsverfahren bietet (lineare Laufzeit im Gegensatz zur kubischen Laufzeit des CYK Algorithmus). Gern werden die erforderlichen deterministischen Kellerautomaten dann in der LR(k)-Form praesentiert. Hierbei geht man vom nichtdeterministischen Kellerautomaten aus und stattet diesen mit einer zusaetzlichen Steuerungseinheit aus, die aufgrund des Kellerinhalts und der k naechsten Eingabesymbole (k lookahead) ermittelt, welche Produktion zu waehlen ist. Diese Steuerungseinheit besteht selbst wiederum aus einem DEA, der auf dem Kellerinhalt operiert. Details im Compilerpraktikum. 4. Kontextsensitive und Typ-0 Sprachen ====================================== Ein Automatenmodell fuer Typ 1 Sprachen muss noch allgemeiner als die PDA sein. Es bietet sich an, gleich das Automatenmodell fuer die Typ-0 Sprachen, naemlich die Turingmaschine vorzustellen und dann ein Automatenmodell fuer Typ-1 als Einschraenkung letzterer zu formulieren. 4.1 Turingmaschinen ------------------- Eine Turingmaschine (kurz TM) kann als endlicher Automat mit zusaetzlichem unbegrenzten Schreib-Lese-Speicher verstanden werden, der also nicht wie beim PDA einer besonderen Zugriffsdisziplin unterworfen ist. Man formalisiert das durch ein unendliches Band, dessen Felder aber bis auf endlich viele ein Leerzeichen enthalten. Auf diesem Band operiert ein Schreib-Lese-Kopf, der durch eine endliche Kontrolleinheit gesteuert wird. Nach Massgabe des internen (endlichen) Zustands und des Bandinhalts unter dem Schreib-Lese-Kopf kann dann dieser Bandinhalt ueberschrieben werden, eine Zustandsaenderung herbeigefuehrt werden und der Schreib-Lese-Kopf nach links oder rechts bewegt werden, bzw auch an Ort und Stelle verbleiben. Definition: Eine Turingmaschine ist ein Septupel M = (Z,Sigma,Gamma,delta,z0,[],E), wobei folgendes gilt: * Z ist eine endliche Menge, die Zustandsmenge * Sigma ist eine endliche Menge, das Eingabealphabet * Gamma ist eine endliche Menge, das Bandalphabet. Letzteres muss eine Obermenge von Sigma sein. * z0:Z ist der Anfangszustand. * []:Gamma ist das Leerzeichen. Das Leerzeichen darf kein Element von Sigma sein. * E <= Z ist die Menge der Endzustaende. * delta : Z * Gamma -> Pow(Z * Gamma * {L,R,N}) ist die Zustanddsueberfuehrungsfunktion. Eine Konfiguration einer Turingmaschine ist ein Tripel k = (wl,z,wr). Hierbei bezeichnet kl den Bandinhalt links des Schreib-Lese-Kopfes ausschliesslich der gerade besuchten Position und wr den Bandinhalt rechts des Schreiblesekopfes einschliesslich der gerade besuchten Position. Falls (o.B.d.A) Z und Gamma disjunkt sind, schreibt man gerne k=wlzwr. Das Wort wr darf hierbei nicht leer sein. Die zweistellige Relation |- auf der Menge der Konfigurationen ist erklaert durch: / (a1..am,z',c b2..bn), falls | (z',c,N):delta(z,b1), m>=0,n>=1 | | (a1..am c,z',b2..bn), falls (a1..am,z,b1..bn) |- | (z',c,R):delta(z,b1), m>=0,n>=2 | | (a1..am-1,z',am c b2..bn), falls | (z',c,L):delta(z,b1), m>=1,n>=1 \ Ausserdem gibt es noch die folgenden beiden Sonderfaelle: a1..amzb1 |- a1..amcz'[], falls (z',c,R):delta(z,b1) zb1..bn |- z'[]cb2..bn, falls (z',c,L):delta(z,b1) Sie beschreiben, dass sich links von den a's und rechts von den b's Leerzeichen befinden. Definition: Eine Turingmaschine ist deterministisch, wenn |delta(z,b)| = 1 fuer alle z:Z, b:Gamma. In diesem Falle schreibt man auch delta(z,b) = (z',c,D) statt delta(z,b) = {(z',c,D)}. Beispiel: Folgende Turingmaschine interpretiert eine Eingabe ueber Sigma={0,1} als Binaerzahl und addiert 1 hinzu. M = ({z0,z1,z2,ze},{0,1},{0,1,[]},delta,z0,[],{ze}). wobei delta(z0,0) = (z0,0,R) delta(z0,1) = (z0,1,R) delta(z0,[]) = (z1,[],L) delta(z1,0) = (z2,1,L) delta(z1,1) = (z1,0,L) delta(z1,[]) = (ze,1,N) delta(z2,0) = (z2,0,L) delta(z2,1) = (z2,1,L) delta(z2,[]) = (ze,[],R) Es gilt zum Beispiel: z0 101 |-* [] ze 110 [] Definition: Die von einer Turingmaschine M akzeptierte Sprache L(M) ist definiert durch L(M) = {w:Sigma* | z0 w |-* alpha z beta, wobei z:E} Wir wollen nun Turingmaschinen definieren, die nicht ueber den linken und rechten Rand der Eingabe hinausfahren, wohl aber die Eingabe ueberschreiben duerfen. Solche Maschinen werden auch als LBA (Linear beschraenkter Automat, linearly bounded automaton) bezeichnet. Damit solche eine Maschine die Raender der Eingabe erkennen kann, nehmen wir an, dass das Bandalphabet fuer jedes a:Sigma eine Kopie $a enthaelt, die dazu dient, die Eingabe rechts abzuschliessen. Definition: Eine (nichtdeterministische) Turingmaschine ist linear beschraenkt, wenn es zu jedem a:Sigma eine Kopie $a in Gamma \ Sigma \ {[]} gibt, sodass fuer alle w=a1..am:Sigma* gilt: z0 a1 ... am-1 $am |-* alpha z beta ======> |alpha beta| = m Satz 21: Sei G eine Typ-1 Grammatik. Dann existiert ein LBA M mit L(M)=L(G). Beweis: Der Automat (die Maschine M) ueberschreibt Teile der Eingabe nichtdeterministisch durch Rueckwaertsanwendung von Produktionen. Fuehrt dies zu einer Verkuerzung, so werden die weiter rechts stehenden Bandsymbole entsprechend nach links verschoben. Die Maschine akzeptiert, wenn der nichtleere Bandinhlat nur noch aus S besteht. Satz 22: Sei M ein LBA. Dann existiert eine Typ-1 Grammatik mit L(G)=L(M). Beweis: Wir fuehren hilfsweise das Alphabet Delta=Gamma u (Z * Gamma) ein. Dieses erlaubt uns, eine Konfiguration k = a1..am z b1..bn von M durch ein Wort (ueber Delta) der Laenge m+n zu beschreiben: naemlich das Wort k~ = a1..an(z,b1)b2..bn. Es ist nun leicht, kontextsensitive Produktionen anzugeben, die auf der Ebene dieser Kodierung die Relation |- beschreiben in dem Sinne dass k |-* k' genau dann wenn k~ =>* k'~: Ist naemlich (z',b,L):delta(z,a), so fuehrt man die Produktionen c (z,a) -> (z',c) b fuer alle c:Gamma ein. Analog geht man fuer die delta-Uebergaenge mit N und R vor. Die beiden "Sonderfaelle" bei denen Leerzeichen in die Konfiguration einfliessen, koennen bei einem LBA nicht vorkommen, muessen daher auch nicht beruecksichtigt werden. Sei P' die so erhaltene Produktionenmenge. Die gewuenschte Grammatik G=(V,Sigma,P,S) hat nun folgende Form: V = {S,A} u (Delta * Sigma) P = {S -> A ($a,a) | a:Sigma} u A -> A (a,a) | a:Sigma} u A -> ((z0,a),a) | a:Sigma} u /* Hiermit werden alle Woerter der Form ((z0,a1),a1)(a2,a2)...(am-1,am-1)($am,am) fuer a1..am : Sigma* erzeugt */ {(X,a)(Y,b) -> (U,a)(V,b) | XY->UV : P'} u /* Hiermit werden die Operationen von P' auf den ersten Komponenten durchgefuehrt. Die zweiten Komponenten bleiben bestehen. */ {((z,a),b) -> b | z:E } u {(a,b) -> b | a:Gamma, b:Sigma} /* Hiermit werden die ersten Komponenten geloescht, vorausgesetzt dass ein Endzustand erreicht wurde. */ Es ist klar, dass L(G)=L(M) gilt. Mit der selben Technik laesst sich ausserdem der folgende Satz beweisen: Satz 23: Die Typ-0 Sprachen sind genau die von Turingmaschinen erkennbaren Sprachen. Bemerkung: Die Unterscheidung "deterministisch" - "nichtdeterministisch" macht bei allgemeinen Turingmaschinen keinen Unterschied, da man alle Moeglichkeiten einer nichtdeterministischen Turingmaschine in einer deterministischen systematisch Durchprobieren kann. Dies fuehrt allerdings zu einem erhoehten Ressourcenverbrauch. Insbesondere ist es ein offenes Problem (das LBA-Problem), ob deterministische linear beschraenkte Turingmaschinen genauso maechtig sind wie (nichtdeterministische) LBAs. Bei der naiven Simulation eines LBA durch eine deterministische Turingmaschine faellt ein Platzbedarf von mindestens n^2 an. LBA-Problem: Laesst sich jede Typ-1 Sprache durch einen deterministischen LBA erkennen, oder nicht? Satz 24 (Immerman-Szelepcsenyi): Die kontextsensitiven Sprachen, also die durch LBA erkennbaren Sprachen sind unter Komplement abgeschlossen. Der Beweis dieses Satzes ist nicht Gegenstand der Vorlesung. Er findet sich im Schoening oder, verstaendlicher dargestellt, in einem Buch ueber Komplexitaetstheorie wie Bovet-Crescenzi oder Papadimitriou. ******************************* *II. Berechenbarkeitstheorie. * ******************************* 1 Intuitive und Turing-Berechenbarkeit ====================================== Eine Funktion f : Sigma* ^n -> Sigma* (z.B. Sigma={0,1}) ist intuitiv berechenbar, wenn es ein Rechenverfahren (Algorithmus, Javaprogramm) gibt, welches bei Eingabe w:Sigma* ^n Rechenschritte durchfuehrt und dann irgendwann anhaelt und das Ergebnis f(w1..wn) liefert. Man erweitert diesen intuitiven Berechenbarkeitsbegriff auf partielle Funktionen mit der Massgabe, dass das Rechenverfahren an solchen Eingaben fuer die f undefiniert ist, nicht terminieren soll. Beispiele: Die Funktion f(x,y) = x / y ist intuitiv berechenbar aufgrund des aus der Schule bekannten Divisionsalgorithmus. Die nirgends definierte Funktion ist berechenbar aufgrund des BASIC Programms 10 GOTO 10 Die Funktion f(n) = 0, falls die Dezimalbruchentwicklung von pi einen Block von n aufeinanderfolgenden 7ern enthaelt; undefiniert sonst ist intuitiv berechenbar durch exhaustive Suche (brute force). Die Funktion f(n)=0, falls das LBA-Problem eine positive Loesung hat, f(n)=1, sonst; ist intuitiv berechenbar, da f eine konstante Funktion ist (wir wissen nur nicht welche) und konstante Funktionen intuitiv berechenbar sind. Die Funktion f(n) = 0, falls die Dezimalbruchentwicklung von pi einen Block von n aufeinanderfolgenden 7ern enthaelt; 1 sonst ist erstaunlicherweise auch berechenbar, wobei allerdings auch hier wiederum kein Verfahren bekannt ist. Der Grund ist folgender. Entweder enthaelt die Dezimalbruchentwicklung von pi beliebig lange 7er Bloecke, dann ist f konstant 0 also berechenbar. Anderenfalls gibt es einen 7er Block einer bestimmten Maximallaenge n0 und keine 7er Bloecke groesserer Laenge. Dann aber ist f(n)=if n<=n0 then 0 else 1 und auch diese Funktion ist intuitiv berechenbar. Anders sieht es aus mit der Funktion f(n) = 0, falls die Dezimalbruchentwicklung von pi einen Block von genau n aufeinanderfolgenden 7ern enthaelt; 1 sonst Hier ist kein Rechenverfahren bekannt und man weiss auch nicht, ob eines existiert. Schliesslich gibt es Funktionen von denen man weiss, dass sie nicht berechenbar sind. Hierzu gehoeren die folgenden: f(p) = 0, falls p ein terminierendes Javaprogramm ist, 1 sonst. f(p) = 0, falls das Gleichungssystem (mit +,*,Variablen, Konstanten) p eine Loesung in ganzen Zahlen hat, 1 sonst. f(G,w) = 1, falls G eine Typ-0 Grammatik ist und w:L(G); 0 sonst. f(p) = 0, falls der Satz von Kacheln p (Quadrate mit gefaerbten Kanten) es erlaubt, die Ebene zu pflastern (nur gleichfarbige Kanten duerfen aneinanderstossen); 1 sonst. f(G1,G2) = 1, falls G1 und G2 Typ-2 Grammatiken sind und L(G1) geschnitten mit L(G2) nicht leer ist. 0 sonst. Mehrstellige Funktionen kann man durch Erweiterung des Alphabets um Klammersymbole und Kommas leicht auf einstellige zurueckfuehren, daher beschraenken wir uns im folgenden auf einstellige Funktionen. Definition: eine partielle Funktion f:Sigma* -> Sigma* ist Turing berechenbar, wenn eine deterministische Turingmaschine M existiert, sodass f(w) = v impliziert z0 w |-* []..[] z v [] .. [] wobei z:E und f(w) undefiniert und z0 w |-* alpha z beta impliziert z nicht in E. Church'sche These: Die intuitiv berechenbaren Funktionen stimmen mit den Turing berechenbaren ueberein. "Beweis": "<=" die Berechnung auf einer deterministischen Turingmaschine entspricht der Vorstellung eines intuitiven Berechnuncgsverfahrens. "=>": ist ein Rechenverfahren in einem vernuenftigen Detaillierungsgrad gegeben, so kann man es auch auf einer Turingmaschine "ausprogrammieren". Wichtig hierbei ist, dass sich mehrere Zwischenergebnisse auf dem einen Band durch Hintereinanderschreiben unter Zuhilfenahme von Separatorsymbolen abspeichern lassen. Schreib-Lese-Zugriff auf diese sequentiell gespeicherten Daten ist umstaendlich aber nicht unmoeglich. 2. Berechnungsmodelle ===================== Zur Untermauerung der Church'schen These werden wir nun verschiedene Berechnungsmodelle studieren und deren Aequivalenz nachweisen. 2.1 Mehrband Turingmaschinen. ----------------------------- Man kann eine Turingmaschine auch mit mehreren Baendern und enstprechend mehreren unabhaengig bewegbaren Schreib-Lese-Koepfen ausstatten. In diesem Fall verwendet man eine Uebergangsfunktion des folgenden Typs (n die Zahl der Baender), wobei wir der Einfachheit halber nur die deterministische Variante angeben: delta : Z * Gamma^n -> Z * Gamma^n * {L,R,N}^n Ist also delta(z,g1..gn) = (z',(g1'..gn'),(d1..dn')), so bedeutet das, dass die Maschine im Zustand z und bei den gelesen Symbolen g1..gn, also g1 unter dem ersten Schreib-Lese-Kopf, g2 unter dem zweiten, etc, in den Zustand z' uebergeht, die Symbole g1..gn durch g1'..gn' ersetzt und die n Schreiblesekoepfe unabhaengig voneinander in die Richtungen d1..dn bewegt. Ist also etwa d1=L und d2=R, so muss der erste Kopf nach links und der zweite Kopf nach rechts bewegt werden. Eine n-Band Turingmaschine berechnet eine partielle Funktion f : Sigma*->Sigma* (Sigma das Eingabealphabet der Turingmaschine) wenn die Maschine gestartet im Anfangszustand, erstes Band beschriftet mit Eingabe w, erster Schreiblesekopf auf dem ersten Symbol von w, alle anderen Baender leer, anhaelt genau dann wenn f(w) definiert ist und dann das Ergebnis v=f(w) auf dem ersten Band links vom ersten Schreiblesekopf steht. Es ist klar, dass eine n-Band Maschine eine normale (also Einband) Turingmaschine simulieren kann, indem nur das erste Band genutzt wird. Die Umkehrung gilt allerdings auch in folgendem Sinne: Satz 25: Sei M eine n-Band Turingmaschine und f:Sigma*->Sigma* eine partielle Funktion derart dass M f berechnet. Dann existiert auch eine 1-Band Turingmaschine, die f berechnet. Beweis: Wir verwenden das neue Alphabet Gamma' = (Gamma * {_,*})^n. Ein Band, dessen Felder mit diesem Alphabet beschriftet sind, laesst sich auffassen als ein Band mit 2n Spuren, wobei die Spuren mit gerader Nummer mit Symbolen aus Gamma beschriftet sind und die Spuren ungerader Nummer mit Symbolen aus {_,*}. Solch ein Band wiederum ist in 1-1 Beziehung mit n Baendern und den zugehoerigen Kopfpositionen. Man legt die n Baender einfach irgendwie uebereinander und markiert die jeweilige Kopfposition mit einem * in der unmittelbar darunterliegenden Spur. Es verbleibt nun die Aufgabe, die Bewegungen und Aktionen der n Band Maschine auf der Ebene dieser Kodierung durch die 1 Band Maschine nachzuvollziehen. Hierzu gehen wir davon aus, dass sich der Schreiblesekopf links von allen * Markierungen befindet. Um nun eine einzige Aktion der n Band Maschine zu simulieren, wird der Kopf solange nach rechts bewegt, bis er an allen * Markierungen vorbeigefahren ist. Deren Zahl n ist fest und kann daher im endlichen Zustand der 1 Band Maschine gemerkt werden. Hierbei merkt sich die Maschine auch alle n Gamma-Symbole, die an den jeweiligen Kopfpositionen stehen. Nunmehr kann die 1-Band Maschine die entsprechende Aktion der n-Band-Maschine auswaehlen und beim Zurueckgehen durchfuehren. QED 2.2 LOOP Programme ------------------ Die Syntax der LOOP Programme ist wie folgt erklaert: P ::= x_i := x_j + 1 /* Wertzuweisung, i,j:N */ | x_i := x_j - 1 /* Wertzuweisung, i,j:N */ | x_i := 0 /* Wertzuweisung, i:N */ | LOOP x_i DO P END /* x_i fache Ausfuehrung von P */ | P ; P /* Hintereinanderausfuehrung */ Zum Beispiel ist x_0 := 0 LOOP x_1 DO x_0 := x_0 + 1; x_0 := x_0 + 1; END ein LOOP Programm. Nach seiner Abarbeitung hat x_2 den doppelten Wert von x_1. 2.2.1 Semantik: Formal ist die Semantik eines LOOP Programms eine partielle Funktion, die Belegungen der Variablen auf Belegungen der Variablen abbildet. Solch eine Belegung ordnet den Variablen Werte in N zu, wobei alle bis auf endlich viele Variablen den Wert 0 bekommen. Ist eta solch eine Belegung, so bezeichnen wir mit [[P]]eta die Belegung nach Ausfuehrung von P. Es gilt: 1) [[x_i:=x_i+1]]eta = eta[xi |-> eta(xi)+1] 2) [[x_i:=x_i-1]]eta = eta[xi |-> eta(xi) -. 1], wobei x-.y = x-y, falls x>=y und 0 sonst. 3) [[x_i := 0]]eta = eta[x_i |-> 0] 4) [[LOOP x_i DO P END]]eta = f^n(eta), wobei f(eta) = [[P]](eta) und n = eta(x_i). 5) [[P1;P2]]eta = [[P2]]([[P1]]eta) 2.2.2 Abgeleitete Konstrukte Wir fuehren die folgenden Abkuerzungen als "syntaktischen Zuckerguss" ein: x_i := x_j + c, wobei c:N, c>0 ist eine Abkuerzung fuer x_i := x_j + 1; x_i := x_i + 1; .... ; x_i := x_j + 1; /* c Zuweisungen, die erste mit x_j, die anderen mit x_i */ Ebenso lassen sich die Anweisungen x_i := x_i - c, x_i := c definieren. SIGN x_i ist eine Abkuerzung fuer LOOP x_i DO x_i:=1 END Hat x_i den Wert 0, so hat x_i auch nach SIGN x_i den Wert 0. Hat x_i einen Wert >0, so hat x_i nach Ausfuehrung von SIGN x_i den Wert 1. IF x_i THEN P END ist eine Abkuerzung fuer x_j:=x_i; SIGN x_j; LOOP x_j DO P; END; wobei j groesser als alle im Gesamtprogramm vorkommenden Variablennummern ist. Wir sagen, x_j sei eine frische Variable. IF x_i THEN P ELSE Q END ist eine Abkuerzung fuer x_j := 1 IF x_i THEN P;x_j := 0 END; IF x_j THEN Q END auch hier ist x_j eine frische Variable. 2.2.3 LOOP Berechenbarkeit Definition: Sei f:N^n -> N eine Funktion. Das LOOP Programm P berechnet die Funktion f, wenn nach Inititalisierung der Variablen x_1,...,x_n mit Argumenten v_1,...,v_n und Initialisierung aller anderen Variablen mit 0 die Abarbeitung von P zu einer Belegung fuehrt, in der x_0 den Wert f(v_1,...,v_n) hat. Eine Funktion, die von einem LOOP Programm berechnet wird, heisst LOOP-berechenbar. Beispiel: Sei P = x_3 := x_1 + c; LOOP x_1 DO x_1 := x_1 - c; IF x_1 THEN x_2 := x_2 + 1; x_3 := x_3 - c; END; END; Das Programm P;x_0:=x_2 berechnet die Funktion x DIV c; das Programm P;x_0:=x_3 berechnet die Funktion x MOD c, jeweils fuer festes c. Das Programm LOOP x_2 DO x_1 := x_2 + 1 END;x_0 := x_1 berechnet die Funktion x+y. Ebenso berechnet man auch die Differenz zweier Zahlen. Ist f bereits als LOOP-berechenbar identifiziert, so fuehren wir die Abkuerzung x_i := f(x_i1,...,x_in) ein, welche den Effekt hat, der Variablen x_i den Funktionswert der Werte der x_ij zuzuweisen. Um diese Abkuerzung tatsaechlich zu implementieren, muss man etwas buchhalterisch vorgehen und zwar besteht das Programmstueck x_i := f(x_i1,...,x_in) aus der Hintereinanderausfuehrung dreier Programme, P1;Pf;P2, wobei Pf ein LOOP Programm ist, welches f berechnet. Das Programm P1 kopiert den Inhalt aller Variablen, die von Pf benutzt werden in frische Variablen und initialisiert die von f benutzten Variablen auf 0, bzw auf die verlangten Argumentwerte. Das Programm P2 restauriert die von Pf verwendeten Variablen zu ihren alten Werten und schreibt ausserdem x_0 nach x_i. Mit dieser Abkuerzung koennen wir nun auch die Division als zweistellige Funktion implementieren unter Verwendung von x_4 := x_1 + x_2; LOOP x_1 DO x_1 := x_1 - x_2; IF x_1 THEN x_3 := x_3 + 1; x_4 := x_4 - c; END; END; Weitere LOOP-berechenbare Funktionen sind Multiplikation, Exponentiation, Fakultaet, aber auch eher symbolische Funktionen, wie etwa f(x,y) = 1, falls die Binaerdarstellung von y in der von x vorkommt. 2.3 WHILE Programme Die WHILE Programme bilden eine Erweiterung der LOOP um eine While-Schleife, bei der solange iteriert wird, bis eine bestimmte Bedingung eintrifft. Formal geschieht dies durch Hinzufuegen der folgenden Klausel zur BNF Grammatik P ::= | WHILE x_i DO P END /* Wiederholte Ausfuehrung von P bis x_i = 0*/ Die Semantik einer solchen While Schleife ist, dass der Rumpf solange ausgefuehrt wird, bis der Wert von x_i Null ist. Die Semantik ist undefiniert, falls dieses Ereignis nie eintritt. 4) [[WHILE x_i DO P END]]eta = f^n(eta), wobei f(eta) = [[P]](eta) und n die kleinste natuerliche Zahl ist, sodass [[P]](eta)(x_i) = 0. Natuerlich kann man die LOOP Schleife durch die WHILE Schleife codieren, sodass man dieses Konstrukt bei WHILE Programmen gar nicht braeuchte. Im Gegensatz zu LOOP Programmen koennen WHILE Programme auch ad infinitum rechnen, also nicht terminieren, Beispiel: x_1:= 1; WHILE x_1 DO x_1 := x_1 END. Daher erweitert man den Begriff der Berechenbarkeit hier wie bei Turingmaschinen auf partielle Funktionen. Definition: Sei f:N^n -> N eine partielle Funktion. Das WHILE Programm P berechnet die Funktion f, wenn nach Inititalisierung der Variablen x_1,...,x_n mit Argumenten v_1,...,v_n und Initialisierung aller anderen Variablen mit 0 die Abarbeitung von P genau dann terminiert, wenn f(v1,...,vn) definiert ist und in diesem Falle zu einer Belegung fuehrt, in der x_0 den Wert f(v_1,...,v_n) hat. Eine Funktion, die von einem WHILE Programm berechnet wird, heisst WHILE-berechenbar. Natuerlich sind echt partielle Funktionen hoechstens WHILE, aber nicht LOOP berechenbar; es gibt aber auch totale Funktionen, die nur WHILE, aber nicht LOOP berechenbar sind. Ein konkretes Beispiel gibt es spaeter. 2.3.1 Simulation von WHILE-Programmen durch Turingmaschinen. Satz 26: Jede WHILE-berechenbare Funktion ist auch Turing berechenbar. Beweis: Wir ordnen jeder Zahl k und jedem WHILE Programm, das hoechstens die Variablen x_0,...,x_k verwendet, eine Turingmaschine mit >= k+1 Baendern zu. Der Inhalt des Bandes i, wobei i=0,...,k soll den Inhalt der Variablen x_i in Binaerdarstellung repraesentieren. Die anderen moeglicherweise verwendeten Baender sind Arbeitsbaender, die zum Beispiel dazu dienen, Variablen zwischenzuspeichern, wie das ja schon bei der Einfuehrung der Kurznotation x_i := f(xs) gemacht wurde. Die Turingmaschine wird durch Induktion ueber den Aufbau des WHILE Programms konstruiert. Fall 1: x_i := x_j + 1. Wir kopieren xj auf ein Hilfsband, simulieren auf diesem die schon bekannte Addiermaschine und kopieren dann das Hilfsband nach x_i. Fall 2: x_i := x_j - 1. Hier benoetigen wir eine Subtrahiermaschine. Sie ist analog zur Addiermaschine. Fall 3: x_i := 0. Das ist klar. Fall 4: P1;P2. Seien M1 und M2 die Maschinen, die P1 und P2 simulieren. Die zu konstruierende Maschine M fuer P1;P2 wird sich zunaechst wie M1 verhalten, sodann aber alle Hilfsbaender loeschen und M2 starten. Fall 4: WHILE x_i DO P END. Sei M die Maschine, die P simuliert. Die gesuchte Maschine geht aus M dadurch hervor, dass Anfangszustand und Endzustaende zu "ganz normalen" Zustaenden werden, die dazu verwendet werden, die Maschine M solange immer wieder zu starten, bis das Band i den Inhalt Null aufweist. Vor jedem Neustart von P muessen die von M eventuell verwendeten Hilfsbaender wie bei der sequentiellen Komposition auf Null gesetzt werden. QED 2.4 GOTO Programme ------------------ Fuer die umgekehrte Richtung also die Simulation von Turingmaschinen durch WHILE Programme sind die assemblernahen GOTO Programme nuetzlich. Diese Programme (P) verwenden neben den Variablen x_0, x_1, ... noch Marken M_0, M_1, ... welche Anweisungen (A) markieren und als Sprungadressen dienen. Ein GOTO - Programm besteht aus einer durch Semikolon getrennten Folge von markierten Anweisungen der Form M_i : A. Die Anweisungen sind *) x_i := x_j +/- 1 /* Wertzuweisung */ *) GOTO M_i /* unbedingter Sprung */ *) IF x_i THEN GOTO M_j /* bedingter Sprung */ *) HALT /* Erfolgreiche Beendigung des Programms */ Jede Marke darf nur einmal als Markierung einer Anweisung vorkommen. Hier ist ein GOTO-Programm zur Berechnung der Addition: M_1 : IF x_2 THEN GOTO M_3 M_2 : GOTO M_6 M_3 : x_1 := x_1 + 1 M_4 : x_2 := x_2 - 1 M_5 : GOTO M_1 M_6 : x_0 := x_1 M_7 : HALT Die Semantik von GOTO-Programmen sollte intuitiv klar sein, man kann sie formal entweder wie bei Turingmaschinen ueber eine Ein-Schritt-Relation auf globalen Konfigurationen erklaeren (operationale Semantik) oder ueber ein System rekursiv definierter Funktionen (denotationelle Semantik), s. Uebung. Berechnung von Funktionen durch GOTO-Programme und GOTO-Berechenbarkeit werden genauso wie bei WHILE Programmen definiert: Marken, die nicht angesprungen werden, lassen wir weg, ausserdem erlauben wir uns auch noch ein IF-THEN-ELSE mit zwei Sprungmarken, welches leicht ausgedrueckt werden kann. Verwenden wir dann noch symbolische Sprungadressen, dann sehen die GOTO Programme gar nicht mehr so schlimm aus: "add(x_1,x_2)" : IF x_2 THEN GOTO "add(x_1,x_2),x_2=/=0" ELSE GOTO "return x_1" "add(x_1,x_2),x_2=/=0" : x_1 := x_1 + 1; x_2 := x_2 - 1; GOTO "add(x_1,x_2)" "return x_1" : x_0 := x_1; HALT Hier sieht man, dass ein GOTO-Programm eigentlich nichts anderes ist, als ein System endrekursiver Funktionen. Ich meine, dass das Konzept etwas zu unrecht durch einflussreiche Arbeiten von Dijkstra und Hoare "GOTO considered harmful", "strukturierte Programmierung", zugunsten von while-Schleifen verdraengt wurde. Wie dem auch sei, WHILE und GOTO Programme sind aequivalent; wie man eine WHILE-Schleife durch GOTO's ausdrueckt sollte klar sein: WHILE x_i DO P entspricht "loop" : IF x_i THEN GOTO "body" ELSE GOTO "done" "body" : P; GOTO "loop" "done" : rest des Programms Etwas interessanter ist die Umkehrung: Satz 27: Jede GOTO-berechenbare Funktion ist auch WHILE berechenbar. Beweis: Sei P ein GOTO-Programm mit den Marken M0,...,Mn. Wir repraesentieren die aktuell zu bearbeitende Marke (Programmzaehler) durch eine frische Variable pc, also pc = x_j fuer j gross genug. Die Variablen von P werden durch dieselben Variablen des zu konstruierenden WHILE-Programms repraesentiert. Ohne Beschraenkung der Allgemeinheit nehmen wir an, dass P die Form M_0 : A_0; M_1 : A_1; ... ; M_n : HALT hat und dass keine der A_1,..A_n-1 die HALT Anweisung ist. Nunmehr konstruieren wir unser WHILE Programm wie folgt: pc := 1; WHILE pc =/= n DO IF pc = 1 THEN /* Simuliere A_1 */ IF pc = 2 THEN /* Simuliere A_2 */ ... IF pc = n-1 THEN /* Simuliere A_n-1 */ END Das "Simulieren" einer Wertzuweisung x_i:=x_j+1 erfolgt durch x_i:=x_j+1;pc:=pc+1 Das "Simulieren" der anderen Zuweisungen erfolgt analog Das "Simulieren" einer Sprunganweisung GOTO M_j erfolgt durch pc:=j Das "Simulieren" eines bedingten Sprungs IF x_i THEN GOTO M_j erfolgt durch IF x_i THEN pc:=j ELSE pc:=pc+1 Die HALT Anweisung wird nicht simuliert, da keine der A_1,...A_n-1 eine solche ist. Es ist klar, dass das resultierende Programm dieselbe Funktion wie P berechnet. QED Durch Hin- und Zurueckuebersetzen sieht man hieraus, dass man jedes WHILE Programm in eine Form bringen kann, in der nur eine einzige WHILE-Schleife benutzt wird. Dies ist die Kleene Normalform. Intuitiv "WHILE noch nicht fertig DO einen Schritt weiterrechnen END". Wir bemerken, dass eine solche Normalform bei LOOP Programmen nicht verfuegbar ist, so erfordert zum Beispiel die Multiplikation auf jeden Fall zwei geschachtelte LOOP Schleifen. Satz 28 Jede Turing-berechenbare Funktion ist auch GOTO berechenbar. Beweis: Sei M eine (deterministische) 1-Band Maschine, die eine Funktion f berechnet. Sei weiter c=|Gamma| die Groesse des Alphabets. O.B.d.A sei Gamma={0,1,2,3,...,c-1} und Z={0,1,...,q-1}. Wir repraesentieren eine Konfiguration alpha z beta durch drei Variablen x_alpha, x_beta, x_z. Hierbei enthaelt x_alpha das Wort rev(alpha), also alpha von rechts nach links gelesen, aufgefasst als Zahl im c-er System. Weiter enthaelt x_beta das Wort beta, also von links nach rechts gelesen, aufgefasst als Zahl im c-er System. x_z schliesslich enthaelt den Zustand. Formal gilt, falls alpha = a(m-1)..a(0), beta=b(0)..b(n-1), dann x_alpha = sum(i=0..m-1,c^i a(m-1-i)) x_beta=sum(j=0..n-1,c^ib(i)) Das Symbol an der Kopfposition ergibt sich also zu x_beta MOD c; das Symbol links neben der Kopfposition ergibt sich also zu x_alpha MOD c; das Symbol rechts neben der Kopfposition ergibt sich also zu x_beta DIV c MOD c. Jetzt fuehren wir fuer jeden Zustand z eine Marke M_z ein. An jeder Marke steht nun eine Folge von Anweisungen, die wir aus der Uebergangsfunktion delta ablesen. Die Reihenfolge der Anweisungen ist beliebig. Falls delta(z,a) = (z',b,L) so schreibe an die Marke M_z die Anweisung IF beta MOD c = a THEN x_beta := ((x_beta DIV c) * c + b) * c + x_alpha MOD c; x_alpha := x_alpha DIV c; GOTO M_z' Falls delta(z,a) = (z',b,R) IF beta MOD c = a THEN x_alpha := x_alpha * c + b; x_beta := x_beta DIV c; GOTO M_z' Falls delta(z,a) = (z',b,N) IF beta MOD c = a THEN x_beta := (x_beta DIV c) * c + b; GOTO M_z' Falls z ein Endzustand ist, so schreibe an M_z die Anweisung HALT und sonst nichts. (Eine Turingmaschine sollte keine Uebergaenge aus Endzustaenden haben, da sie (im Gegensatz zu endlichen Automaten und DPDA!) bei Erreichen eines Endzustandes sofort stehenbleibt. Hier haben wir IF-THEN etwas freier als eigentlich erlaubt verwendet. Die Uebersetzung in die formale Syntax sollte klar sein. Wir beginnen nun die Programmausfuehrung bei M_z0, ggf indem wir als erste Anweisung dorthin springen. Es sollte klar sein, dass auf diese Weise M korrekt simuliert wird. QED. Wir haben jetzt gesehen, dass die folgenden Formalismen allesamt aequivalent sind, was deren Berechnungskraft betrifft: 1-Band TM Mehrband TM WHILE Programme GOTO Programme 2.5 Primitive Rekursion ----------------------- Wir lernen nun ein eher mathematisch motiviertes Berechnungsmodell kennen, welches den LOOP Programmen entspricht. Definition: Die Klasse der primitiv rekursiven Funktionen ist die kleinste Klasse von (ein oder mehrstelligen) Funktionen auf den natuerlichen Zahlen, die den folgenden Bedingungen genuegt: 1) Die im folgenden genannten Grundfunktionen sind primitiv rekursiv. *) Nachfolgerfunktion succ(x)=x+1 *) Projektionen proj_(n,i)(x_1,..,x_n) = x_i *) Konstante Null 0(x)=0 2) Komposition: Sind f(x1..xn) und g1(ys),..., gn(ys) primitiv rekursiv, so auch h(ys) = f(g1(ys),...,gn(ys)) (Komposition). Man beachte, dass ys fuer einen Variablenvektor y1..ym steht. 3) Primitive Rekursion: Erfuellt f ein Gleichungssystem der Form f(0,ys) = g(ys) f(x+1,ys) = h(x,f(x,ys),ys) mit primitiv rekursiven Funktionen g, h, so ist auch f primitiv rekursiv. Will man zeigen, dass eine Funktion primitiv rekursiv ist, so muss man sie also, falls es sich nicht gerade um eine Grundfunktion handeln sollte, aus schon als primitiv rekursiv erkannten Funktionen durch Komposition oder primitive Rekursion definieren. Zum Beispiel ist die Funktion add(x,y)=x+y primitiv rekursiv, denn sie entsteht durch Komposition aus der Funktion add'(x,y)=y+x, naemlich add(x,y) = add'(proj_(2,2)(x,y), proj_(2,1)(x,y)) und add' erfuellt das Gleichungssystem add'(0,x) = x = proj_(1,1)(x) add'(y+1,x) = h(y, add'(y,x), x) wobei h(y,z,x) = succ(z) = succ(proj_(3,2)(x,y,z)) Natuerlich haette man die Addition auch durch Rekursion ueber das erste Argument definieren koennen und sich dadurch ein paar Zwischenschritte erspart. In der Praxis laesst man auch etwas verallgemeinerte Rekursionsschemata zu, wie zum Beispiel add(x,0) = x add(x,y+1) = succ(add(x,y)) wobei es sich versteht, dass ein solches Schema durch Einsetzen von Projektionen und Kompositionen in eine "offizielle" Definition verwandelt werden kann. Ein weiteres Beispiel ist die Vorgaengerfunktion u(x) = max(x-1,0) (modifizierte Differenz) Hier hat man u(0) = 0 u(x+1) = x also formal u(0) = 0 u(x+1) = proj_(2,1)(x,u(x)) Durch weitere primitive Rekursion laesst sich daraus die allgemeine Subtraktion definieren. Satz 29. Die folgende Funktion ist eine primitiv rekursive Bijektion von N x N nach N. / x+y+1 \ c(x,y) = (x+y+1)(x+y) / 2 + x = | | + x (Binomialkoeffizient) \ 2 / Ausserdem sind die durch e(c(x,y)) = x, f(c(x,y))=y definierten Inversen von c primitiv rekursiv. Beweis. Wir setzen b(n) = n(n-1)/2 (Binomialkoeffizient) und beobachten b(0)=0, b(n+1)=b(n)+n, somit ist b primitiv rekursiv. Es gilt aber c(x,y)=b(x+y+1)+x, somit ist auch c als primitiv rekursiv erwiesen. Zum Beweis der Surjektivitaet argumentieren wir wie folgt: 0=c(0,0). Ist z=c(x,y), mit y>0, so ist z+1=c(x+1,y-1). Ist dagegen z=c(x,0), so ist z+1=c(0,x+1). (Es gilt naemlich c(0,x+1) = choose(x+2,2) = choose(x+1,2)+x+1 = c(x,0)+1). Der Beweis der Injektivitaet erfolgt durch Induktion ueber z=c(x,y). Ist c(x,y)=0, so folgt x=y=0. Ist c(x,y)=c(x',y')=z+1, dann sind drei Faelle zu unterscheiden: x>0, x'>0: es folgt c(x-1,y+1)=c(x-1,y'+1)=z. Die Behauptung folgt mit der Induktionshypothese. x=0, x'=0: es folgt c(y-1,0)=c(y'-1,0)=z. Induktionshypothese. x=0, x'>0: es folgt c(y-1,0)=c(x'-1,y'+1)=z, also nach IH y'+1=0, was ein Widerspruch ist. Da man nun weiss, dass c bijektiv ist, kann man die Inversen durch systematische Suche ausrechnen: e(z) = max({x <= z | es existiert y <= z. c(x,y)=z} u {0}) Um dies als primitiv rekursiv zu erweisen, definieren wir zunaechst eine Hilfsfunktion P(x,z,k) = 1, falls es existiert y<=k sodass c(x,y)=z, 0 sonst. Es gilt P(x,z,0) = eq(c(x,0),z) wobei eq(u,v)=sign(u-v)+sign(v-u) und sign(0)=0, sign(x+1)=1 (letzteres ist eine primitive Rekursion!) Ausserdem gilt P(x,z,k+1) = max(P(x,z,k), eq(c(x,k+1),z)) wobei max(x,y) = (x-y)+y. Somit ist P primitiv rekursiv. Des weiteren definieren wir eine Hilfsfunktion Q(z,k) = max({x <= z | P(x,z,z)=1} u {0}) Es gilt Q(z,0) = 0, Q(z,k+1) = max((k+1)*P(k+1,z,z), Q(z,k)) Schliesslich hat man e(z) = Q(z,z). Die Definition von f erfolgt analog. QED Satz 30: Jede primitiv rekursive Funktion ist LOOP berechenbar. Beweis: Die Grundfunktionen sind sicherlich LOOP-berechenbar und ausserdem sind die LOOP-berechenbaren Funktionen unter Komposition abgeschlossen. Es bleibt zu zeigen, dass eine aus LOOP-berechenbaren Funktionen durch primitive Rekursion definierte Funktion auch LOOP-berechenbar ist. Sei also f(0,y) = g(y) f(x+1,y) = h(x,f(x,y),y) Der Einfachheit halber erlauben wir nur einen Parameter y. Der allgemeine Fall ist aehnlich. Das folgende LOOP Programm berechnet dann f: x_0 := g(x_2); x_3 := 0; LOOP x_1 DO x_0 := h(x_3,x_0,x_2); x_3 := x_3+1 END QED Satz 31: Jede LOOP-berechenbare Funktion ist primitiv rekursiv. Beweis: Wir verwenden folgende Bijektion von N* auf N: code([x0,...,x_n]) = c(x_0,c(x_1,...,c(x_n,0)...)) Sie hat die Inversen d_0(z) = e(z), d_1(z) = e(f(z)), d_2(z) = e(f(f(z))), etc pp. Wir definieren ausserdem die Funktion set_i(x,z) durch set_i(x,z) = c(d_0(z),c(d_1(z),...,c(d_(i-1)(z),x,f^(i+1)(z)...) Es gilt set_i(x, code([x0,...,xn])) = code([x0,...,x(i-1),x,x(i+1),...,xn]). Wir koennen jetzt auch Variablenbelegungen durch einzelne Zahlen codieren: code(eta) = code([eta(x_0), eta(x_1), ... , eta(x_n)]), wobei n so gross gewaehlt ist, dass eta(x_m)=0 fuer m>n. Man beachte, dass fuer alle i gilt d_i(code(eta)) = eta(x_i). Durch Induktion ueber den Aufbau von LOOP Programmen ordnen wir jetzt jedem LOOP Programm P eine primitiv rekursive Funktion f_P zu, derart dass f_P(code(eta)) = code([[P]](eta)). Ist P = x_j := x_i+1, so ist f_P(z) = set_j(d_i(z)+1,z). Die anderen elementaren Anweisungen sind analog. Ist P = P1;P2, so ist f_P(z) = f_P2(f_P1(z)) Ist P = LOOP x_i DO P1 END, so ist f_P(z) = t(d_i(z),z) wobei t(0,z) = z t(k+1,z) = f_P1(t(k,z)) Ist nun f(x1,...,xn) LOOP berechenbar durch das LOOP Programm P, so ist f auch primitiv rekursiv, da ja f(x1,...,xn) = d_0(f_P(c(0,c(x1,c(x2,...,c(xn,0)))))) QED 2.6. mu-Rekursion ----------------- Um auch die WHILE Programme durch Rekursionsmuster in den Griff zu bekommen, fuehren wir noch die sogenannte mu-Rekursion ein: Definition: Sei g(n,x1,...,xk) eine k+1 stellige partielle Funktion auf N. Die k-stellige partielle Funktion f(x1,...,xk) entsteht aus g durch mu-Rekursion, wenn gilt / das kleinste n, sodass g(n,xs)=0 | und g(k,xs) fuer k<=n definiert ist. f(x1,...,xk) = < | \ undefiniert, falls kein solches n existiert. Man schreibt: f(xs) = mu n.g(n,xs). Erinnerung: x-vektor wird als xs geschrieben. Man beachte, dass f das folgende (endrekursive, aber nicht primitiv rekursive) Rekursionsschema erfuellt: f(xs) = h(0,xs) h(n,xs) = n, falls g(n,xs)=0, h(n+1,xs) sonst. Definition: Die mu-rekursiven Funktionen sind die kleinste Klasse von Funktionen, die die primitiv rekursiven Grundfunktionen enthaelt und unter Komposition, primitiver Rekursion und mu-Rekursion abgeschlossen ist. Mit der mu-Rekursion gelingt es nun, auch die WHILE-Schleife zu simulieren und zwar in derselben Weise, wie wir auch schon die LOOP-Programme simuliert haben: Ist P = WHILE x_i DO P END, so setzen wir f_P(z) = iter(num(z), z), wobei iter(0,z) = z und iter(n+1,z) = f_P1(iter(n,z)), also iter(n,z) = f_P1^n(z) und num(z) = mu n.d_i(iter(n,z)) Die Codierung ist ineffizient, da man die Anzahl der erforderlichen Iteration separat von der eigentlichen Iteration ausrechnet. Das liegt in der Natur der mu-Rekursion. Auf der anderen Seite laesst sich die mu-Rekursion leicht durch eine WHILE-Schleife implementieren, sodass wir zusammengefasst folgendes gezeigt haben: Satz 32: Die Klasse der mu-rekursiven Funktionen stimmt mit der Klasse der WHILE-berechenbaren Funktion (und damit mit der Klasse der Turing-berechenbaren) Funktionen ueberein. Wir haben nunmehr die folgenden allesamt aequivalenten Berechnungsbegriffe kennengelernt: Turingmaschinen (1Band, Mehrband), WHILE-Programme, GOTO-Programme, mu-Rekursion. Auf der anderen Seite wurde noch kein maechtigeres Berechnungsmodell gefunden, welches gleichzeitig beanspruchen kann, den intuitiven Berechenbarkeitsbegriff zu erfassen. Maechtigere Modelle gibt es viele, erlaubt man etwa die Operation mu' definiert durch mu' n.f(n,xs) = "das kleinste n sodass f(n,xs)=0; 0 falls kein solches n existiert" so kann man zeigen, dass mehr Funktionen berechenbar werden; andererseits ist mu' n.f(n,xs) im allgemeinen nicht intuitiv berechenbar; wie soll man denn feststellen, ob keine solche Nullstelle von f existiert? Wir wollen jetzt noch zeigen, dass die LOOP-berechenbaren Funktionen und damit die primitiv rekursiven Funktionen eine echte Teilmenge der berechenbaren Funktionen bilden. 2.7. Die Ackermannfunktion -------------------------- Die Ackermannfunktion A : N x N -> N ist wie folgt rekursiv definiert: A(0,y) = y+1 A(x+1,0) = A(x,1) A(x+1,y+1) = A(x,A(x+1,y)) Es gilt also A(x,y) = B_x(y), wobei B_0(y) = y+1 B_(x+1)(y) = B_x(B_x(...B_x((1)...) (y+1 malige Anwendung) Hieraus folgt sofort, dass A(x,y) fuer alle x,y definiert ist und dass B_x fuer festes x primitiv rekursiv ist. Wir werden jetzt zeigen, dass A selbst nicht primitiv rekursiv ist. Auf der anderen Seite ist A intuitiv berechenbar, da man ja die rekursive Definition als Javaprogramm auffassen kann. Um weitere Evidenz fuer die Church'sche These aufzubauen und als Beispiel dafuer, wie man allgemeine Rekursionsschemata als WHILE Programme implementiert, wollen wir auch noch formal die WHILE-berechenbarkeit der Ackermannfunktion nachweisen. Satz 33: Die Ackermannfunktion ist WHILE-berechenbar. Beweis: Wir definieren zunaechst wie folgt eine Verallgemeinerung der Ackermannfunktion auf Listen: Die Funktion AList : N* * N -> N ist definiert durch: AList([x1,...,xn],y) = A(xn,A(x(n-1),...A(x3,A(x2,A(x1,y)))...) Es gilt nun (in funktionalem Pseudocode): AList([],y) = y AList(0 :: l, y) = AList(l,y+1) AList(x+1 :: l, 0) = AList(x::l, 1) AList(x+1 :: l, y+1) = AList(x+1 :: x :: l, y) A(x,y) = AList([x],y) Diese Definition ist aber endrekursiv und kann somit direkt in eine WHILE Schleife uebersetzt werden. Um ein WHILE-Programm zu erhalten, muessen wir noch die Liste als natuerliche Zahl repraesentieren, was wiederum durch die Paarungsfunktion c(-,-) (mit den Inversen e und f) gelingt: /* Das folgende WHILE Programm berechnet die Ackermannfunktion */ l:=c(x_1,0); y:=x_2; WHILE l DO x := e(l); IF x = 0 THEN l := f(l);y:=y+1 ELSE IF y = 0 THEN l:=c(x-1,f(l)); y:=1 ELSE l:=c(x,c(x-1,f(l))); y:=y-1 END END END x_0 := y QED Satz 34: Die Ackermannfunktion ist nicht LOOP-berechenbar und damit nicht primitiv rekursiv. Beweis: Man zeigt zunaechst die folgenden arithmetischen Eigenschaften der Ackermannfunktion. i) A(x,y) ist streng monoton wachsend in x und y. ii) Fuer alle c1, c2 existiert c3, sodass A(c2, A(c1, y)) <= A(c3, y) iii) Fuer alle c1 existiert c2, sodass B_c1^x(x) <= A(c2,x) i) ist Lemma B und D in Schoenings Buch. Man beweist es durch Induktion ii) Folgt aus der Monotonie und der Definition, siehe auch Schoening. Man kann setzen c3 := max(c1-1,c2)+2. iii) B_c1^x(x) <= B_c1^x(B_c1^x(1)) <= B_c1^(2x)(1) <= B_c2^x(1) = A(c2+1,x) wobei c2 aus ii) erhalten wird. Fuer Variablenbelegung eta schreiben wir max(eta) fuer max(eta(x_i) | i>=0). Da nur endlich viele eta(x_i) von Null verschieden sind, ist i>das wohldefiniert. Fuer LOOP-Programm P definieren wir die Funktion f_P durch f_P(x) = max{ max([[P]](eta)) | max(eta)<=x} Also ist f_P(x) der groesstmoegliche Variableninhalt, der nach Ausfuehrung von P erreichbar ist, falls alle Variablen mit Werten <= x vorbesetzt werden. Durch Induktion ueber den Aufbau der LOOP Programme zeigen wir nun folgendes: Lemma: Fuer jedes LOOP Programm P existiert eine Konstante c, sodass f_P(x) <= B_c(x) = A(c,x) Beweis des Lemmas: Ist P eine Wertzuweisung, so kann man c=0 waehlen, denn es ist f_P(x) <= x+1 = A(0,x). Ist P=P1;P2 und sei f_P1(x) <= B_c1(x), f_P2(x) <= B_c2(x). Es gilt f_P(x) = max{max(P2(P1(eta))) | max(eta)<=x} <= max{max(P2(rho)) | max rho <= f_P1(x)} = f_P2(f_P1(x)). Also ist f_P(x) <= B_c2(B_c1(x)) <= B_c3(x) wg Eigenschaft ii) Ist P=LOOP x_i DO P1 END und f_P1(x) < B_c1(x), so haben wir f_P(x) <= f_P1(f_P1(...f_P1(x))...) <= B_c1^x(x) <= B_c2(x) mit Eigenschaft iii) \______ _______/ \/ <= x viele Damit ist das Lemma bewiesen. Der Beweis, dass die Ackermannfunktion nicht LOOP berechenbar ist, ist jetzt ganz leicht: Waere die Ackermannfunktion LOOP-berechenbar, dann auch die Funktion a(x) = A(x,x)+1. Dann aber gaebe es ein festes c, sodass a(x) = A(x,x)+1 <= A(c,x). Das aber fuehrt zum Widerspruch, wenn man c = x einsetzt. QED Ein anderes Beispiel fuer eine totale nicht LOOP-berechenbare Funktion ist ein LOOP-evaluator: eval(x,y) = f_P(y), falls x ein LOOP Programm P codiert, 0 sonst. Waere naemlich eval(x,y) LOOP berechenbar, so auch a(x) = eval(x,x)+1 Ist aber nun x0 Codierung eines (hypothetischen) LOOP-Programms P fuer a(x), so haette man eval(x0,x0) + 1 = a(x0) = f_P(x0) = eval(x0,x0). Selbstverstaendlich ist aber eval eine berechenbare Funktion. 3: Unentscheidbarkeit, Halteproblem, Reduzierbarkeit ------------------------------------------------------ Definition: Eine Menge A <= N heisst entscheidbar, wenn ihre charakteristische Funktion chi_A : N -> {0,1} wobei chi_A(x)=1 genau dann, wenn x:A ist, berechenbar ist. Das bedeutet, dass es eine Turingmaschine gibt, die bei Eingabe x immer haelt und genau dann 1 ausgibt, wenn x in A ist. Definition: Eine Menge A <= N heisst semientscheidbar, wenn die folgende partielle Funktion berechenbar ist: 1, falls x:A chi'_A(x) = < undefiniert sonst. Das bedeutet, dass eine Turingmaschine gibt, die bei Eingabe x anhaelt genau dann, wenn x:A ist und nicht terminiert, falls x nicht in A ist. Diese Begriffe verallgemeinern sich sofort auf Teilmengen von Sigma* durch Fixierung einer geeigneten Codierung von Sigma* in N, etwa mithilfe des |Sigma|-er Systems wie im Beweis, dass Turingmaschinen durch WHILE-Programme simuliert werden koennen. Natuerlich ist jede entscheidbare Menge auch semientscheidbar (bei negativer Antwort schickt man die Maschine in eine Endlosschleife). Die umgekehrte Richtung gilt allerdings nicht. Es gibt Mengen, die semientscheidbar sind, aber nicht entscheidbar. Eine solche wollen wir nunmehr kennenlernen: Wir fixieren hierzu eine Codierung von Turingmaschinen als 0-1 Folgen durch Wahl irgendeines geeigneten Binaerformats. Definition: Das Halteproblem H ist die folgende Teilmenge von N: H = { c(x,y) | x codiert eine Turingmaschine M und M angewendet auf x haelt}. Das Halteproblem ist also intuitiv die Frage, ob eine gegebene Turingmaschine auf gegebener Eingabe anhaelt. Diese Fragestellung ist nicht entscheidbar (unentscheidbar): Satz 35: Das Halteproblem ist unentscheidbar. Waere das Halteproblem entscheidbar, dann waere auch die folgende Funktion berechenbar: / 0, falls c(x,x) nicht in H (also, falls x angewendet auf x | nicht haelt. ) | f(x) = < | | undefiniert, falls c(x,x) in H (also falls x angewendet \ auf x haelt.) Man muss hierzu nur ein hypothetisches WHILE Programm (oder Turingmaschine) fuer die charakteristische Funktion von H etwas umbauen. In diesem Fall gaebe es aber auch eine Turingmaschine M, die f berechnet und diese Maschine M haette dann eine Codierung, sagen wir x0. Nachdem M die Funktion f berechnet, gilt insbesondere 1) f(x0) ist definiert genau dann wenn M angewendet auf x0 haelt. Aufgrund der Definition der Funktion f gilt aber auch: 2) f(x0) ist definiert, genau dann wenn c(x0,x0) nicht in H, also wenn M angewendet auf x0 nicht haelt. Diese beiden Aussagen sind aber widerspruechlich, weswegen solch eine Maschine M gar nicht existieren kann! QED Satz 36: Das Halteproblem ist semientscheidbar. Beweis: Gegeben z:N, so bestimme man x,y mit z=c(x,y) und simuliere die durch x codierte Turingmaschine auf der Eingabe y. Kommt diese Simulation zum Ende, so gebe man 0 aus. Dieses intuitive Berechnungsverfahren kann leicht als WHILE o.ae. Programm formalisiert werden. Satz 37: Eine Menge A ist entscheidbar, genau dann, wenn sowohl A, als auch N \ A (Komplement von A) semi-entscheidbar sind. Beweis: Ist A entscheidbar, so auch N \ A durch Vertauschen von 0 und 1. Mithin sind aber auch A und N\A semi-entscheidbar. Sind andererseits sowohl A, als auch N\A semi-entscheidbar (vermoege der Turingmaschinen M1 und M2), so erhaelt man ein Entschidungsverfahren fuer A, indem man bei gegebenem x:N die Berechnungen M1(x) und M2(x) parallel durchfuehrt. Genau eine von beiden muss irgendwann zum Halt kommen und dies liefert dann die gesuchte Antwort. Satz 38 Es existieren primitiv rekursive Funktionen T, U, derart, dass zu jeder (einstelligen) berechenbaren Funktion f eine natuerliche Zahl e existiert, sodass gilt f(x) = U(mu s.T(e,s,x)) Beweis: Wir definieren S(e,t,y,x) als if "Turingmaschine codiert durch e angewendet auf Eingabe x terminiert nach t Schritten mit Ergebnis y" then 0 else 1 Das ist offensichtlich LOOP berechenbar, also primitiv rekursiv. Nun setzen wir T(e,s,x) = S(e,pr1(s),pr2(s),x) wobei pr1 und pr2 die Inversen der Paarungsfunktion sind, also pr1(c(x,y))=x, pr2(c(x,y))=y. und schliesslich U(x) = pr2(x). QED Definition: Eine Menge A<=N ist rekursiv aufzaehlbar (r.e.), wenn es eine totale berechenbare Funktion f:N->N gibt, sodass A = {x | es existiert i:N mit f(i)=x}. Die Funktion f zaehlt also die Elemente von A der Reihe nach auf. Satz 38: Eine nichtleere Menge A ist rekursiv aufzaehlbar gdw sie semi-entscheidbar ist. Beweis: Wird A durch f aufgezaehlt, so laesst sich chi'_A(x) wie folgt definieren: chi'_A(x) = let t = mu t.if f(t) = x then 0 else 1 in f(t) Man zaehlt also solange auf, bis das gegebene x erwaehnt wird, ggf nie. Ist umgekehrt chi'_A berechenbar und e der Code einer entsprechenden Turingmaschine, so ist f(n) = if T(e,x,n)=0 then U(n) else a0 eine Aufzaehlung von A, wobei a0 ein beliebiges fest gewaehltes Element von A ist. QED Definition: Seien A, B zwei Teilmengen von N. A laesst sich auf B reduzieren, i.Z. A <= B, genauer gesagt many-one reduzieren, wenn es eine totale berechenbare Funktion f gibt, sodass gilt: x:A <==> f(x):B Folgerung: Laesst sich A auf B reduzieren und ist B (semi) entscheidbar, so ist auch A (semi)entscheidbar; ist dagegen A unentscheidbar, dann erst recht B. Desgleichen fuer "nicht semi entscheidbar". Beispiele: Sei K = {e | e codiert eine Turingmaschine, die bei Eingabe e haelt}. Es gilt K <= H. Wir haben im Beweis von Satz 35 eigentlich gezeigt, dass K unentscheidbar ist und dann die Unentscheidbarkeit des Halteproblems H gefolgert vermoege der Reduktion f(e) = c(e,e). Die Abkuerzung K fuer obige Menge ist Standard. Sei H0 = {e | e codiert eine Turingmaschine, die bei leerer Eingabe haelt} Es ist H <= H0 vermoege der Reduktion f(z) = "diejenige Maschine, die das Band mit pr2(z) vorinitialisiert und dann pr1(z) simuliert". Satz 39 (Satz von Rice): Sei P eine Eigenschaft von (einstelligen) berechenbaren Funktionen auf N. P gelte weder fuer alle, noch fuer gar keine berechenbaren Funktionen. Dann ist A_P = {e | die von der Turingmaschine e berechnete Funktion hat die Eigenschaft P} unentscheidbar. Beweis: Fall 1: Die nirgends definierte Funktion Omega habe die Eigenschaft P. Es muss ausserdem eine berechenbare Funktion q geben, welche die Eigenschaft P nicht hat. Sei M eine Turingmaschine fuer q. Jetzt definieren wir eine Reduktion von N\H0 auf A_P durch f(e) = "Die Maschine, die die Eingabe x zwischenspeichert, sodann e auf leeres Band anwendet und anschliessend M_q auf Eingabe x simuliert." Die durch f(e) berechnete Funktion ist ueberall undefiniert, hat also die Eigenschaft P, falls e auf leerem nicht haelt. Haelt dagegen e auf leerem Band, so verhaelt sich f(e) wie M und liegt amit in A_P. Somit gilt in diesem Falle N\H0 <= A_P und A_P ist unentscheidbar. Im anderen Falle zeigt man analog H0 <= A_P womit A_P ebenfalls unentscheidbar ist. QED. Dieser Satz bedeutet also, dass keine nichttriviale semantische Eigenschaft von Programmen ("berechnet eine bestimmte Funktion", "verhaelt sich bei bestimmten Eigenschaften soundso", ... durch Inspektion des Programmtexts entscheidbar ist. Wir bemerken, dass manche semantischen Programmeigenschaften immerhin semi-entscheidbar sind, etwa die Frage, ob zu bestimmten Testeingaben ein bestimmter Wert herauskommt. Andere aber nicht, wie zum Beispiel die Frage, ob ein gegebenes Programm bei einer bestimmten Eingabe nicht terminiert. Der Satz von Rice-Shapiro (nicht in dieser VL) charakterisiert diejenigen semantischen Programmeigenschaften P, sodass A_P semi-entscheidbar (= r.e.) ist. Satz (Kriterium von Rice-Shapiro): Ist P eine Eigenschaft der berechenbaren Funktionen, sodass A_P = {e | die durch e berechnete Funktion hat Eigenschaft P} r.e. ist, so muss folgendes gelten: Hat Funktion f die Eigenschaft P, so existiert eine endliche Teilfunktion g von f (also g ist nur an endlich vielen Punkten definiert und stimmt an diesen mit f ueberein), welche auch die Eigenschaft P hat. Die Zugehoerigkeit zu P bemisst sich also nach dem Werteverlauf an endlich vielen Testpunkten. Beweis: Sei widerspruchshalber P eine Eigenschaft, die obiges Kriterium verletzt, gebe es also eine Funktion f mit Eigenschaft P so, dass keine endliche Teilfunktion g von f die Eigenschaft P hat. Wir koennen dann zeigen (N \ K) <= A_P, woraus folgt, dass A_P nicht r.e. ist. Wir definieren jetzt w(x) = "diejenige Turingmaschine, die bei Eingabe t die Maschine x fuer t Schritte auf Eingabe x simuliert und dann, falls diese Berechnung noch nicht gehalten hat, f(t) ausgibt und ansonsten undefiniert ist." Wenn jetzt x : N \ K, dann haelt also x angewendet auf x fuer kein t und somit ist w(x) ein Programm fuer die Funktion f. Damit aber liegt w(x) in A_P. Ist dagegen x : K, haelt also x angewendet auf x nach, sagen wir, t Schritten, so berechnet w(x) die endliche Teilfunktion von f mit Definitionsbereich eingeschraenkt auf {0,1,...,t}. Diese hat nach Voraussetzung aber nicht die Eigenschaft P und somit ist dann w(x) nicht in A_P. Wir haben gezeigt x : N\K <=> w(x):A_P und es folgt, dass A_P nicht r.e. sein kann. QED Mit diesem Kriterium kann man zum Beispiel sehen, dass folgende Probleme nicht einmal semi-entscheidbar sind: {x | x berechnet eine gegebene totale Funktion f} {x | x berechnet irgendeine totale Funktion} In der Literatur ist unter "Satz von Rice-Shapiro" eine exakte Charakterisierung der r.e. semantischen Programmeigenschaften bekannt, die wir hier nicht bringen. Schliesslich noch ein weiterer Nachtrag: Wir schreiben, Kleene folgend, {e} fuer die durch e:N (in einem fest gewaehlten Binaerformat) als Turingmaschine aufgefasst berechnete partielle Funktion, also {e}(x) = U(mu t.T(e,x,t)) Satz (s-m-n-Theorem): Es gibt eine primitiv rekursive (totale) Funktion "curry" mit den folgenden Eigenschaften: i) {curry(e)} ist total ii) Fuer alle x,y:N gilt {{curry(e)}(x)}(y) = {e}(c(x,y)), wobei die eine Seite genau dann definiert ist, wenn es die andere ist. 4 Weitere unentscheidbare Probleme ================================== Im folgenden wollen wir weitere unentscheidbare Probleme vorstellen. Das Postsche Korrespondenzproblem (PCP) ist das folgende: Definition: Geg.: Wortpaare (x1,y1),...,(xk,yk) fuer k:N und xi,yi:Sigma^+. Gefragt: Gibt es eine endliche Folge von Indizes i1,i2,...,in: N, so dass gilt: xi1xi2...xin = yi1yi2...yin? Die Folge i1,...,in heisst Loesung des PCP. Bsp.: Das PCP K = ((1,101),(10,00),(011,11)) hat die Loesung 1,3,2,3. Bsp.: Das PCP K = ((1000,10),(1,0011),(0,111),(11,0)) hat genau eine Loesung, und diese hat Laenge 495. Satz: PCP ist semi-entscheidbar. Beweis: Eine TM kann systematisch immer laengere Folgen von Indizes aufzaehlen und testen, ob diese eine Loesung der Eingabe darstellen. Dies stoppt, falls es Loesung existiert, aber nicht, falls keine existiert. QED Um Unentscheidbarkeit des PCP zu zeigen, definieren wir zunaechst eine leicht Modifikation, genannt MPCP, und zeigen dann H <= MPCP <= PCP. Definition: Eingabe wie bei PCP. Frage: Gibt es eine Loesung i1,...,in mit i1=1? Satz: MPCP <= PCP Beweis: Seien $ und # neue Symbole, die im Alphabet des MPCP nicht vorkommen. Fuer ein Wort w = a1..an sei w^ = #a1#...#an# w` = #a1#...#an w' = a1#...#an# Eine Eingabe K = ((x1,y1),...,(xk,yk)) bilden wir nun auf eine Eingabe f(K) = ((x1^,y1`),(x1',y1`),...,(xk',yk`),($,#$)) fuer das PCP ab. Zu zeigen: K besitzt eine Loesung mit i1=1 gdw. f(K) irgendeine Loesung besitzt. (=>) Sei i1,...,in mit i1=1 eine Loesung fuer K. Dann ist (1,i2+1,... in+1,k+2) eine Loesung fuer f(K). (<=) Sei i1,...,in eine Loesung fuer f(K). Da jedes yi mit # anfaengt, aber unter den xi nur x1 mit # anfaengt, muss fuer eine Loesung j1,...,jm fuer K gelten: j1=1. Genauso sieht man leicht: jm=k+2. Ausserdem gilt: (1,i2-1,...,in-1) ist eine Loesung fuer K. QED Satz: H <= MPCP Beweis: Gegeben die Kodierung einer TM M = (Z,Sigma,Gamma,delta,z0,_,E) und ein Eingabewort w: Sigma^*. Wir konstruieren daraus eine Instanz f(M,w) des MPCP die eine Loesung hat gdw. M auf w haelt. Als Alphabet waehlen wir Gamma u Z u {#}. Als erstes Wortpaar waehlen wir (#,#_z0w_#). Somit muss jede Loesung damit beginnen. Die Idee ist, eine Loesung fuer das MPCP eine Folge von Konfigurationen von M nachbauen zu lassen. Dabei legt man mit der zweiten Komponente immer etwas vor, was in der ersten Komponente nachgebaut werden muss. Ausserdem bestimmt die erste Komponente, was in der zweiten in der naechsten Konfiguration passieren darf. Die weiteren Wortpaare sind: 1) Kopierregeln: (a,a) fuer alle a:Gamma u {#} 2) Transitionsregeln: fuer alle z:Z, a,b,c: Gamma (za,z'c) falls delta(z,a) = (z',c,N) (za,cz') falls delta(z,a) = (z',c,R) (bza,z'bc) falls delta(z,a) = (z',c,L) 3) Blanks einfuegen: (#,_#) und (#,#_) 4) Loeschregeln: (aze,ze) und (zea,ze) fuer alle a:Gamma, ze:E 5) Abschlussregeln: (ze##,#) fuer alle ze:E Zu zeigen: M haelt auf w gdw. f(M,w) eine Loesung 1,...,in hat. (=>) Angenommen, M haelt auf w. Dann gibt es eine Folge von Konfigurationen k0,...,kt, so dass gilt: k0 = z0w, kt ist eine Endkonfiguration und ki |- ki+1 fuer alle i=0,..,t-1. Dann hat f(M,w) eine Loesung mit dem Loesungswort #k0#k1#...#kt#kt'#kt''##..#ze## wobei kt',kt'',... durch Loeschen von Nachbarsymbolen von ze in kt entstehen. (<=) Aus einer Loesung 1,...,in fuer f(M,w) laesst sich in derselben Weise eine endliche Folge von Konfigurationen bauen, die bezeugt, dass M auf w haelt. QED Korollar: PCP ist unentscheidbar. Bem.: Die folgenden, speziellen Instanzen des PCP sind entscheidbar: PCP ueber einem einelementigen Alphabet, PCP mit k=1 oder k=2. Unentscheidbar ist PCP mit k >= 7, fuer 3 <= k <= 6 noch unbekannt. Mithilfe des PCP lassen sich nun einige Fragestellungen bzgl. kontext-freier Grammatiken als unentscheidbar beweisen, die bei regulaeren Sprachen noch entscheidbar sind. Satz: Gegeben zwei kontext-freie Grammatiken G1 und G2. Die folgenden Probleme sind alle unentscheidbar. (P1) L(G1) n L(G2) = 0? (P2) |L(G1) n L(G2)| = unendlich? (P3) L(G1) n L(G2) ist kontextfrei? (P4) L(G1) <= L(G2)? (P5) L(G1) = L(G2)? Beweis(skizzen): Man kann zeigen: PCP <= P1, PCP <= P2, PCP <= P3, P1 <= P4, P1 <= P5. (PCP<=P1) Sei K = (x1,y1),...,(xk,yk) eine Instanz des PCP ueber Alphabet 0,1. Wir bauen zwei kontext-freie Grammatiken ueber dem Alphabet Sigma = {0,1,a1,...,ak}. G1 = S -> A$B A -> a1Ax1 | ... | akAxk | a1x1 | ... | akxk B -> -y1Ba1 | ... | -ykBak | -y1a1 | ... | -ykak wobei -w die Spiegelung von w ist. G2 = S -> a1Sa1 | ... | akSak | T T -> 0T0 | 1T1 | $ Jetzt gilt: K hat die Loesung i1,...,in mit Loesungswort w, genau dann wenn ain...ai1w$-wai1...ain: L(G1) n L(G2). (PCP<=P2) Folgt daraus, dass K eine Loesung hat genau dann wenn K unendlich viele Loesungen hat. (PCP<=P3) Mithilfe des Pumping-Lemmas kann man zeigen, dass L(G1)nL(G2) nicht kontext-frei ist. 0 ist jedoch kontext-frei. (P1<=P4,P1<=P5) Dies benutzt die Tatsache, dass L(G1) und L(G2) sogar deterministisch kontext-frei sind, und man somit Typ-2-Grammatiken fuer ihre Komplemente angeben kann. QED ************************** III. Komplexitaetstheorie* ************************** 1 Die Komplexitaetsklassen P und NP ------------------------------------- In der Komplexitaetstheorie fragen wir nicht nur danach, ob eine Sprache entscheidbar ist, sondern wir kategorisieren Probleme auch danach, wie schwer es ist sie zu entscheiden. Bsp.: Vergleiche das Endlichkeitsproblem fuer NEAs und fuer kontext-freie Grammatiken. Intuitiv ist ersteres wesentlich leichter. Als Mass fuer "Schwierigkeit" werden wir - wie ueblich - den Zeitverbrauch eines Algorithmus als Funktion der Eingabelaenge ansehen. Als Zeiteinheit verwenden wir einen elementaren Schritt einer Turing-Maschine. Nur gilt zwar, dass Einband-TM dieselben Sprachen wie Mehrband-TM erkennen, letztere aber mit weniger Schritten auskommen. Aus diesem Grund betrachten wie Komplexitaetsklassen, die gross genug sind darueber hinwegzusehen. Def. Polynomielle Turingmaschine: Eine deterministische TM M hat polynomielle Laufzeit, wenn es ein Polynom p gibt, sodass die Maschine M bei Eingabe x hoechstens p(|x|) viele Schritte rechnet. Man definiert allgemeiner auch die Laufzeit einer beliebigen TM als Funktion (z.B exponentiell, linear etc) der Eingabelaenge und studiert auch Laufzeiten nichtdeterministischer Maschinen. Bem.: Die Simulation einer Mehrband- durch eine Einband TM verursacht quadratischen Overhead, daher ist es egal, ob man "polynomiell" fuer Ein- oder Mehrband definiert. Intuition fuer Polynome: Verdopplung der Eingabelaenge geht einher mit Ver-k-fachung der Rechenzeit, wobei k fest ist. Z.B. quadratische Laufzeit: Verdopplung der Eingabelaenge -> Vervierfachung der Rechenzeit. Dagegen exponentielle Laufzeit: Verlaengerung der Eingabelaenge um Eins -> Doppelte Rechenzeit. Definition: Ein Problem A <= Sigma* ist in der Komplexitaetsklasse P, wenn es eine (deterministische) polynomielle TM M gibt mit A = L(M). Gemeinhin wird "polynomiell" mit "praktisch durchfuehrbar" gleichgesetzt. Haeufig sind "echte" Algorithmen mit einer cleveren Idee polynomiell, waehrend blindes Durchprobieren exponentielle Laufzeit hat. Bsp.: Die Menge { Kodierung(G,w) | G eine CFG, w ein Wort, w: L(G) } ist in P, da es den CYK-Algorithmus gibt. Laesst man da auch kontext-sensitive Grammatiken zu, dann ist die Menge hoechstwahrscheinlich nicht mehr in P. Satz: Ist f:P, dann ist L LOOP-berechenbar. Beweis: Sei M eine TM, die f in Zeit O(n^k) berechnet (dies gilt offen- sichtlich fuer alle in P berechenbaren Funktione). Diese laesst sich durch eine 1-Band-TM in Zeit O(n^2k) simulieren, dies wiederum durch ein GOTO- Programm in Zeit O(n^2k), dies durch ein WHILE-Programm mit einer WHILE- Schleife in Zeit O(n^2k). Da die Laufzeit dieses Programms durch ein Polynom p'(n) beschraenkt ist, laesst sich die WHILE-Schleife ersetzen durch y := p'(n); LOOP y DO. Da Addition und Multiplikation LOOP- berechenbar ist, ist somit auch f LOOP-berechenbar. QED Als naechstes definieren wir NP, die nichtdeterministische Variante von P. Beispiele fuer Probleme in P: Grundrechenarten auf den natuerlichen Zahlen ("Ist das i-te Bit von x +-*/ y gleich 1?"). Loesen linearer Gleichungssysteme. Kuerzeste Wege in Graphen ("Ist der kuerzeste Weg hoechstens k lang? Fuehrt er ueber x?"). Schedulingprobleme: Gegeben Aufgaben mit Start- und Endzeiten. Wie kann man moeglichst viele Auftraege abarbeiten? Beispiele fuer Probleme, von denen man nicht weiss, ob sie in P sind: Finden einer kuerzesten Rundreise (alle Staedte besuchen), optimale Stundenplanung, Graphenfaerbung, Schedulingprobleme: Gegeben Auftraege mit Dauern (Zeitpunkt egal). Wie kann man moeglichst viele abarbeiten? Aequivalent: Waescheleinenproblem. Definition: Komplexitaetsklasse NP: Ein Problem A <= Sigma* ist in der Klasse NP, wenn es ein Problem B in P, sowie ein Polynom p gibt, derart dass x:A <==> es existiert y mit |y| <= p(|x|) und (x,y):B Interpretation: x:A gdw eine "Loesung" y existiert und man kann in polynomieller Zeit verifizieren, ob ein vorgelegtes Wort "Loesung" zu gegebener Instanz ist. Loesungen duerfen nur polynomielle Laenge haben. Bem: Trivialerweise gilt: Wenn A:P dann auch A:NP. Bem: Traditionell wird NP ueber nichtdeterministische polynomielle TM definiert. Mit Nichtdeterminismus kann man ja die "Loesung" raten. Bsp.: Ein Hamilton-Kreis in einem ungerichteten Graphen ist eine Tour durch den Graphen, die jeden Knoten genau einmal besucht. Ein Euler- Kreis ist eine Tour, die jede Kante genau einmal besucht. Es gilt: 1) { G | G hat Euler-Kreis } : P 2) { G | G hat Hamilton-Kreis } : NP (und vermutlich nicht in P) zu 1) G hat Euler-Kreis genau dann, wenn jeder Knoten gerade Grad hat. Dies kann offensichtlich von einer det. TM in polynomialer Zeit getestet werden. zu 2) Ein vorgelegter Hamilton-Kreis ("Loesung") kann offensichtlich in polynomieller Zeit erkannt werden. Bem.: Offensichtlich gilt P <= NP. Ob P=NP gilt, ist seit ca. 1970 unbekannt und wird auch als das groesste Problem der theor. Informatik bezeichnet. Analogie: P =~= Entscheidbar, NP =~= Semi-entscheidbar Leider ist es bisher nicht moeglich, ein Problem in NP \ P anzugeben. Dennoch kann man, sozusagen proaktiv, Reduktionen betrachten: Definition (Klasse FP): Eine Funktion f:Sigma* -> Sigma* ist in polynomieller Zeit berechenbar, kurz f : FP, wenn es eine polynomielle Turingmaschine gibt, die f berechnet. (Bei Eingabe w haelt die Maschine irgendwann an (nach p(|w|) Schritten) und auf dem Band steht dann f(w). Satz: Sind f, g:FP, so auch die Komposition h(x)=g(f(x)). Beweis: Seien p, q Polynome, die die Laufzeit von Maschinen fuer f bzw g beschraenken. Wir koennen annehmen, dass p und q monoton sind, ggf durch Weglassen von Monomen mit negativen Koeffizienten. Die offensichtliche Maschine, die h berechnet hat nun bei gegebener Eingabe x eine Laufzeit T(x), die durch p(|x|) + q(|f(x)|) + c.(|x| + |f(x)|) fuer eine Konstante c nach oben abgeschaetzt werden kann. Nun gilt |f(x)| <= p(|x|) da ja die einzelnen Symbole der Ausgabe f(x) im Rahmen der Rechenzeit eins nach dem anderen hingeschrieben werden muessen. Somit gilt fuer die Gesamtrechenzeit T <= p(|x|) + q(p(|x|)) + c.(|x| + p(|x|)) Das aber ist ein Polynom in |x|. QED Definition: A<= Sigma*, B<=Sigma*. Das Problem A ist polynomiell reduzierbar auf das Problem B, i.Z. A <=P B, wenn es eine Funktion f:FP gibt, sodass x:A <==> f(x):B Wenn A <=P B und B:P so folgt A:P. Ausserdem folgt aus A <=P B und B <=P C, dass A <=P C. Definition: Ein Problem B ist NP-schwer (auch NP-hart), wenn A <=P B fuer alle Probleme A in NP erfuellt ist. Ein Problem B ist NP-vollstaendig, wenn es NP-schwer ist und zusaetzlich selbst in NP liegt. NP-vollstaendige Probleme sind also diejenigen Probleme in NP, die bzgl. <=P maximalen Schwierigkeitsgrad haben. Zum Beispiel ist das folgende (entscheidbare) Problem NP-hart: EVAL = {(P,x) | P ist ein LOOP Programm, welches bei Eingabe x Ergebnis 1 liefert} Ist naemlich A in NP, so ist die charakteristische Funktion von A leicht LOOP berechenbar. Liegt die Eingabe x vor, so ist die Zahl der moeglichen Loesungen durch |Sigma|^p(|x|) beschraenkt und man kann mit geschachtelten LOOP-Schleifen alle moeglichen Loesungen durchprobieren und pruefen. Sei P das entsprechende LOOP Programm. Die Funktion f(x) = (P,x) ist in FP und liefert eine Reduktion von A auf EVAL. Das Problem EVAL ist aber selbst nicht in NP, daher nicht NP-vollstaendig. Das Erfuellbarkeitsproblem -------------------------- Wir fixieren eine endliche Menge von Variablen V, die Werte in {0,1} (0 = falsch, 1 = wahr) annehmen sollen. Ein Literal ist entweder eine Variable x:V oder eine negierte Variable ~x. Es gibt also zweimal soviele Literale wie Variablen. Eine Klausel ist eine Menge von Literalen {l1,..,lk}. Man versteht eine Klausel als die Disjunktion ("oder") ihrer Variablen. Dementsprechend verwendet man auch die Notationen l1 v ... v lk l1 | ... | lk Die leere Klausel bezeichnet Falschheit. Beispiele mit V ={x,y,z,w}: ~x | ~y | w ~x | y | w x ~y Die ersten beiden Klauseln kann man auch in der Form x&y -> w x -> y|w schreiben, denn ~x|~y|w bedeutet ja gerade, dass wenn x und y wahr sind, dann auch wahr sein muss. Eine konjunktive Normalform ist gegeben durch eine Menge von Klauseln. Eine Belegung ist eine Funktion eta:V->{0,1}, die also jeder Variablen einen Wahrheitswert zuordnet. Eine Belegung eta erfuellt eine Klausel k, wenn es ein Literal l in k gibt, sodass eta(l)=1. Man setzt hierbei eta(~x)=1-eta(x). Die Belegung erfuellt eine KNF K, wenn sie alle Klauseln in K erfuellt. Das Erfuellbarkeitsproblem fuer konjunktive Normalform, kurz KNF-SAT besteht darin, zu gegebener KNF festzustellen, ob es eine Belegung gibt, die sie erfuellt: KNF-SAT: Gegeben: Eine endliche Menge von Variablen V und eine KNF K ueber V. Gefragt: Existiert eine Belegung, die K erfuellt. Diese "Gegeben-Gefragt"-Spezifikation definiert KNF-SAT formal als die Menge aller Paare (V,K), geeignet codiert als Woerter ueber einem bestimmten Alphabet, sodass eine erfuellende Belegung fuer K existiert. Die "Gegeben-Gefragt" Notation abstrahiert von der Wahl der Codierung, vom Alphabet und auch von der Formalisierung eines "Problems" als Sprache ueber einem Alphabet. Satz: KNF-SAT ist in NP. Bemerkung: Hat man ein Entscheidungsverfahren fuer KNF-SAT, so kann man ohne grossen Zusatzaufwand auch eine erfuellende Belegung bestimmen. Hierzu setzt man zunaechst die erste Variable x1 auf 0 und berechnet die Klauselmenge, die man erhaelt, indem man alle Literale x entfernt und alle Klauseln loescht, die das Literal ~x enthalten. Ist die resultierende Klauselmenge noch erfuellbar, so kann man mit x2 weiterfahren, ansonsten muss x1=1 die richtige Setzung gewesen sein und man ersetzt entsprechend jedes Vorkommen von x1 durch 1, vereinfacht und arbeitet weiter. Viele andere Probleme lassen sich auf KNF-SAT polynomiell reduzieren, indem man die moeglichen Loesungen durch die Variablenbelegungen repraesentiert und die Klauseln dazu nutzt, die problemspezifischen Einschraenkungen zu formulieren. Beispiel: 3-COL: Gegeben ist ein ungerichteter Graph G = (V,E). V ist die Knotenmenge, E <= VxV die Menge der Kanten. Gefragt: Gibt es eine Zuordnung von Farben c:{r, w, b} zu den Knoten derart, dass keine durch eine Kante verbundene Knoten dieselbe Farbe erhalten? Es gilt 3-COL <=P KNF-SAT. Ist naemlich ein Graph G = (V,E) gegeben, so konstruiert man wie folgt eine Instanz f(G) von KNF-SAT: Fuer jeden Knoten e fuehrt man drei Variablen ein: er, ew, eb, sowie die Klauseln {er,ew,eb}, {~er, ~ew}, {~er, ~eb}, {~ew, ~eb} Diese stellen sicher, dass genau eine der drei Variablen gesetzt ist (auf 1). Zusaetzlich fuehrt man fuer jede Kante e-f die Klauseln {~er,~fr}, {~ew,~fw}, {~eb, ~fb} ein, wodurch sichergestellt ist, dass verbundene Knoten nicht dieselbe Farbe bekommen. Aehnlich zeigt man HAMILTON <=P KNF-SAT: Fuer jede Kante (u,v) in E fuehrt man eine Variable x(u,v) ein. Die Idee ist, dass diejenigen Kanten (u,v), fuer die x(u,v)=1 einen Hamiltonschen Kreis bilden. Die Klauseln sollen gerade das sicherstellen: 1) Zu jedem Knoten v gibt es Knoten u1, u2, sodass x(u1,v)=1 und x(v,u2)=1: Hierzu fuehren wir fuer jeden Knoten v eine eigene Klausel ein, deren Literale gerade die x(u1,v),x(v,u2) sind. Deren Anzahl ist |V|^2. 2) Jeder Knoten kommt hoechstens in zwei Kanten vor und zwar einmal links und einmal rechts: Hierzu fuehren wir fuer je vier Knoten v,u1,u2,u3 die folgenden zwei Klauseln ein: ~x(u1,v) | ~x(v,u2) | ~x(v,u3) ~x(u1,v) | ~x(v,u2) | ~x(u3,v) Die Anzahl dieser Klauselpaare ist also |V|^4 Erfuellt eine Belegung alle genannten Klauseln, so definiert sie einen Hamiltonschen Pfad, insbesondere ist also die erzeugte Klauselmenge erfuellbar genau dann wenn im gegebenen Graphen ein Hamiltonscher Kreis existiert. Sicherlich ist die konstruierte Klauselmenge in polynomieller Zeit berechen- und hinschreibbar, sodass tatsaechlich eine Reduktion definiert wurde. Es gilt in der Tat auch KNF-SAT <=P HAMILTON; das ist aber deutlich schwerer nachzuweisen. Auf aehnliche Weise lassen sich auch andere viele andere kombinatorische Probleme als KNF-SAT Instanzen kodieren. In der Tat kann man KNF-SAT als eine Art Spezifikations- oder Programmiersprache fuer solche Probleme auffassen. NP Vollstaendigkeit von KNF-SAT ------------------------------- Satz ("Satz von Cook"): KNF-SAT ist NP-vollstaendig. Beweis: Sei A:NP und x:A <==> existiert y. |y|<=p(|x|) & (x,y):B, wobei p ein Polynom ist und B:P. Sei M eine polynomielle TM fuer B. Wir muessen eine Reduktion A <=P KNF-SAT konstruieren. Sei also x:Sigma* gegeben. Wir bestimmen n so, dass die Laufzeit, wie auch die Groesse der Bandinhalte einer Berechnung von M auf Eingabe (x,y) mit |y|<=p(|x|) durch n beschraenkt ist. Es gilt n = q(|x|) fuer ein festes Polynom q. Wir repraesentieren Bandinhalte als Woerter der Laenge n. Wir fuehren nun die folgenden Variablen ein: 1) Fuer Zustand z, Zeitpunkt t (0 <= t <= n) eine Variable zust(t,z) ("Zustand zum Zeitpunkt t ist z") 2) Fuer Zeitpunkt t (0 <= t <= n) und Bandposition p (-n <= p <= n) eine Variable kopf(t,p) ("Kopf steht zum Zeitpunkt t an Position p") 3) Fuer Bandsymbol a:Gamma, Zeitpunkt t (1<=t<=n) und Bandposition p (-n <= p <= n) eine Variable band(t,p,a) ("Bandinhalt zum Zeitpunkt t an Position p ist a") Man beachte, dass die Zahl der eingefuehrten Variablen ein Polynom in n und somit auch in |x| ist. Genauer gesagt ist sie (n+1)*|Z| + (n+1)(2n+1) Es ist klar, dass jeder Folge von Konfigurationen der Laenge n eine Belegung dieser Variablen entspricht und umgekehrt. Durch die folgenden Klauseln stellen wir jetzt sicher, dass nur solche Belegungen infrage kommen, die eine akzeptierende Berechnung der Laenge n von Eingabe x aus kodieren. Ist die resultierende Klauselmenge noch erfuellbar, so gibt es eine akzeptierende Berechnung, also x:A und umgekehrt. Die erforderlichen Klauseln sind wie folgt: 1) Fuer -n<=p<=n Klauseln mit den Variablen band(0,p,a), welche besagen, dass der initiale Bandinhalt von der Form (x,y) ist fuer ein beliebiges y mit |y|<=p(|x|). 2) Die Klausel kopf(0,1) ("Zu Beginn steht der Kopf auf Position 1.") 3) Fuer -n <= i1 < i2 <= n und 0 <= t <= n die Klausel ~kopf(t,i1) v ~kopf(t,i2) (Der Kopf steht jeweils an hoechstens einer Stelle) 4) Fuer -n <= i < n und 0 <= t <= n und a1, a2 : Gamma mit a1 =/= a2 die Klausel ~band(t,i,a1) v ~band(t,i,a2) (Hoechstens ein Symbol an jeder Bandposition und Zeitpunkt) 5) Die Klausel zust(n,z_A), wobei z_A der akzeptierende Zustand ist. ("Am Ende der Rechnung wurde akzeptiert") 6) Fuer 0<=t<n, -n<=p<=n, Zustand z, Symbol a eine Klauselmenge, die der folgenden aussagenlogischen Formel entspricht: zust(t,z) & band(t,p,a) & kopf(t,p) -> \/_((z',b,d):delta(z,a) (kopf(t+1,p+d) & band(t+1,p,b) & zust(t+1,z') wobei diesmal d:{-1,0,1} statt {L,R,N} gewaehlt wird. Sollte p+d nicht im Bereich -n..n liegen, so lassen wir das entsprechende Disjunkt weg. Man erhaelt die gewuenschte Klauselmenge durch Anwenden der de Morganschen Regeln, z.B. A&B -> (U&V | W&Z) = ~A | ~B | (U&V) | (W&Z) = (~A|~B|U|W)&(~A|~B|U|Z)&(~A|~B|V|W)&(~A|~B|V|Z) Es entstehen also hier 4 Klauseln. In der obigen Anwendung entstehen jeweils 3^(|delta(z,a)|) viele Klauseln, was eine feste, von |x|, unabhaengige Groesse ist und somit polynomial in |x|. 7) Fuer 0 <= t < n, -n <= p <=n und Symbol a die Klausel band(t,p,a) & ~kopf(t,p) -> band(t+1,p,a) bzw. als Disjunktion geschrieben: ~band(t,p,a) | kopf(p) | band(t+1,p,a) ("Diejenigen Bandpositionen, an denen sich der Kopf nicht befindet, bleiben stehen.") Es ist jetzt aufgrund der Konstruktion klar, dass die genannte Klauselmenge genau dann erfuellbar ist, wenn eine akzeptierende Berechnung existiert. Damit ist die verlangte Reduktion von A auf KNF-SAT gegeben. QED 3.2.3: Weitere NP-vollstaendige Probleme: 3KNF-SAT: Gegeben eine Menge von Klauseln mit jeweils genau 3 Literalen. Gefragt ist nach der Erfuellbarkeit dieser Klauselmenge. Satz: 3KNF-SAT ist NP-vollstaendig. Beweis: Es genuegt zu zeigen KNF-SAT <=P 3KNF-SAT. Hat man eine Klausel l1|...|lk gegeben, so fuehrt man neue Variablen qi ein und fuehrt folgende Dreierklauseln ein: ~l1|q1, ~q1|l1 ("q1 = l1") ~q1|q2, ~l2|q2, ~q2|q1|l2 ("q2 = q1|l2") ~q2|q3, ~l3|q3, ~q3|q2|l3 ("q3 = q2|l3") ... ... ("qk = q(k-1)|lk") und nimmt schliesslich noch die Klausel qk hinzu, deren Wahrheitswert ja gerade der Disjunktion der li entspricht. QED SAT: Ist eine gegebene aussagenlogische Formel erfuellbar? Satz: SAT ist NP-vollstaendig. Beweis: Klarerweise ist KNF-SAT <=P SAT, somit ist SAT NP-hart. Auf der anderen Seite ist SAT natuerlich in NP, da ja eine geratene erfuellende Belegung in polynomialer Zeit bestaetigt werden kann. QED Man kann SAT auch direkt auf 3KNF-SAT reduzieren, indem man fuer jede Teilformel eine frische Variable einfuehrt und wie beim letzten Beweis durch 3er-Klauseln sicherstellt, dass diese die gewuenschte Belegung erfaehrt. Was man nicht machen kann, ist die aussagenlogische Formel durch Umformungen auf konjunktive Normalform zu bringen, da sich dabei die Groesse u.U. exponentiell aufblaeht. Es handelte sich dabei also nicht um eine in polynomialer Zeit berechenbare Reduktion. Interessanterweise ist das Problem 2KNF-SAT in P. Ab jetzt werden wir ein kanonisches Beispiel einer 3KNF-SAT zur Illustration weiterer NP-Vollstaendigkeitsbeweise verwenden: F = {k1, k2, k3} (3 Klauseln) k1 = x1 v ~x3 v x5 k2 = ~x1 v x5 v x4 k3 = ~x2 v ~x2 v ~x5 x3 -> x1 v x5 x1 -> x4 v x5 x2 -> x5 in fuenf Variablen x1,x2,x3,x4,x5. MENGENUEBERDECKUNG: Gegeben: Ein System von n Teilmengen S1..Sn einer endlichen Menge T und eine Zahl k <= n. Gefragt: Existiert eine Auswahl von k Teilmengen Si1..Sik deren Vereinigung bereits ganz T ergibt? Satz: MENGENUEBERDECKUNG IST NP-vollstaendig. Beweis: Dass MENGENUEBERDECKUNG in NP ist, ist klar: Hat man eine entsprechende Auswahl der Teilmengen vorgegeben, so faellt die Ueberpruefung leicht. Umgekehrt konstruieren wir eine Reduktion von KNF-SAT auf MENGENUEBERDECKUNG. Seien also m Klauseln K1..Km gegeben, in den Variablen x1..xn. Fuer jede Variable xj fuehren wir jetzt zwei Mengen Sj und Sj' ein. Die Idee ist, dass wenn eine Ueberdeckung Sj beinhaltet, dann xj=1 genommen werden kann und wenn Sj' ausgewaehlt wird, dann xj=0 genommen werden kann um eine erfuellende Belegung zu erhalten. Sj = {i | 1<=i<=m, xj kommt in Ki positiv vor} u {m + j} Sj' = {i | 1<=i<=m, xj kommt in Ki negativ vor} u {m + j} T = {1,...,m+n} Gesucht ist eine Ueberdeckung mit hoechstens n (Zahl der Variablen) Mengen. Da ja die Zahlen m+j ueberdeckt werden muessen, muss eine Ueberdeckung fuer jedes j<=n entweder Sj oder Sj' aber nicht beide enthalten. Das Ueberdecken eines 1<=i<=m bedeutet aber, dass unter der zugeordneten Belegung die Klausel i erfuellt wird. Also entsprechen Ueberdeckungen mit n Mengen genau den erfuellenden Belegungen. QED Im Beispiel waere S1 = {1,4} S1' = {2,4} S2 = {5} S2' = {3,5} S3 = {6} S3' = {1,6} S4 = {2,7} S4' = {7} S5 = {1,2,8} S5' = {3,8} CLIQUE: Gegeben: ein (ungerichteter) Graph G = (V,E) und eine Zahl k. Gefragt: Besitzt G eine Clique der Groesse k (oder mehr). Eine Clique ist eine Teilmenge von Knoten, so dass je zwei verschiedene Knoten aus der Teilmenge ueber eine Kante verbunden sind. (Kante=befreundet sein, Clique=jede(r) mit jede(r,m) befreundet.) Satz: CLIQUE ist NP-vollstaendig. Dass CLIQUE in NP ist, ist klar. Fuer die NP-Haerte verwenden wir eine Reduktion von 3KNF-SAT. Sei l(i,k), i=1..m, k=1..3 das k-te Literal der i-ten Klausel in einer Klauselmenge C. Wir konstruieren einen Graphen mit den Knoten {(i,k) | i=1..m, k=1..3} und verbinden (i,k) mit (i',k'), wenn i=/=i' und ausserdem l(i,k) und l(i',k') sich nicht gegenseitig ausschliessen. Dieser Graph hat eine Clique der Groesse m genau dann wenn C erfuellbar ist. Ist naemlich eine erfuellende Belegung gegeben, so waehlt man aus jeder Klausel i ein erfuelltes Literal k aus. Die l(i,k) bilden dann eine Clique der Groesse m. Umgekehrt muss eine Clique der Groesse m fuer jedes i einen Knoten (i,m_i) beinhalten. Man setzt nun eine Belegung eta so fest, dass eta(l(i,m_i)) = 1 wird. QED Im Beispiel gaebe es also 9 Knoten (i,k) mit i=1,2,3 und k=1,2,3. Es gibt eine Verbindung von (2,1) nach (3,2), da das 1-te Literal in k2 ~x1 ist und das 2-te Literal in k3 ~x2 ist. Die beiden sind aber kompatibel. Andererseits gibt es keine Verbindung von (1,1) nach (2,1) da die entsprechenden Literale x1 und ~x1 inkompatibel sind. VERTEX-COVER: Gegeben ungerichteter Graph G=(V,E) und eine Zahl k. Gefragt: Gibt es eine Auswahl U<=V von hoechstens k Knoten, sodass jeder Kante einen der ausgewaehlten Knoten enthaelt? Satz: VERTEX-COVER ist NP-vollstaendig. VERTEX-COVER in NP ist klar. Ausserdem gilt CLIQUE <=P VERTEX-COVER vermoege der Reduktion f(V,E) = ((V, Komplement von E), |V|-k). Es gilt: (V,E) besitzt eine Clique C der Groesse k <=> Im Komplementgraphen sind die Knoten von C paarweise nicht verbunden <=> Die Menge V \ C bildet eine Ueberdeckung. QED RUCKSACK: Gegeben natuerliche Zahlen a1..an und b. Gefragt: gibt es eine Teilmenge I <= {1,...,n} sodass summe{a_i | i:I} = b. Beachtung: die Laenge der ai und b in der Binaerdarstellung geht hier in die Problemgroesse ein. Satz: RUCKSACK ist NP vollstaendig. Beweis: RUCKSACK in NP ist klar. Fuer die Haerte geben wir eine Reduktion 3KNF-SAT <= RUCKSACK an. Sei eine Instanz von 3KNF-SAT mit m Klauseln k1..km und n Variablen x1..xn gegeben. Die Zahlen a_i und b, die wir konstruieren haben alle m + n Stellen im Zehnersystem. Fuer jede Variable xj fuehren wir zwei Zahlen uj und vj ein. Hierbei hat uj eine 1 in der i-ten Position, wenn xj in ki positiv vorkommt und eine 1 in der m+j-ten Position. vj eine 1 in der i-ten Position, wenn xj in ki negativ vorkommt und eine 1 in der m+j-ten Position. Ausserdem gibt es noch Zahlen ci mit einer 1 in der i-ten Position di mit einer 2 in der i-ten Position. Die Zahlen haben 0-er in allen nicht explizit erwaehnten Positionen. Aus diesen Zahlen laesst sich eine Auswahl zu 444....444111....111 `--------´`--------´ m n summieren genau dann, wenn die gegebene 3KNF erfuellbar ist. Im Beispiel haben wir die Zahlen u1 = 100 10000 u2 = 000 01000 u3 = 000 00100 u4 = 010 00010 u5 = 110 00001 v1 = 010 10000 v2 = 001 01000 v3 = 100 00100 v4 = 000 00010 v5 = 001 00001 c1 = 100 00000 c2 = 010 00000 c3 = 001 00000 d1 = 200 00000 d2 = 020 00000 d3 = 002 00000 PARTITION: Gegeben natuerliche Zahlen a1..ak. Gefragt: gibt es eine Teilmenge I <= {1..k} sodass summe{a_i | i:I} = summe{ai | i nicht in I}. Satz: PARTITION ist NP-vollstaendig. Beweis: PARTITION <=P RUCKSACK, also PARTITION in NP. Umgekehrt gilt aber auch RUCKSACK <=P PARTITION wie folgt: Sei (a1..ak,b) eine Instanz von RUCKSACK und M=summe{ai | i=1..k}. Die Instanz (a1,...,ak,M-b+1,b+1) von PARTITION hat eine Loesung genau dann, wenn die gegebene Instanz von RUCKSACK eine Loesung besitzt. QED BIN-PACKING: Gegeben n natuerliche Zahlen a1..an und zwei weitere natuerliche Zahlen b und k. Gefragt: Koennen die Zahlen a1..an so in hoechstens k Gruppen aufgeteilt werden, dass die Summe der Zahlen in jeder Gruppe <= b ist. Deutung: b = Behaeltergroesse, k = Zahl der Behaelter. Satz: BIN-PACKING ist NP-vollstaendig. Beweis: BIN-PACKING in NP ist klar. Fuer die Haerte reduzieren wir PARTITION auf BIN-PACKING: (a1..ak) |-> Behaeltergroesse b = summe{ai | i=1..k} / 2 (ggf alles mit 2 durchmultiplizieren), Zahl der Behaelter k = 2 Objekte: a1,...,ak. QED DIR-HAMILTON: Gegeben: ein gerichteter Graph G=(V,E). Gesucht: eine Bijektion pi:{1,...,|V|}->V sodass gilt: pi(i)->pi(i+1) ist eine Kante fuer alle i=1..|V|-1 und ausserdem ist pi(|V|)->pi(1) eine Kante. Mit anderen Worten ist ein geschlossener Kantenzug gesucht, der jeden Knoten genau einmal besucht. Satz: DIR-HAMILTON ist NP-vollstaendig. Beweis: DIR-HAMILTON in NP ist klar. Fuer die Haerte reduzieren wir von 3-KNF-SAT aus. Details siehe Schoening. QED HAMILTON: Dasselbe wie DIR-HAMILTON, nur fuer ungerichtete Graphen. Satz: HAMILTON ist NP-vollstaendig. Beweis: Man reduziert DIR-HAMILTON auf HAMILTON. Details siehe Schoening. TRAVELLING-SALESMAN: Gegeben: eine n x n Matrix mit Eintraegen aus N und eine Zahl k. Gefragt: gitb es eine Permutation pi:{1..n}->{1..n} sodass M(pi(1),pi(2)) + M(pi(2),pi(3)) + .. + M(pi(n-1),pi(n)) + M(pi(n),pi(1)) <= k ? Deutung: Es seien n Staedte in einer bestimmten Reihenfolge zu besuchen. M(i,j) gibt die Entfernung der Stadt i von j an. Gibt es eine Rundreise, der Gesamtlaenge kuerzer als k ist? Satz: TRAVELLING-SALESMAN ist NP-vollstaendig. Beweis: Triviale Reduktion von HAMILTON. 3-FAERBBARKEIT: Gegeben ein ungerichteter Graph G=(V,E). Gefragt: Gibt es eine Funktion f:V->{1,2,3} sodass fuer jede Kante {u,v}:E gilt f(u) =/= f(v). Deutung: Lassen sich die Knoten so mit 3 Farben einfaerben, dass keine zwei beanchbarten Knoten dieselbe Farbe erhalten. Satz: 3-FAERBBARKEIT ist NP-vollstaendig. Beweis: Durch Reduktion von 3KNF-SAT an. Details siehe Schoening. IV Logik -------- 1. Die Arithmetik. Terme sind durch folgende Grammatik definiert: Tm ::= x | 0 | 1 | Tm + Tm | Tm * Tm Hierbei rangiert x ueber eine abzaehlbar unendliche MEnge von Variablen, z.B. x1,x2,x3,x4,x5,... Formeln der Arithmetik sind durch folgende Grammatik definiert: Fo ::= Tm = Tm | All x.Fo | Ex x.Fo | Fo&Fo | ~Fo | Fo v Fo | Fo->Fo Zum Beispiel ist phi := Ex z.x+z=y eine Formel. Man definiert in offensichtlicher Weise die freien Variablen einer Formel. ZumBeispiel hat phi die freien Variablen x und y. Die Bedeutung einer Formel haengt von der Belegung der freien Variablen ab. Alle Variablen rangieren ueber natuerliche Zahlen; die Bedeutung der Symbole +, 0, 1, =, &, v, ->, All, Ex ist die allgemein uebliche. Hat zum Beispiel x den Wert 7 und y den Wert 10, so ist phi wahr, da ja zum Beispiel z=3 gewaehlt werden kann. Im allgemeinen ist phi wahr, genau dann wenn der Wert von x kleiner oder gleich dem Wert von y ist. Man schreibt kurz phi(x,y) <=> x<=y und sagt, phi definiere (in der Arithmetik) die kleiner oder gleich Relation. Ebenso laesst sich die Relation z = x DIV y definieren durch Ex r. x = z*y+r & r+1 <= y wobei natuerlich <= durch die obige Formel phi zu ersetzen ist. Ist irgendeine Relation (in der Arithmetik) definierbar, so erlauben wir uns so aehnlich wie bei den LOOP Programmen, sie direkt in Formeln zu verwenden. Ist der Graph einer Funktion definierbar, wie etwa der Graph der Funktion DIV in obigem Beispiel, so erlauben wir uns auch die Verwendung solch einer Funktion in Termen. Zum Beispiel ist All x.All y. y * (x DIV y) <= x eine Abkuerzung fuer All x.All y.Ex m.(m = x DIV y) & y * m <= x und im uebrigen eine wahre Aussage. Satz: Ist f:N^n->N berechenbar, so ist {(y,xs) | f(xs)=y} in der Arithmetik definierbar. Beweis: Siehe Schoening oder als Uebung. Eine Formel, die keine freien Variablen enthaelt heisst Satz. Ein Satz ist entweder wahr oder falsch. Korollar: Die Menge aller wahren Saetze ist nicht rekursiv aufzaehlbar. Beweis: Sei f(x) = 0, falls x:K (x angewandt auf x haelt) und undefiniert sonst. f ist berechenbar, also gibt es eine Formel phi(x) sodass phi(n) wahr ist, genau dann wenn n:K. Hierbei bezeichnet phi(n) den Satz, den man aus phi erhaelt, indem man jedes Vorkommen von x durh 1+...+1 (n Mal) ersetzt. Somit ist aber ~phi(n) wahr, genau dann, wenn n nicht in K. Waere nun die Menge der wahren Saetze r.e., so auch N\K, was nicht der Fall ist. Das aber bedeutet, dass es keinen formalisierten Beweisbegriff geben kann, mit dem alle wahren Saetze der Arithmetik bewiesen werden koennen. Was ist eigentlich ein formalisierter Beweis ? Nun, wir koennen sagen, dass ein Beweissystem einfach eine entscheidbare Relation Bew auf N * N ist, wobei Bew(n,f) bedeuten soll, dass n einen Beweis codiert (in einem geeigneten Binaerformat), der den durch f codierten Satz der Arithmetik beweist. Das Beweissystem sollte korrekt sein in dem Sinne, dass aus Bew(n,f) folgt, dass der durch f codierte Satz wahr ist. Gibt es auch umgekehrt fuer jeden Satz f einen Beweis, also ein n:N mit Bew(n,f), so ist das Beweissystem vollstaendig. Wir haben soeben gezeigt, dass es fuer die Arithmetik kein vollstaendiges Beweissystem gibt. Das ist der Goedelsche Unvollstaendigkeitssatz. Goedel selbst ist beim Beweis seines Theorems etwas direkter und aus philosophischer Sicht vielleicht interessanter vorgegangen. Er gibt sich ein beliebiges korrektes Beweissystem vor und argumentiert, dass die Relation Bew in dr Arithmetik definierbar ist. Er argumentiert weiter, dass die Funktion subst definiert durch subst(f,n) = Code desjenigen Satzes, den man durch Einsetzen von 1+...+1 (n Mal) fuer die einzige freie Variable in der durch f codierten Formel erhaelt; 0, falls f keine Formel mit genau einer freien Variablen codiert. auch in der Arithmetik definierbar ist. Dann definiert er folgende Formel: G(x) = ~Ex y. Bew(y,subst(x,x)) bezeichnet dann mit g den Code dieser Formel (mit genau einer freien Variablen!) und definiert den Goedelsatz G(g). Es gilt G(g) <=> ~ Ex y.Bew(y,subst(g,g)) <=> G(g) ist nicht beweisbar. Letzteres deshalb, weil subst(g,g) gerade die Formel G(g) codiert. Der Goedelsatz sagt also aus, dass er selbst nicht beweisbar ist. Daraus folgt sofort, dass der Goedelsatz wahr ist, aber keinen Beweis besitzt. ENDE DER VORLESUNG.
Artikelaktionen