Zusammenfassung Theoretische Informatik (c) 2002-07-02 F.M. Suchanek http://suchanek.name/texts/summaries/infod.txt Dieses ist die Zusammenfassung des Kurses "Informatik D" von Prof. Sperschneider an der Universitaet Osnabrueck im SS 2002. Sie lehnt sich stark an das sehr ausfuehrliche Skript. Durch das Weiterlesen akzeptiert der Leser, dass der Autor keinerlei Verantwortung fuer die Richtigkeit oder Vollstaendigkeit dieser Zusammenfassung uebernimmt. Wenn jemand einen Fehler gefunden hat, so waere ich fuer eine Mail dankbar. Nur so habe auch ich etwas von der Veroeffentlichung dieser Zusammenfassung. Meine E-Mail-Adresse ist f.m.suchanek@zweb.de, wobei das 'z' aus der Adresse geloescht werden muss. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Intro ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Siehe auch cl.txt (Computerlinguistik) totale Funktion: Eine Funktion f:A -> B, die auf allen Elementen von A definiert ist. partielle Funktion: Eine Funktion f:A -> B, die nicht auf allen Elementen von A definiert sein muss. Buchstabe, Zeichen: Ein Symbol. Sonderzeichen: Ein Meta-Symbol. Beispiele sind Blank (geschrieben '_'), Kellerbodensymbol oder Eingabeende-Symbol. Alphabet: Eine Menge von Symbolen ohne Sonderzeichen. Wort: Ein Wort ueber einem Alphabet ist eine endlich lange Folge von Symbolen dieses Alphabets. w = (w1,w2,...wn) = w1w2...wn Laenge: Die Laenge eines Wortes ist die Anzahl seiner Symbole. |w|=n epsilon, eps: Das leere Wort mit |eps|=0. // In CL bezeichnet Epsilon ein fehlendes Symbol Menge aller Woerter: Die Menge aller Woerter ueber einem Alphabet S * mit beliebiger Laenge heisst S* * mit einer Laenge > 0 heisst S+ * mit einer festen Laenge n heisst S^n Verkettung: Die Verkettung zweier Woerter ist das Wort mit allen Symbolen des ersten Wortes gefolgt von allen Symbolen des zweiten Wortes. u=(u1,u2,...un), v=(v1,v2,...vm), uv=(u1,u2,...un,v1,v2,...vm) Spiegelung: Die Spiegelung eines Wortes ist das Wort aus denselben Zeichen in umgekehrter Reihenfolge. wmi = w[n] w[n-1] ... w[1] Praefix, Anfangswort: Das Wort u ist ein Praefix vom Wort w, wenn es ein Wort v gibt, sodass uv=w. Suffix, Endwort: Das Wort v ist ein Suffix vom Wort w, wenn es ein Wort u gibt, sodass uv=w. Infix, Teilwort: Das Wort v ist ein Teilwort eines Wortes x, wenn es Woerter u und w gibt, sodass uvw=x. (x1,x2,...xn)[i..j] = (xi,...xj) Palindrom: Ein Wort, das gleich seiner Spiegelung ist. Beispiele: "Reliefpfeiler", "aabbaa", "Ein Neger mit Gazelle zagt im Regen nie", "A man, a plan, a canal - panama". Sprache: Eine Sprache ueber einem Alphabet S ist eine Teilmenge von S*. Vereinigung: Die Vereinigung zweier Sprachen L und M ist die Menge aller ihrer Woerter. L \/ M = { u E S* : u E L | u E M} Durchschnitt: Der Durchschnitt zweier Sprachen L und M ist die Menge all derer Woerter, die sowohl in L als auch in M sind. L /\ M = { u E S* : u E L & u E M} Komplement: Das Komplement einer Sprache ist die Menge aller Woerter, die nicht in ihr enthalten sind. Lc = { u E S* : ~(u E L)} Sprachspiegelung: Die Spiegelung einer Sprache L ist die Menge Lmi aller Spiegelungen ihrer Woerter. Mengendifferenz: Die Mengendifferenz zweier Sprachen ist die Menge all derer Woerter, die in der ersten Sprache, nicht aber in der zweiten Sprache enthalten sind. L \ M = L - M = { u E L : ~(u E M)} Sprachverkettung: Die Verkettung zweier Sprachen ist die Menge all derer Woerter, die aus einem Praefix der ersten und einem Suffix der zweiten Sprache bestehen. LM = { uv : u E L & v E M} "N-fache Selbstverkettung", Endlichmalige Verkettung: Die n-fache Selbstverkettung einer Sprache ist die Menge aller Woerter, die aus n Woertern der Sprache bestehen. L^0 = {eps} L^(n+1) = L L^n "Unendliche Selbstverkettung", Iterative Verkettung: Die iterative Verkettung einer Sprache ist die Menge aller Woerter, die aus 0,1,...INF vielen Woertern der Sprache bestehen. L* = Menge aller L^n mit n=0...INF L+ = Menge aller L^n mit n=1...INF Rechtsquotient: Der Rechtsquotient zweier Sprachen ist die Menge all derer Praefixe, zu denen es ein Suffix in der zweiten Sprache gibt, sodass ihre Verkettung in der ersten Sprache ist. L M^-1 = { x : Es gibt ein y E M mit xy E L} L = M Der Rechtsquotient ist die Sprache L ohne die Suffixe aus M. Linksquotient: Der Linksquotient zweier Sprachen ist die Menge all derer Suffixe, zu denen es ein Praefix in der ersten Sprache gibt, sodass ihre Verkettung in der zweiten Sprache ist. L^-1M = { y : Es gibt ein x E L mit xy E M} M = L Der Linksquotient ist die Sprache M ohne die Praefixe aus L. Produktion: Eine Produktion ueber einem Alphabet ist ein Paar von Worten dieses Alphabets (eine konkrete Ersetzungsregel). x -> y, "x produziert y" x ist der "Input", y der "Output". Wortersetzungssystem: Eine endliche Menge von Produktionen. Produktion in einem Schritt: Ein Wortersetzungssystem produziert aus einem Wort vxu ein Wort uyv, falls es eine Produktion x -> y enthaelt. uxv |-1 uyv Produktion in endlich vielen Schritten: Ein Wortersetzungssystem produziert aus einem Wort vxu ein Wort uyv, in endlich vielen Schritten, falls es uyv in einem Schritt produziert oder falls es ein Wort z gibt, sodass uzv |-1 uyv und uzv in endlich vielen Schritten produziert werden kann. uxv |- uyv <=> uxv |-1 uyv oder es existiert ein Wort z mit uzv |-1 uyv und uxv |- uzv Ableitung: Eine Folge von Produktionen. Grammatik: Formalismus zur Erzeugung einer Sprache. Er besteht aus * einem Alphabet N der Nichtterminalsymbole (meist Grossbuchstaben) * einem Alphabet T der Terminalsymbole (meist Kleinbuchstaben) * einem Wortersetzungssystem P ueber dem Alphabet N \/ T * einem Startsymbol S E N wobei N und T disjunkt sind. Ausserdem muss das Wortersetzungssystem nur Produktionen enthalten, deren linke Seite mindestens ein Nichtterminalsymbol enthaelt. Die von einer Grammatik G erzeugte Sprache ist L(G) = { w E T* : S |- w } Die Gramnmatik ist also eine deklarative Definition einer Sprache. Satzform: Wort aus (eventuell 0) Terminalsymbolen und (eventuell 0) Nichtterminalsymbolen. s E (N \/ T)* - T* Aequivalenz von Sprache und Grammatik: Um zu beweisen, dass fuer eine Grammatik G und eine Sprache L gilt L=L(G), ist zu zeigen 1. L < L(G), d.h. L laesst sich von G erzeugen. Dieses zeigt man durch Induktion ueber der Laenge der abzuleitenden Satzformen, d.h. man zeigt fuer jede grundlegende Satzform der Sprache, dass sie durch G generiert werden kann. 2. L(G) < L ,d.h. jedes von L(G) generierte Wort gehoert L an. Dieses zeigt man durch Induktion ueber die Laenge der Ableitung, d.h. man zeigt, dass jedes in einem Schritt generierte Wort in L ist und sodann, dass jedes aus einer Satzform generierte Wort auch ein Wort aus L ist. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Endliche Automaten ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Konfiguration: Ein Tupel aus Wort, Zustand und Wort. Erkennen: Eine Eingabe als "positiv" oder "negativ" klassifizieren, wobei im Fall "positiv" positiv geantwortet wird, im Fall "negativ" hingegen nicht geantwortet zu werden muss. Entscheiden: Eine Eingabe als "positiv" oder "negativ" klassifizieren, wobei im Fall "positiv" positiv geantwortet wird und im Fall "negativ" negativ geantwortet wird. "Entscheiden" bedeutet also mehr als "Erkennen". Automat: Formalismus zur Erkennung der Sprachzugehoerigkeit eines Wortes. Er besteht aus * einer endlichen Zustandsmenge Q = {q0,q1,q2,...} * einem Alphabet N von Hilfssymbolen * einem Alphabet T von Eingabesymbolen * einem Wortersetzungssystem ueber dem Alphabet Q \/ N \/ T * einem Startkontext S E (Q \/ NQ) * einer Finalmenge F < (N \/ T)*Q(N \/ T)* wobei Q, N und T disjunkt sind. Ausserdem arbeiten die Produktionen immer auf Konfigurationen. Der Automat erkennt die Sprache L(A) = { w E T* : Es gibt f E F mit sw |- f } Ein Automat kann auf einem Band von Speicherzellen lesen und schreiben. Anfangs steht das Eingabewort auf dem Band und am Ende die Ausgabe des Automaten. In jedem Schritt ueberfuehrt der Automat eine Konfiguration aus links vom Lese/Schreibkopf stehenden Wort, internem Zustand und rechts vom Lese/Schreibkopf stehenden Wort in eine neue Konfiguration. Verbleibt der Automat am Ende in einem Zustand der Finalmenge, so "akzeptiert" er das Wort. Da Zustaende keine Nichtterminalsymbole oder Terminalsymbole sind, kann jeder Schreib/Lese-Vorgang eindeutig durch eine Produktion lqr -> l'q'r' beschrieben werden. Dabei denkt man sich q als in das Eingabewort geschriebenes Zeichen, welches die Position des Schreib/Lese-Kopfs bezeichnet. Nun entspricht beispielsweise die Produktion qa -> aq dem Weiterruecken des Schreib/Lese-Kopfes beim Lesen eines a's: "Hqallo" -> "Haqllo". Deterministischer Automat: Ein Automat, der zu jeder KOnfiguration nur eine anwendbare Produktion hat. Vollstaendiger Automat: Ein Automat, der zu jeder Konfiguration mindestens eine anwendbare Produktion hat. Terminierender Automat: Ein Automat, bei dem es zu jedem Wort w E T* eine mit sw startende Abarbeitungsfolge gibt, die mit einer Konfiguration in F endet. Vom Automat berechnete Funktion: Ein deterministischer Automat berechnet eine Funktion f: T* -> T*. Dazu steht anfangs das Argument der Funktion auf dem Band. Nach Erreichen eines Finalzustandes liest sich das Ergebnis als laengstes Wort ueber T im Arbeitsfeld des Automaten. Ist der Automat zusaetzlich noch vollstaendig und terminierend, so ist f nicht partiell, sondern total. Leseproduktion: Eine Produktion, die ein Zustands-Wort-Tupel auf einen Zustand abbildet. q a -> q' mit q,q' E Q und a E T Endlicher Automat: Ein Automat, bei dem die Menge der Nichtterminalsymbole leer ist und der nur Leseproduktionen hat. Dieser Automat kann also nur sequentiell lesen, nicht schreiben und hat ein Band, auf dem lediglich die Eingabe steht. Deterministischer endlicher Automat: Ein endlicher Automat, der zu derselben Eingabe dieselben Produktionen abarbeitet. Auch beschrieben durch ein 5-Tupel aus * einer endlichen Menge Q von Zuständen * einem Alphabet T von Eingabesymbolen * einem Startzustand s E Q * einer Menge von Finalzustaenden F < Q * einer Ueberfuehrungsfunktion d:Q x T -> Q, die jedem Paar aus Zustand und gelesenem Symbol einen Folge-Zustand zuordnet. Ist d*:Q x T* -> Q die Funktion, die einer Folge von Eingabesymbolen und einem Zustand den letztendlich resultierenden Zustand zuordnet, so ist die vom Automat erkannte Sprache L(A) = { w E T* : d*(s,w) E F} Indeterministischer endlicher Automat: Ein endlicher Automat, der zur selben Eingabe unterschiedliche Produktionen abarbeiten kann. Auch beschrieben durch ein 5-Tupel aus * einer endlichen Menge Q von Zuständen * einem Alphabet T von Eingabesymbolen * einem Startzustand s E Q * einer Menge von Finalzustaenden F < Q * einer Ueberfuehrungsfunktion d:Q x T -> P(Q), die jedem Paar aus Zustand und gelesenem Symbol eine Menge von Folge-Zustaenden zuordnet. // In CL ist s eine Menge von Startzustaenden! // Dieser indeterministische Automat kann sich deterministisch verhalten, // wenn die Produktionen eindeutig sind! Ist d*:Q x T* -> P(Q) die Funktion, die einer Folge von Eingabesymbolen und einem Zustand die Menge aller moeglichen letztendlich resultierenden Zustaende zuordnet, so ist die vom Automat erkannte Sprache L(A) = { w E T* : d*(s,w) /\ F != {} } Sollte _irgendeine_ moegliche Abarbeitungsfolge fuer eine Eingabe in F enden, so "akzeptiert" der Automat die Eingabe. Umwandlung eines indeterministischen endlichen Automaten: Jeder indeterministische Automat kann in einen deterministischen umgewandelt werden, indem man als Zustaende Zustandsmengen all derjenigen Zustaende betrachtet, in denen der Automat sich befinden koennte. Regulaerer Ausdruck: Ein regulaerer Ausdruck ueber einem Alphabet S ist * ein Wort aus dem Symbol a, falls a E S * ein Wort aus dem Symbol 'lambda' * ein Wort '(' r '\/' s ')', falls r und s regulaere Ausdruecke sind * ein Wort '(' r s ')' , falls r und s regulaere Ausdruecke sind * ein Wort r '*', falls r ein regulaerer Ausdruecke ist falls S /\ { 'lambda', '\/', '*', '(', ')' } = {} // Hier ist 'lambda' das leere Zeichen, wohingegen in CL Epsilon benutzt wird. // In CL darf ein regulaerer Ausdruck noch die ueblichen "[...]" und das "+" // enthalten Regulaere Sprache: Eine von einem regulaeren Ausdruck beschriebene Sprache. * L(a) = {a} fuer alle Symbole * L('lambda') = {} * L( '(' r '\/' s ')' ) = L(r) \/ L(s) * L( '(' r s ')' ) = L(r)L(s) * L( r '*' ) = L(r)* // cl.txt haelt eine unabhaengige Definition von regulaeren Sprachen // bereit, die aber aequivalent ist Spontanuebergang: Eine Produktion, die einem Zustand ohne eine Eingabe einen neuen Zustand zuordnet. q -> q' mit q,q' E Q "spontaner Automat": Ein Automat ohne Nichtterminalsymbole, mit Leseproduktionen und Spontanuebergangen (d.h. ein endlichen Automaten mit Spontanuebergaengen). Regularitaet: Folgende Aussagen ueber eine Sprache S ueber einem Alphabet T sind aequivalent 1. L ist regulär. 2. L wird von einem deterministischen endlichen Automaten erkannt. 3. L wird von einem nichtdeterministischen endlichen Automaten erkannt. 4. L wird von einem spontanen Automaten erkannt Beweis durch Implikation 1 => 4 => 3 => 2 => 1, wobei 3 => 2 s.o. Regulaere Sprachen und spontane Automaten: Ist eine Sprache regulaer, so kann sie von einem endlichen Automaten mit Spontanuebergangen erkannt werden, denn zu jeder regulaeren Sprache laesst sich ein solcher Automat angeben, der auch nur diese Sprache erkennt: * Der Automat zur regulaeren Sprache {a} mit a E T ist der Automat mit nur einer einzigen Produktion, die aus Startzustand und a den Endzustand macht * Der Automat zur regulaeren Sprache {} ist ein Automat ohne Produktionen. * Sind L und M regulaere Sprachen, so erhaelt man den Automaten zur Erkennung von L \/ M, indem man beide Automaten vereinigt, einen neuen Zustand q einfuehrt und von q Spontanproduktionen zu den Startzustaenden der Automaten fuer L und M hinzufuegt. * Sind L und M regulaere Sprachen, so erhaelt man den Automaten zur Erkennung von LM, indem man beide Automaten vereinigt und Spontanproduktionen von den Endzustaenden des Automaten fuer L zum Startzustand des Automaten fuer M hinzufuegt. * Ist L eine regulaere Sprache, so erhaelt man den Automaten fuer L*, indem man die Startzustaende des Automaten fuer L in die Menge der Endzustaende aufnimmt und Spontanproduktionen von den Endzustaenden in die Startzustaende hinzufuegt. Spontane Automaten und indeterministische endliche Automaten: Zu jedem spontanen Automaten gibt es einen aequivalenten indeterministischen endlichen Automaten, da sich jede Folge von Spontanproduktionen durch eine Leseproduktion ersetzen laesst -- naemlich durch eine Produktion q a -> q', wobei q der naechstvorherliegende Zustand mit Leseproduktion ist und q' der letztendlich resultierende Zustand. Existiert kein solcher Zustand q, so wird die Produktion gestrichen und der Ausgangszustand der Folge von Spontanzustaenden in die Menge der Endzustaende aufgenommen. Deterministische endliche Automaten und regulaere Sprachen: Erkennt ein deterministischer endlicher Automat eine Sprache, so ist sie regulaer. Zum Beweis werden die n Zustaende des Automaten durchnummeriert. Sei L(a,b,t) die Sprache aus denjenigen Woertern, die der Automat erkennt, wenn er von Zustand Nummer a ueber Zustaende mit den Nummern 1...t in Zustand Nummer b landet. Nun ist zu beweisen, dass alle Sprachen, die der Automat erkennt (also alle L(a,b,t) mit t=0..n), regulaer sind. Ist t=0, so wurde kein anderer Zustand ausser a und b passiert. Es handelt sich also entweder um eine leere Sprache oder um eine Sprache aus dem leeren Wort. Ist aber L(a,b,t) regulaer, so ist es auch L(a,b,t+1), da * entweder beim Erkennen von L(a,b,t+1) der Zustand t gar nicht verwendet wurde, also L(a,b,t+1)=L(a,b,t) oder * beim Erkennen von L(a,b,t+1) der Zustand t+1 passiert wurde. Das geschieht in 3 Phasen, dem Weg von a nach t+1, eventuell einigen Produktionen von t+1 nach t+1 und einem abschliessenden Weg von t+1 zu b. Alle diese Phasen benutzen lediglich die Zustaende 1..t. // Warum (?) Also ist L(a,b,t+1) = L(a,b,t) \/ L(a,t+1,t)L(t+1,t+1,t)*L(t+1,b,t) und damit regulaer, da alle L(x,y,t) ja nach Induktionsvorraussetzung bereits regulaer sind. Damit sind alle L(a,b,t) fuer alle Endzustaend b regulaer. Die Menge aller erkannten Sprachen ist nun die Vereinigung aller dieser L(a,b,t) -- und damit selbst wieder regulaer. Pumping Lemma: In jeder regulaeren Sprache haben alle Woerter uvw ab einer Mindestlaenge n ein Teilwort v, sodass v beliebig vervielfacht werden kann und das Gesamtwort trotzdem noch in der Sprache ist. Begruendung: Sei L=L(A) die regulaere Sprache samt zugehoerigem Automat. Waehle Mindestlaenge n gleich der Anzahl der Zustaende des Automaten. Verarbeitet der Automat ein Wort s aus L mit |s|>n, so werden |s| Zustaende passiert. Da |s|>n, muss mindestens ein Zustand 2-mal passiert werden. Zerlegt man nun s in uvw, sodass der gleiche Zustand einmal beim letzten Zeichen von u auftritt und einmal beim letzten Zeichen von v, so spielt es keine Rolle, wie oft v vorkommt, da der endliche Automat kein Gedaechtnis hat. // Ein formaler Beweis findet sich im Skript Das Pumping Lemma ist nuetzlich, wenn man zeigen will, dass eine Sprache nicht regulaer ist, denn dann gibt es keine solche Mindestlaenge. Aequivalenzrelation: Eine transitive, symmetrische und reflexive 2-stellige Relation. Beispiel: Die Gleichheit "=". Kongruenzrelation: Eine Aequivalenzrelation, bei der gilt // ja was denn (?) Verhaltensgleichheit: Zwei Zustaende q und r eines Automaten heissen verhaltensgleich, wenn fuer alle Woerter w gilt d*(q,w) E F = d*(r,w) E F -- d.h. wenn sie fuer alle Woerter dieselbe Antwort hervorrufen. In Zeichen: q ~A r ~A ist eine Aequivalenzrelation, da "=" eine Aequivalenzrelation ist ~A ist eine Kongruenzrelation, d.h. 1. q ~A r => (q E F = r E F) Dieses gilt, da d*(q,eps) E F = d*(r,eps) E F <=> q E F = r E F 2. q ~A r => d(q,a) ~A d(r,a) fuer alle Zeichen a Dieses gilt, da d*(q,aw) E F = d*(r,aw) E F <=> d*(d(q,a),w) E F = d*(d(r,a),w) E F <=> d(q,a) ~A d(r,a) ~A ist die groebste Kongruenzrelation, da im vorhergehenden Punkt nur Aequivalenzumformungen stattgefunden haben. Jedwede Kongruenzrelation schliesst also ~A ein. // Das ist selbstgestrickt Approximative Verhaltensgleichheit: Zwei Zustaende q und r sind k-approximativ verhaltensgleich, wenn fuer alle Woerter w kuerzer als k d*(q,w) E F = d*(r,w) E F gilt. q ~A,k r <=> d*(q,w) E F = d*(r,w) E F fuer alle w E T* mit |w|= (q E F & r E F ) | (~(q E F) & ~(r E F)) q ~A,k+1 r <=> ( q ~A,k r & d(q,a) ~A,k d(r,a) für alle a E T) Aequivalenzklasse: Die Aequivalenzklasse eines Zustandes bezueglich einer Aequivalenzrelation ist die Menge all derer Zustaende, die zu ihm aequivalent sind -- einschliessslich im selbst. [q] = {p E Q : p ~ q } Quotientenautomat: Der Quotientenautomat eines Automaten bezueglich einer Aequivalenzrelation ist der Automat aus den Aequivalenzklassen. A/~ = ([Q], T, [d], [s], [F]) A/~ Der Quotoientenautomat, gelesen "A modulo ~" [Q] Menge aller Aequivalenzklassen [s] Aequivalenzklasse des Startzustandes [F] Teilmenge von [Q] fuer Finalzustaende [d] Funktion von [Q] x T nach [Q]: [d]([q],a) = [d(q,a)] Es spielt keine Rolle, von welchem q E [q] man d(q,a) berechnet, da fuer alle r E [q] (d.h. r ~ q) gilt, dass d(r,a) ~ d(q,a) (d.h. d(r,a) E [d(q,a)]). A/~ ist aequivalent zu A, da stets gilt [d]*(q,w) = [d*(q,w)] (d.h. A/~ spuckt diejenige Aequivalenzklasse aus, in der auch das Ergebnis von A gelegen haette). Beweis: [d]*([q],eps) = [q] = [d*(q, eps)] [d]*([q],aw) = [d]*([d]([q],a),w) = [d]*([d(q,a)],w) = [d*(d(q,a),w)] = [d*(q,aw)] Reduzierter endlicher Automat: Ein endlicher Automat, bei dem keine Zustaende aequivalent sind. Zusammenhaengender endlicher Automat: Ein endlicher Automat, der keine ueberfluessigen Zustaende hat. Minimaler endlicher Automat: Ein endlichen Automat, zu dem es keinen aequivalenten anderen endlichen Automaten gibt, der weniger Zustaende haette. Ein minimaler Automat ist nichts anderes als ein reduzierter zusammenhaengender Automat: Waere ein minimaler Automat A nicht reduziert, so haette A/~ weniger Zustaende und A waere nicht minimal. Waere A nicht zusammenhaengend, so liessen sich die ueberfluessigen Zustaende entfernen und A waere nicht minimal. Jeder minimale Automat ist also zusammenhaengend und reduziert. Ist ein Automat reduziert und zusammenhaengend, so ist er umgekehrt auch zwangslaeufig minimal, Beweis s. Skript. Der Quotientenautomat A/~A ist minimal. Homomorphismus: Eine strukturerhaltende Abbildung. Ein Homomorphismus auf Sprachen ist eine Abbildung von einer Sprache ueber einem Alphabet T* auf eine Sprache ueber einem Alphabet S*, sodass h(xy) = h(x)h(y). h ist also eindeutig durch h(a) von allen Buchstaben a E T* festgelegt. Menge aller regulaeren Sprachen: Die Menge aller regulaeren Sprachen ueber einem Alphabet T wird mit L3(T) bezeichnet. Regulaere Substitution: Eine Funktion s: L3 -> L, die jedem Zeichen des Alphabetes der Eingabesprache eine ganze regulaere Sprache zuordnet und so aus einem Wort ein neues Wort erzeugt, in dem jedes Zeichen durch eine ganze Sprache ersetzt wurde. Die Menge aller resultierenden Worte ist wiederum eine regulaere Sprache. Abgeschlossenheit von L3: L3 ist abgeschlossen gegenueber * Vereinigung (wg. Definition regulaerer Sprachen) * Verkettung (wg. Definition regulaerer Sprachen) * Iteration (wg. Definition regulaerer Sprachen) * Komplement Bei dem zugrundeliegenden endlichen Automaten kann man F:=Fc setzen und erhaelt einen L3(T)c erkennenden Automaten * Durchschnitt Fuer zwei regulaere Sprachen L und M gilt: L /\ M = (Lc \/ Mc)c Alle Operationen sind wohldefiniert, daher auch das Ergebnis * Sprachspiegelung Der zugehoerige regulaere Ausdruck laesst sich wie folgt spiegeln: ami = a lambdami = lambda (A \/ B)mi = (Ami \/ Bmi) (A B)mi = Bmi Ami A*mi = Ami* Er beschreibt die gespiegelte Sprache, die somit auch regulaer sein muss. * Rechtquotient LM^-1 = { x E T* : es gibt ein y E M mit xy E L } = { x E T* : es gibt ein y E M mit d*(s,xy) E F } fuer Automaten von L = { x E T* : es gibt ein y E M mit d*(d*(s,x),y) E F } = { x E T* : d*(s,x) E { q E Q : es gibt ein y E M mit d*(q,y) E F } } Nimmt man diese q's als Finalmenge eines neuen Automaten, so erkennt dieser genau LM^-1. Damit ist LM^-1 regulaer. * Linksquotient M^-1L = ( Lmi Mmi^-1 )mi * Homomorphismen Die Sprache h(L) wird durch den regulaeren Ausdruck von L definiert, wenn man alle Zeichen a durch ihr Pendant h(a) ersetzt. Damit ist auch h(L) regulaer. * Regulaere Substitutionen Der regulaere Ausdruck zu s(L) entsteht durch Ersetzen aller Zeichen a durch s(a). Produktautomat: Der Produktautomat zweier Automaten arbeitet beide Automaten parallel ab: A=(Q1 x Q2,T,d,(s1,s2),F1 x F2) mit d((q1,q2),a) = (d1(q1,a), d2(q2,a)). Er verwaltet also 2-Tupel von je einem Zustand des einen und einem Zustand des anderen Automaten. Der Produkt-Automat erkennt den Durchschnitt der Ausgangs-Sprachen. "Komplementaerautomat": Der Komplementaerautomat eines Automaten hat als Finalmenge genau diejenigen Zustaende, die nicht in der Finalmenge des Ausgangsautomaten liegen.Er erkennt genau das Komplement der Ausgangssprache. Algorithmisch ueberpruefbare Eigenschaften regulaerer Sprachen: * w E L Dieses ist mithilfe des endlichen Automaten von L bestimmbar. * L = {} Die Sprache ist leer, falls es im Automaten keinen Weg vom Startzustand zu einem Finalzustand gibt.Sie ist ebenso leer, wenn der zugehoerige regulaere Ausdruck nur aus lambdas besteht. * L unendlich L ist unendlich, wenn der regulaere Ausdruck einen Stern enthaelt, der auf einen nicht die leere Sprache produzierenden regulaeren Ausdruck angewandt wird. * L = T* (L umfasst alle Woerter ueber T) Hierzu nimmt man den Komplementaerautomaten des Automaten von L (mit F'=Fc) und zeigt, dass seine Sprache leer ist. * L1 /\ L2 = {} Dieses gilt genau dann, wenn die Sprache des Produktautomaten leer ist * L1 =< L2 Dieses gilt, wenn L1 /\ L2c leer ist. * L1 = L2 Genau dann, wenn L1 =< L2 und L2 =< L1. * L1 \/ L2 = T* Genau dann, wenn L1c /\ L2c leer ist. Linkslineare Grammatik: Eine Grammatik, die lediglich Produktionen der Form A -> By oder A -> y hat. Eine solche Grammatik baut also immer das linkeststehende Nichtterminalsymbol aus. Rechtslineare Grammatik: Eine Grammatik, die lediglich Produktionen der Form A -> yB oder A -> y hat. Eine solche Grammatik baut also immer das rechteststehende Nichtterminalsymbol aus. Zu jeder rechtslinearen Grammatik kann man eine linkslineare angeben und umgekehrt. Dieses geschieht durch Umdrehen der Produktionsregeln: Rechtslinear Linkslinear A -> y, mit A != S S -> Ay A -> yB, mit A != S B -> Ay S -> y S -> y Es kann oBdA angenommen werden, dass S in keiner rechten Seite einer Produktion vorkommt (sonst fuehrt man ein neues Nichtterminalsymbol S' ein). Die aequivalente linkslineare Grammatik erzeugt also zuerst das letzte Zeichen des herzuleitenden Wortes, gefuehrt von dem ersten Nichtterminalsymbol. Das erste Nichtterminalsymbol aber wurde umdefiniert und erzeugt das vorletzte Zeichen und das zweite Nichtterminalsymbol. So geht das weiter bis zum Startsymbol. Regulaere Grammatik: Eine Grammatik, die entweder linkslinear oder rechtslinear ist. Zu jeder regulaeren Grammatik laesst sich ein entsprechender endlicher Automat finden und umgekehrt. Das geht, indem man die Zustaende des Automaten mit den Nichtterminalsymbolen der Grammatik identifiziert. Ein Herleitungsschritt des Automaten "qa -> d(q,a)" wird in der rechtslinearen Grammatik zu "q -> a d(q,a)". Sollte d(q,a) ein Finalzustand sein, so enthaelt die Grammatik stattdessen "q -> a". ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Kellerautomaten ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Kontextfreie Grammatik: Eine Grammatik, die nur Produktionen der Form A -> X enthaelt, wobei A ein Nichtterminalsymbol ist und X eine Satzform. Syntaxbaum,Strukturbaum,Ableitungsbaum: Graphische Darstellung von Produktionen einer kontextfreien Grammatik. Seine Knoten sind Terminalzeichen, Nichtterminalzeichen oder epsilon. Die Wurzel ist das Startsymbol. Die Kinder eines Knotens werden durch eine auf das Knotensymbol anwendbare Produktion definiert. Eindeutige Grammatik: Eine Grammatik G, die zu jedem Wort nur einen einzigen Syntaxbaum hat. Eindeutige Sprache: Eine Sprache, zu der es eine eindeutige Grammatik gibt. Menge aller kontextfreien Sprachen: Die Menge aller kontextfreien Sprachen ueber einem Alphabet T wird mit L2(T) bezeichnet. Sie schliesst die Menge aller regulaeren Sprachen ein. Kellerautomat: Ein Automat, der im Eingabebereich nur sequentiell lesen kann, allerdings links vom Eingabewort auf dem Band eine Art Keller verwaltet. Er besitzt nur Produktionen der Form * uqa -> vr "Eingabe-Keller-Produktion" * uq -> vr "Kellerproduktion" Sein Startkontext ist entweder der Startzustand oder aber das Wort aus einem speziellen "Kellerbodensymbol" und dem Startzustand. In den Produktionen steht der linke Teil des Inputs fuer den Stack, der mittlere Teil fuer den aktuellen Zustand und der rechte Teil fuer die Eingabe des Automaten. Deterministischer Kellerautomat: Ein Kellerautomat, der fuer eine bestimmte Konfiguration nur eine einzige Produktion hat. Deterministische Kellerautomaten sind weniger leistungsfaehig als indeterministische. Beispiel: L={a^nb^n} wird von einem indeterministischen Kellerautomaten erkannt, nicht jedoch von einem deterministischen. Normalform eines Kellerautomaten: Derjenige aequivalente Kellerautomat, der nur Produktionen mit Input "Zeichen Zustand Zeichen" hat und zudem am Ende des Kellers ein "Kellerbodensymbol" verwaltet, das niemals geloescht und niemals neu erzeugt wird. Ausserdem verfuegt er ueber eine besondere Endproduktion, die die Konfiguration "Kellerbodensymbol Endzustand" ueberfuehrt in den "Endzustand". Dieser Endzustand ist das einzige Element der Finalmenge. Zu jedem Kellerautomaten gibt es eine Normalform. Das Lesen und Schreiben mehrerer Zeichen muss dabei durch sequentielles Lesen/Schreiben einzelner Zeichen simuliert werden. Die Menge der Finalzustaende kann durch die Menge aus dem einzelnen Endzustand ersetzt werden, wenn man von jedem vorherigen Finalzustand eine Spontanproduktion zum neuen Endzustand einfuehrt. Alle Spontanproduktionen lassen sich sodann in die Leseproduktionen integrieren. // Eigentlich sollen noch die Produktionen der Form qa -> q'a' // eliminiert werden, doch die hat der Kellerautomat doch gar nicht (?) Linksableitung: Eine Ableitung, bei der jede Produktion immer das linkeststehende Nichtterminalsymbol ersetzt. Zu jedem Wort w E L gibt es eine Linksableitung. Jeder Linksableitung entspricht genau ein Syntaxbaum. Rechtsableitung: Eine Ableitung, bei der jede Produktion immer das rechteststehende Nichtterminalsymbol ersetzt. Zu jedem Wort w E L gibt es eine Rechtsableitung. Jeder Rechtsableitung entspricht genau ein Syntaxbaum. LL-Automat: Der LL-Automat zu einer Grammatik ist ein Automat mit nur einem Zustand, dem Startkontext Sq und nur Produktionen der Form A q -> umi q fuer alle A -> u der Grammatik (Produzieren eines umgedrehten Wortes r aus einem Nichtterminalsymbol, "produce") t q t -> q fuer jedes Terminalsymbol t (vergleichendes Auffressen in Keller und Eingabe, "compare") Dieser Automat baut also im Keller linksableitend Satzformen (z.B. S -> AB -> CDB, jeweils gespiegelt). Sobald der Anfang des Eingabewortes dem linken Teil (da gespiegelt: dem rechten Teil) der produzierten Satzform gleicht, wird dieser Teil als erfolgreich gematcht entfernt. Der LL-Automat probiert indeterministisch herum, bis er eine Satzform gefunden hat, die zu einer Compare-Produktion fuehrt. Dabei beginnt er "von oben", naemlich bei S. Dieses nennt man Top-Down-Erkennung. Jeder Linksableitung eines Wortes entspricht genau ein Erkennungsvorgang des LL-Automaten. LR-Automat: Der LR-Automat zu einer Grammatik ist ein Automat mit nur einem Startzustand und einem Finalzustand und nur Produktionen der Form u q -> A q fuer alle A -> u der Grammatik (Erraten der Herkunft eines Nichtterminalsymbols, "reduce") q t -> t q fuer alle Terminalsymbole t ("shiften" in den Keller) S q -> f wurde das Wort auf S reduziert, folgt der Finalzustand Der LR-Automat schiebt also zunaechst indeterministisch eine Zahl von Terminalsymbolen aus der Eingabe in den Keller. Dann versucht er, einen Teil des gelesenen auf ein Nichtterminalsymbol zu reduzieren. Eventuell reduziert er dann die Folge von Nichtterminalsymbolen wiederum zu einem Nichtterminalsymbol oder aber er liest erst weiter ein. Der LR-Automat versucht also, zu einem Praefix des Eingabewortes passende Nichtterminalsymbole zu finden, er geht den Syntaxbaum von unten hoch ("Bottom-Up-Erkennung"). Jeder Rechtsableitung eines Wortes entspricht genau ein Erkennungsvorgang des LR-Automaten. epsilon-freie kontextfreie Grammatik: Eine kontextfreie Grammatik, die keine Produktion mit epsilon hat oder lediglich "S -> epsilon" hat. Jede kontextfreie Grammatik laesst sich epsilon-frei machen. Dazu streicht man alle Produktionen A, die nur epsilon produzieren. Dann baut zu allen Produktionen, die A im Output haben eine Produktion, die A nicht im Output haben -- und simuliert dadurch die Moeglichkeit, dass A epsilon produziert. separierte kontextfreie Grammatik: Eine kontextfreie Grammatik, in der es nur Produktionen gibt, die nur Nichtterminalsymbole oder nur Terminalsymbole produzieren. Jede kontextfreie Grammatik laesst sich separieren, indem man fuer jedes Terminalsymbol a ein Nichtterminalsymbol A einfuehrt. Dann ersetzt man alle rechts in den Produktionen stehenden Terminalsymbole a durch ihr Nichtterminalsymbol A und fuegt Produktionen der Form A -> a hinzu. Kettenproduktion: Eine Produktion der Form A -> B, wobei A und B beides Nichtterminalsymbole sind. "kettenlose" kontextfreie Grammatik, kontextfreie Grammatik die frei von Kettenproduktionen ist: Eine kontextfreie Grammatik, die keine Kettenproduktionen enthaelt. Jede epsilonfreie separierte kontextfreie Grammatik laesst sich kettenlos machen. Dazu sammelt man alle Folgen von Kettenproduktionen A -> B -> C ... und merkt sich, auf was sie fuehren (z.B. auf x). Dann streicht man die Kettenproduktionen und fuegt ueberall dort, wo A im Output einer Produktion steht, eine neue Produktion hinzu, die statt A x im Output stehen hat. "Chomsky-normalisierte" kontextfreie Grammatik: Eine kontextfreie Grammatik, die nur Produktionen der Form A -> BC A -> a und evtl. S -> epsilon enthaelt. Jede kontextfreie Grammatik laesst sich Chomsky-normalisieren. Dazu macht man sie zunaechst separiert, dann epsilonfrei und kettenlos und ersetzt dann alle Produktionen der Form A -> BCDE... durch Produktionen der Form A -> BZ1 Z1 -> CZ2 Z2 -> DZ3 ... . uvwxy-Theorem: Zu jedem Wort z einer kontextfreien Sprache, das laenger als eine sprachabhaengige Konstante nL ist, gibt es eine Zerlegung in 5 Teilwoerter z=uvwxy, sodass uv^kwx^ky fuer alle k auch wieder ein Wort der Sprache ist. Dabei ist |vwx|=0, d.h. der auf- und abpumpbare Teil hat eine eingeschraenkte Laenge und es wird mindestens ein Buchstabe gepumpt. Dieses Theorem kann unter Zuhilfenahme des Syntaxbaumes von z gezeigt werden. nL kann aus der Chomsky-normalisierten Grammatik abgelesen werden // und wie (?) kontextfreie Substitution: Eine Abbildung, die jedem Terminalsymbol eine kontextfreie Sprache zuordnet. Abgeschlossenheit von L2: L2(T) ist abgeschlossen gegenueber * Vereinigung Die Grammatik zu zwei kontextfreien Grammatiken kann konstruiert werden mit der Vereinigung der beiden Wortersetzungssysteme und den Produktionen S -> S1 und S -> S2. * Verkettung Die Grammatik zu zwei kontextfreien Grammatiken kann konstruiert werden mit der Vereinigung der beiden Wortersetzungssysteme und der Produktion S -> S1 S2. * Iteration Die Grammatik zu einer Iteration einer kontextfreien Sprache kann konstruiert werden durch Hinzufuegen der Produktionen S -> S S und S -> epsilon. * kontextfreie Substitution Dazu ersetzt man in der Chomsky-normierten Grammatik alle Produktionen A -> a durch A -> S(a), wobei S(a) das Resultat der kontextfreien Substitution auf a ist. * Homomorphe Bilder Ein Homomorphismus ist eine spezielle kontextfreie Substitution. * Spiegelung Die Grammatik der gespiegelten Sprache erhaelt man, indem man in der Chomsky-normierten Grammatik alle Produktionen A -> BC umdreht zu A -> CB. * Rechtsquotientenbildung mit regulaerer Sprache LM^-1 mit kontextfreiem L und regulaerem M ist kontextfrei. Dieses laesst sich mit einer Hilfssprache beweisen. L2(T) ist ab 2 Terminalzeichen nicht abgeschlossen gegenueber: * Durchschnitt Gegenbeispiel sind die kontextfreien Sprachen L={a^nb^nc^m : n,m>0} und M={a^nb^mc^m : n,m>0}. L/\M = {a^nb^nc^n : n>0} ist nicht kontextfrei, da sie dem uvwxy-Theorem nicht unterliegt. * Komplement L /\ M = (Lc \/ Mc)c . Waere das Komplement abgeschlossen, so waere auch der Durchschnitt abgeschlossen. Algorithmisch ueberpruefbare Eigenschaften kontextfreier Sprachen: Zunaechst Chomsky-normiert man die Grammatik der Sprache. * w E L Ist |w|=n, so koennen hoechstens n Produktionen der Form A -> BC verwandt worden sein, die man durchprobieren kann. * L = {} L ist genau dann leer, wenn es kein Wort mit einer Laenge kleiner nL gibt. Denn gaebe es ein Wort > nL, so koennte man dieses sukzessive auf < nL abpumpen. * L unendlich L ist unendlich, falls es ein Wort w mit nL=<|w|<2*nL gibt, denn dieses kann man zu unendlich vielen Woertern aufpumpen. Cocke-Kasami-Younger-Algorithmus: Vorgehen zum Festellen der Zugehoerigkeit eines Wortes w zu einer kontextfreien Sprache. Dazu muss die Grammatik Chomsky-normalisiert sein. Dann erstellt man eine Tabelle mit |w| Spalten und |w| Zeilen. In die Diagonale traegt man an Position i,i all diejenigen Nichtterminale ein, die das i-te Zeichen von w direkt produzieren. Nun fuellt man Diagonale fuer Diagonale nach rechts oben hin. Dazu schreibt man in jede Zelle all diejenigen Nichtterminale, die zwei Nichtterminale BC erzeugen, welche sich in der Tabelle wie folgt gegenueber liegen: B steht in der Zeile der zu fuellenden Zelle und C in der Spalte. Der Abstand von B zu der zu fuellenden Zelle muss dabei gleich dem Abstand von C zur Hauptdiagonale sein. Steht zuletzt S in der rechten oberen Ecke, hat man einen Weg gefunden, das Wort auf S zurueckzufuehren, das Wort ist in der Sprache. Kellerautomat in Normalform (D): Ein Kellerautomat, der * ein Kellerbodensymbol hat, das erst am Ende geloescht wird und nie geschrieben wird * Kellerproduktionen nur in der Form aq -> xq' hat, wobei a ein Symbol ist und x ein Wort sein darf. * Keller-Eingabe-Produktionen nur in der Form aqb -> xq', wobei a und b Symbole sind und x ein Wort sein darf. // Anscheinend gehoert das "(D)" mit zum Bezeichner Deterministischer Kellerautomat in Normalform (D): Ein Kellerautomat in Normalform (D), der fuer jede Konfiguration cqx nur eine anwendbare Produktion hat. Dies ist entweder eine einzig moegliche Kellerproduktion oder eine einzig moegliche Keller-Eingabe-Produktion. Menge aller deterministischen kontextfreien Sprachen: Menge all derer Sprachen L, zu denen es einen deterministischen Kellerautomaten in Normalform (D) gibt, der die Sprache L{#} erkennt. Man haengt den Woertern der Sprache also ein Metasymbol an, um dem Automaten das Erkennen zu ermoeglichen. Die Menge aller deterministischen kontextfreien Sprachen ueber einem Alphabet T wird mit L2det(T) bezeichnet. L2det(T) ist eine echte Teilmenge von L2(T), denn fuer jedes L E L2det(T) gilt: L{#} wird von einem Kellerautomaten erkannt, ist also kontextfrei. {#} ist regulaer, damit ist auch der Rechtsquotient (L{#}){#}^-1 kontextfrei. Nun ist aber (L{#}){#}^-1=L. Ausserdem kann nicht L2(T)=L2det(T) sein, da L2det(T) gegen Komplementbildung abgeschlossen ist, L2(T) hingegen nicht. Abgeschlossenheit von L2det: L2det(T) ist abgeschlossen gegen Komplementbildung, wie man mithilfe eines kompliziert konstruierten Kellerautomaten beweisen kann. L2det(T) ist nicht abgeschlossen gegen Vereinigung. Damit ist L2det auch nicht gegen Durchschnitt abgeschlossen. Vollstaendiger deterministischer Kellerautomat in Normalform (D): Ein deterministischer Kellerautomat in Normalform (D), der fuer jede Konfiguration genau eine anwendbare Produktion hat. Jeder deterministischer Kellerautomat in Normalform (D) laesst sich vervollstaendigen. Dazu fuehrt man einen neuen Zustand q* ein, der fuer "Anhalten wegen fehlender Produktion" steht. Sodann fuegt man fuer all die Konfigurationen, fuer die es keine Produktion gab, eine hinzu, die nach q* fuehrt. Auch fuegt man fuer alle Zeichen a des Eingabealphabets Produktionen aq* -> q* hinzu, sodass der Keller leergemacht wird. Falls der alte Automat wegen fehlender Produktionen anhielt, wird der neue Automat in q* mit leerem Keller enden. q* ist dabei kein Finalzustand. Unsterbliches Wort: Ein Zeichen-Zustands-Tupel, fuer das ein vollstaendiger deterministischer Kellerautomat in Normalform (D) eine unendlich lange Folge von xq's produziert, wobei die x nicht-leere Woerter sind. Die Unsterblichkeit eines Wortes aq ist algorithmisch ueberpruefbar. Terminierender vollstaendiger deterministischer Kellerautomat in Normalform (D): Ein vollstaendiger deterministischer Kellerautomat in Normalform (D), der keine unsterblichen Woerter hat. Jeder solche Automat laesst sich terminierend machen, indem man einen neuen Zustand f* einfuehrt, der nicht in der Finalmenge ist. Nun uebernimmt man alle Produktionen des alten Automaten bis auf die, deren Input ein unsterbliches Wort aq ist. Diese ersetzt man durch aq -> f*. Sodann fuegt man fuer alle Zeichen a Produktionen af* -> f* hinzu, sodass der entstehende Automat vollstaendig ist. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Linear beschraenkte Automaten ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ kontextsensitive Grammatik: Eine Grammatik, die nur Produktionen der Form uAv -> uxv hat, wobei u,v,x Satzformen sind, x nicht leer ist und A ein Nichtterminalsymbol ist. Ausserdem muss die Grammatik epsilon-frei sein und das Startsymbol S darf in keiner rechten Seite einer Produktion vorkommen. erweiternde Grammatik: Eine Grammatik, deren Produktionen aus einer beliebigen Satzform eine laengere oder gleichlange Satzform machen. Ausserdem muss sie epsilon-frei sein und das Startsymbol S darf in keiner rechten Seite einer Produktion vorkommen. Jede kontextsensitive Grammatik ist erweiternd und zu jeder erweiternden Grammatik laesst sich eine aequivalente kontextsensitive Grammatik angeben. Diese Grammatik simuliert mit Hilfs-Nichtterminalsymbolen die erweiternden Produktionen durch kontextsensitive Produktionen. Vektorzeichen: Ein Hilfszeichen, welches die Information mehrerer aufeinander folgender Eingabezeichen, des Zustandes und der Position des Schreiblesekopfes innerhalb der Eingabezeichenkette enthaelt. Definiert man fuer alle moeglichen k-stelligen Eingabezeichenketten ein neues Vektorzeichen (was moeglich ist, da das Eingabealphabet endlich ist), so kann das Wort w auf auf |w|/k Speicherzellen komprimiert werden. Die Produktionen muessen noch entsprechend angeglichen werden, um die Bewegung des Schreib/Lese-Kopfes in einem Vektorzeichen und ueber ein Vektorzeichen hinaus in das naechste korrekt abzubilden. Linear beschraenkter Automat, linear bounded automaton, LBA: Ein Automat mit nur Produktionen der Form: * qa -> q'a' (Lesen und Drucken) * qa -> a'q' (Lesen und nach rechts gehen und Drucken (?)) * bqa -> q'ba' (Lesen, nach links gehen und Drucken (?)) Produktionen duerfen nur von dem rechtsstehenden Zeichen abhaengen, d.h. der Automat muss bei Produktionen bqa->q'ba' fuer alle Zeichen b dieselbe Produktion haben. Der LBA besitzt also einen festen Speicherbereich, in dem er die vorgegebenen Zeichen umwandeln kann. Er kann nicht nach rechts oder links aus dem Speicher heraus. Um ein Wort zu erkennen, muss er den rechten Rand ueberschreiten um so einen Finalzustand zu erreichen. Ein LBA erkennt genau die kontextsensitiven Sprachen. Dazu reduziert er Folgen von Terminalsymbolen indeterministisch zu Nichtterminalsymbolen und fuellt den Platz mit Blanks auf. Bleibt am Ende das Startsymbol stehen, wird das Wort erkannt. Umgekehrt laesst sich zu jedem LBA eine Grammatik angeben. Diese erzeugt zunaechst eine willkuerliche Zeichenfolge und fuehrt darauf dann die Produktionen des Automaten rueckwaerts aus. Nur wenn der Automat das Wort erkannt haette, loescht die Grammatik das letzte Nichtterminal aus der Zeichenfolge und erzeugt somit ein gueltiges Wort. Um die Grammatik erweiternd zu machen, benutzt man 2-stellige Vektorzeichen, sodass auch die letzte Produktion, die das letzte Nichtterminalsymbol loescht, eine "erweiternde" Produktion wird. Deterministischer linear beschraenkter Automat, DLBA: Ein LBA, der zu jeder Konfiguration nur eine anwendbare Produktion hat. Der DLBA erkennt eine Sprache L, wenn er Woerter der Sprache L{#} akzeptiert. Ein DLBA braucht also einen rechten Randbegrenzer. Ein linker Randbegrenzer ist unnoetig, da der Automat ganz zu Anfang links steht und so das linkeste Zeichen selbst durch ein speziell markiertes Zeichen ersetzen kann. Menge aller kontextsensitiven Sprachen: Die Menge aller kontextsensitiven Sprachen ueber einem Alphabet T wird mit L1(T) bezeichnet. Sie schliesst die Menge aller kontextfreien Sprachen ein. L1 ist gegen Vereinigung und Durchschnittsbildung abgeschlossen und damit auch gegen Komplementbildung. Menge aller deterministischen kontextsensitiven Sprachen: Die Menge aller von einem DLBA erkannten Sprachen ueber einem Alphabet T wird mit L1det(T) bezeichnet. Es ist bis heute ungeloest, ob L1det=L1 gilt. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Turingautomaten ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Erkennbare Sprache, Rekursive aufzaehlbare Sprache: Eine Sprache, zu der es eine Grammatik gibt. Menge aller rekursiv aufzaehlbaren Sprachen: Die Menge aller rekursiv aufzaehlbaren Sprachen ueber einem Alphabet T wird mit L0(T) bezeichnet. Sie schliesst die Menge aller kontextsensitiven Sprachen ein. Turingmaschine: Ein Formalismus bestehend aus * einer endlichen Menge von Zustaenden Q * einem Alphabet von Hilfszeichen N * einem Alphabet von Eingabezeichen T * einem Startzustand s E Q * einem akzeptierenden Zustand q+ nicht aus Q * einem verwerfenden Zustand q- nicht aus Q * einer Ueberfuehrungsfunktion delta, die jedem Zustands-Zeichen- Tupel einen neuen Zustand (eventuell auch q+ oder q-), ein neues Zeichen und einen Operationsmodus L,R,S (links, rechts, stehen) zuordnet Die Turingmaschine arbeitet auf einem endlosen Speicherband und wandelt den anfaenglichen Speicherinhalt in einem neuen um, bis q+ oder q- erreicht werden. Dabei kann der Schreib/Lese-Kopf entsprechend des Operationsmodus verschoben werden. Unbeschriebene Speicherzellen werden mit einem Blank gekennzeichnet. Ausserdem benutzt die Turingmaschine einen rechten und linken Randbegrenzer '#'. indeterministische Turingmaschine: Eine Turingmaschine, deren Ueberfuehrungsfunktion in eine Menge von Zeichen-Zustand-Modus-Tupel abbildet. Turingautomat: Ein Automat zu einer Turingmaschine, bestehend aus * ihrer Zustandmenge, inklusive des erkennenden Zustandes q+ und des verwerfenden Zustandes q- * ihrem Hilfszeichenalphabet, inklusive der Sonderzeichen Blank und '#'. * ihrem Startzustand * ihrem Eingabezeichenalphabet * einer Finalmenge bestehend aus dem Zustand q+ * einer Produktionenmenge mit qa -> q'a' fuer alle delta(q,a)=(q',a',stehen) qab -> a'q'b fuer alle delta(q,a)=(q',a',rechts) mit allen b E N\/T qa# -> a'q'_# fuer alle delta(q,a)=(q',a',rechts) Dadurch wird der Randbegrenzer verschoben und ein Blank eingefuegt bqa -> q'ba' fuer alle delta(q,a)=(q',a',links) mit allen b E N\/T #qa -> #q'_a' fuer alle delta(q,a)=(q',a',links) Hier wird die linke Randbegrenzung erweitert Die erkannte Sprache ist die Menge aller Woerter w, bei denen der Automat fuer #s_w# in q+ landet. Turingautomaten und rekursiv aufzaehlbare Sprachen: Fuer eine rekursiv aufzaehlbare Sprache L sind aequivalent: * L wird von einer Grammatik erzeugt * L wird von einer indeterministischen Turingmaschine erkannt Diese reduziert das Wort wie ein LBA zum Startsymbol, hat dafuer aber unendlich viel Speicher zur Verfuegung, sodass auch nicht- erweiternde Produktionen simuliert werden koennen. Umgekehrt laesst sich zu einer Turingmaschine eine Grammatik angeben, die zunaechst willkuerlich ein Wort erzeugt und sodann die Schritte des Automaten rueckwaerts ausfuehrt. Nur im Falle des Erreichens der Startkonfiguration werden dann Startsymbol und Randbegrenzer aus der Satzform geloescht. * L wird von einer Turingmaschine erkannt Zu jeder indeterministischen Turingmaschine laesst sich eine deterministische angeben. Diese fuehrt eine Breitensuche ueber alle moeglichen Produktionsfolgen der indeterministischen Turingmaschine durch. Entscheidbare Sprache: Eine Sprache L, zu der es eine Turingmaschine gibt, die fuer alle w E L in q+ landet und fuer alle w E Lc in q-. Berechenbare Funktion: Eine (eventuell partielle) Funktion f:T* -> T*, zu der es eine Turingmaschine gibt, die fuer alle z E T*, auf denen f definiert ist, aus #s_z# in q+ landet, wobei f(z) dann rechts vom Schreib/Lese-Kopf auf dem Band steht. Ist M die Turing-Maschine, so schreibt man auch M(z) fuer f(z). Zeitkomplexitaetsfunktion: Eine Funktion time, die einem Wort z die Anzahl von Schritten zuordnet, die eine Turingmaschine braucht, um dafuer in q+ oder q- zu landen. Wird niemals ein solcher Zustand erreicht, so ist time(z) undefiniert. Speicherplatzkomplexitaetsfunktion: Eine Funktion space, die jedem Wort z den Abstand der beiden Randbegrenzer zuordnet, nachdem eine Turingmaschine darueber in q+ oder q- gelandet ist. Wird niemals ein solcher Zustand erreicht, so ist space(z) undefiniert. O(t)-zeitbeschraenkte Turingmaschine: Eine Turingmaschine, bei der fuer alle erkannten Woerter z time(z) (N \/ T)^(k-1) x (Q \/ {q+,q-}) x {L,R,S}^k Es handelt sich also um eine Turingmaschine mit k Speicherzellen-Baendern. Auf dem ersten Band wird nicht geschrieben, sondern nur die Eingabe gelesen. Auf dem letzten Band steht dann die Ausgabe der Turing-Maschine. Da die Speicherplatzkomplexitaet ohne das Eingabeband definiert wird, sind auch Komplexitaetsklassen unter O(n) ("sublineare Komplexitaetsklassen") moeglich. Zu jeder k-Band-Maschine kann man eine normale aequivalente Turingmaschine angeben. Diese verwaltet die k Baender samt der k Schreib/Lese-Kopfpositionen auf ihrem einzigen Band. Braucht ein Band mehr Platz, so werden die anderen Baender aufgeschoben. War die k-Band-Maschine in TIME(t), so gehoert die neue Turingmaschine TIME(t^2) an. // Steht nicht im Skript, sondern nur in den Folien (?) Sprache der Palindrome: Die Sprache der Palindrome gehoert ist in TIME(n^2). Codierung: Eine Funktion code:delta -> {0,1}*, die eine Ueberfuehrungsfunktion einer Turing-Maschine binaer codiert und als Wort zurueck gibt. Die Codierung kann beispielsweise wie folgt vor sich gehen: * Die Eingabezeichen werden durchnummeriert. * Die Zustaende werden durchnummeriert, wobei q+ die Nummer 1 erhaelt, q- die Nummer 2 und der Startzustand s die Nummer 3. * Die Kopfbewegungen werden durchnummeriert: links=1, rechts=2, stehen=3. * Der Befehl delta(q[i],a[j])=(q[k],a[l],s[m]) wird zu 0 0 1^i 0 1^j 0 1^k 0 1^l 0 1^m, wobei hier die Zeichen '1' und '0' gemeint sind. Das Ergebnis ist die Verkettung aller deltas. Universelle Turing-Maschine: Eine Turing-Maschine, die als Eingabe die binaer codierte Ueberfuehrungsfunktion einer anderen Turingmaschine M und ein Eingabewort x bekommt, woraufhin sie simuliert, was M auf x machen wuerde. Die Codierung von M und das Eingabewort x sind auf dem Band durch ein Ampersand '&' getrennt. Die Universelle Turingmaschine berechnet also folgende Funktion: U( code(M) '&' x ) = M(x). Entscheidungsproblem (informelle Definition): Eine Fragestellung nach einer Klassifizierung zu "positiv" oder "negativ". Eine solche Frage laesst sich als Frage nach der Zugehoerigkeit zu einer Menge auffassen. Da sich die Elemente jeder Menge als Zeichenfolgen codieren lassen, handelt es sich also eigentlich um eine Frage nach der Sprachzugehoerigkeit. Also ist ein Problem eine Sprache. // Manchmal ist auch eine Sprache ein Problem -- z.B. im Ausland Spezielles Halteproblem: Die Sprache K aller Codierungen (d.h. aller zum Wort gemachten Turingmaschinen M), die ihren eigenen Code erkennen. Die Fragestellung ist also: Terminiert eine bestimmte Turingmaschine, wenn man ihr ihren eigenen Code als Eingabe gibt? Die Menge all dieser Turingmaschinen ist die Sprache K. K ist nicht entscheidbar. Beweis: Wenn K entscheidbar waere, dann gaebe es eine Turing-Maschine M, die auf allen sich selbst erkennenden Turingmaschinen in q+ anhaelt und auf allen anderen in q-. M wird nun so abgewandelt, dass jeder Ueberfuehrungsfunktionseintrag, der in q+ muendet, ersetzt wird durch einen Eintrag, der zu einer Endlosschleife fuehrt: d(q,a)=(q+,a',m') ~~~> d(q,a)=(q,a,stehen) Fuer alle sich selbst erkennenden Turingmaschinen versinkt M also in einer Endlosschleife, fuer alle anderen Turingmaschinen stoppt M in q-. Wirft man M nun ihren eigenen Code vor, so geschieht folgendes: Fall 1: M ist selbsterkennend. Dann versinkt M in einer Endlosschleife und erkennt sich nicht. Fall 2: M ist nicht selbsterkennend. Dann landet M in q-. Das bedeutet aber, dass M sich selbst erkannt hat. K ist aber rekursiv aufzaehlbar: Dazu baut man eine Turingmaschine MK, die zunaechst prueft, ob das Eingabewort die Form einer Codierung hat. Sodann produziert sie das Wort code(M)&code(M) und simuliert darauf die universelle Turingmaschine. Diese haelt genau dann an, wenn M sich selbst erkennt. Dann terminiert auch MK und hat M erkannt. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RAMs ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ RAM: Random Access Memory. Hier: Random Access Machine. Ein Formalismus, der einen Computer nachstellt und besteht aus: * Unendlich vielen "Eingaberegistern" i[0], i[1], ... mit ihren Inhalten x[0], x[1], ... // Entspricht dem Data Segment * Unendlich vielen "Registern" r[0], r[1], ... mit ihren Inhalten y[0], y[1], ... // Entspricht dem Extended Segment Dabei heisst das 0-te Register "Akkumulator" // Entspricht ax Sein Inhalt wird oft auch als "Akkumulator" bezeichnet * Einem Programmzaehler k mit seinem Inhalt c // Entspricht ip * Einem Programmspeicher mit seinen Befehlen b[1], b[2], ... // Entspricht dem Code Segment Dabei sind die Inhalte von Registern ganze Zahlen. Eine RAM beginnt in der Startkonfiguration, arbeitet RAM-Befehle ab und liefert die Ausgabe beginnend bei r[1] in den Registern, wobei der Akkumulator die Laenge der Ergebnisliste enthaelt. Es wird also eine Funktion f:Z* -> Z* berechnet, die zu einer Liste ganzer Zahlen eine Liste ganzer Zahlen liefert. RAM-Befehl: Eine Kombination aus einer Anweisung und einem Operanden. Folgende Befehle sind definiert (jew. mit Assembler-Aequivalent): Von der Eingabe lesen: READ j MOV ax, ds:[j] READ ^j MOV bx, ds:[j]; MOV ax, ds:[bx] //Indirekte Adressierung! Aus den Registern lesen: LOAD =j MOV ax,j //Konstante laden LOAD j MOV ax, es:[j] LOAD ^j MOV bx, es:[j]; MOV ax, es:[bx] In die Register schreiben: STORE j MOV es:[j], ax STORE ^j MOV bx, es:[j]; MOV es:[bx], ax Auf den Akkumulator addieren: ADD =j ADD ax,j ADD j ADD ax, es:[j] ADD ^j MOV bx, es:[j]; ADD ax, es:[bx] Vom Akkumulator subtrahieren: SUB =j SUB ax,j SUB j SUB ax, es:[j] SUB ^j MOV bx, es:[j]; SUB ax, es:[bx] Akkumulator durch 2 dividieren ("shiften"): HALF SAR ax,1 Spruenge: JUMP c JMP c JPOS c JG c JNEG c JL c JZERO c JZ z // Fuer Java-Programmierer: Die Anweisung "JUMP" entspricht dem legendaeren, // verruchten und doch als Schluesselwort reservierten "goto", welches eine // Fortsetzung der Code-Interpretation an jeder beliebigen Stelle erlaubt. Anhalten: HALT MOV ah,4Ch; INT 21h Der Programmzaehler wird dazu auf 0 gesetzt. Startkonfiguration einer RAM: Ein Zustand, in dem im 0-ten Eingaberegister die Laenge der Eingabe steht und in den darauffolgenden Eingaberegistern die tatsaechliche Eingabe. Der Programmzaehler ist 1, im Programmspeicher steht eine Folge von RAM-Befehlen. Der Rest des Programmspeichers ist mit "HALT"-Befehlen gefuellt. In den Registern stehen Anfangsinhalte, der Rest ist mit Nullen gefuellt. Rechenzeit: Eine Funktion time:Z* -> N, die zu einer RAM-Eingabe die Anzahl der Schritte liefert, bis die RAM terminiert hat. Platzverbrauch: Eine Funktion space:Z* -> N, die zu einer RAM-Eingabe die maximale Summe der Binaerziffern aller Register in der Laufzeit der RAM liefert. Uniformes Komplexitaetsmass: Eine Komplexitaetsangabe unter der Annahme, dass 1 Schritt 1 Zeiteinheit benoetigt. Logarithmisches Komplexitaetsmass: Eine Komplexitaetsangabe, unter der Annahme, dass die Verarbeitung einer Zahl z log(z) Zeiteinheiten benoetigt. Konvertierung einer Turing-Maschine in eine RAM: Die Schaffung einer RAM, die aequivalent zu einer vorgegebenen Turingmaschine ist. Dazu werden die Zeichen der Turingmaschine durchnummeriert, und die RAM wird statt auf den Zeichen auf den Nummern laufen. Das unendlich lange Band wird durch die Register simuliert, indem die Register immer abwechselnd fuer eine rechte und fuer eine linke Speicherzelle stehen. Die Register 1 und 2 werden allerdings zu Rechenzwecken benoetigt. Ist die Turingmaschine in O(t(n)) mit t(n)>=n, so ist auch die zugehoerige RAM in O(t(n)). Konvertierung einer RAM in eine Turing-Maschine: Die Schaffung einer Turingmaschine, die aequivalent zu einer vorgegebenen RAM ist. Die RAM muss dazu mindenstens in O(n) liegen. Zur Simulation der RAM wird die Eingabeliste der RAM als Folge von Dezimalziffern mit Vorzeichen interpretiert. Man konstruiert nun eine k-Band-Maschine mit folgenden Baendern: 1. Band: Anzahl und Liste der Eingabezeichen 2. Band: (_ i _ y[i])*, also die Folge von Registern mit zugehoeriger Nummer, jeweils dezimal codiert. 3. Band: Wert des Programmzaehlers (binaer) 4-6. Band: Hilfsbaender fuer Addition, Subtraktion, Shiften, Vergleiche 7. Band: Ausgabeband Diese 7-Band-Maschine kann in eine Turingmaschine transformiert werden. Aufwand der Simulation: Macht die RAM t(n) Schritte, so koennen in den Registern hoechstens Zahlen der Laenge O(t(n)) stehen, da sich die Laenge der Zahlen in jedem Schritt um hoechstens eine konstante Laenge vergroessern kann. Die Laenge des 2. und 7. Bandes ist somit in O(t(n)^2). Da die Simulation eines Befehls hoechstens t(n) Schritte benoetigt, liegt die k-Band-Maschine in O(t(n)^3) und die Turingmaschine in O(t(n)^5). Polynomiell entscheidbare Sprache: Eine Sprache, fuer die es eine Turingmaschine gibt, die sie in O(n^d) entscheidet (fuer eine natuerliche Zahl d). Menge der polynomiell entscheidbaren Sprachen: Die Menge aller polynomiell entscheidbare Sprachen ueber einem Alphabet T wird mit P(T) bezeichnet. Mit polynomiellem Platz entscheidbare Sprache: Eine Sprache, fuer die es eine Turingmaschine gibt, die in SPACE(n^d) liegt (fuer eine natuerliche Zahl d) und die Sprache entscheidet. Menge der mit polynomiellem Platz entscheidbaren Sprachen: Die Menge aller mit polynomiellem Platz entscheidbaren Sprachen ueber einem Alphabet T wird mit PSPACE(T) bezeichnet. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Problemtypen ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Algorithmus: Eine endliche Folge von Anweisungen. Hier werden die Begriffe "Algorithmus" und "Turingmaschine" aequivalent benutzt. Da der Algorithmus zu einer Eingabe ein Ergebnis berechnen kann, werden auch die Begriffe "berechenbare Funktion" und "Algorithmus" aequivalent benutzt. Datenkonvertierung in Woerter: Jedes Datum laesst sich als Zeichenfolge ausdruecken: * Natuerliche Zahlen als Binaerstring * Ganze Zahl als Binaerstring mit Vorzeichen * Rationale Zahl als Bruch zweier ganzer Zahlen * Datenvektoren als Liste von Zahlen mit Komma als Trennzeichen * Datenmatritzen als Liste von Vektoren mit Semikolon als Trennzeichen * Endliche Mengen wie Vektoren * Endliche Funktionen als Menge von Eingabe-Ausgabe-Tupeln * Graphen als Adjazenz-Matrix oder Adjazenz-Liste // Diese Behauptung ist trivial: Schliesslich werden alle Theorien der // Mathematik und Informatik schriftlich fixiert, wobei die // Datenkonvertierung unausweichlich stattfindet. Entscheidungsproblem: Ein Tupel aus zwei Sprachen I und E ueber demselben Alphabet T, wobei I in P liegt. I ist die Menge der Instanzen und E ist die zu entscheidende Eigenschaft. Gefragt ist also, ob ein bestimmtes Element aus dem "Definitionsbereich" I in E liegt. // Ist im Allgemeinen E eine Teilmenge von I (?) Jedem Entscheidungsproblem ist die Sprache L all derer Woerter zugeordnet, die in I und E liegen, L=I\/E. polynomiell loesbares Entscheidungsproblem: Ein Entscheidungsproblem, fuer das es eine polynomielle Turingmaschine gibt, die fuer alle x E I\/E in q+ landet und fuer alle x E I\/Ec in q-. polynomiell ausgeglichene Relation: Eine Relation R ueber einem Alphabet T, fuer die es ein Polynom q(n) gibt, sodass fuer alle (x,y) E R gilt: |y| =< q(|x|). Die Laenge des "Ergebnisses" y ist also bereits durch die "Eingabe" x beschraenkt. Es gibt zu einem gegebenen x also nur |T|^q(|x|) viele in Frage kommende y's. Suchproblem: Ein Tupel aus zwei polynomiell entscheidbaren Sprachen I < T* und S < T* x T*, wobei S polynomiell ausgeglichen ist. I ist die Menge der Instanzen und S ist die Suchrelation. Die Aufgabe ist, zu einem gegebenen x E I ein y zu finden, sodass S(x,y) gilt. Da S polynomiell beschraenkt ist, gibt es stets die Moeglichkeit, alle |T|^q(|x|) viele in Frage kommenden y durchzuprobieren. Dieser Algorithmus haette aber exponentielle Laufzeit. polynomiell loesbares Suchproblem: Ein Suchproblem, fuer das es eine polynomielle Turingmaschine gibt, die fuer ein x E I in q+ landet und ein y berechnet, sodass S(x,y) gilt. Gibt es kein solches y, so soll die Turingmaschine in q- landen. NP-Entscheidungsproblem: Ein Tupel aus zwei polynomiell entscheidbaren Sprachen I < T* und S < T* x T*, wobei S polynomiell ausgeglichen ist. I ist die Menge der Instanzen und S ist die Suchrelation. Die Aufgabe ist (im Unterschied zum Suchproblem), zu einem gegebenen x aus I zu entscheiden, ob es ein y gibt mit S(x,y). Das NP-Entscheidungsproblem ist damit ein Entscheidungsproblem (I,E), wobei E die Menge all derer x ist, zu denen es ein y gibt mit S(x,y). polynomielle loesbares NP-Entscheidungsproblem: Ein NP-Entscheidungsproblem, dessen zugeordnetes Entscheidungsproblem polynomiell loesbar ist. NP-Sprache: Eine Sprache L, zu der es eine polynomiell ausgeglichene und polynomiell entscheidbare Relation S < T* x T* gibt, sodass L die Sprache all derer x ist, fuer die S(x,y) gilt. Die Entscheidung, ob ein Wort in L ist, beinhaltet die Suche in einem exponentiell grossen Suchraum mit einem polynomiellen Erfolgstest. // Im Skript taucht in der Definition noch ein undeklariertes I auf. Generate-and-Test-Paradigm: Die Idee, exponentiell viele Woerter zu generieren und fuer diese jeweils in polynomieller Zeit zu entscheiden, ob sie einer gegebenen NP-Sprache angehoeren. Menge aller NP-Sprachen: Die Menge aller NP-Sprachen ueber einem Alphabet wird mit NP(T) bezeichnet. Sie ist die Menge aller "Generate-and-Test-Suchsprachen". P ist eine Teilmenge von NP, denn die Zugehoerigkeit zu einer polynomiell entscheidbaren Sprache L laesst sich als Suche nach einer Loesung y auffassen, wenn die Suchrelation L x {epsilon} ist: Entweder, das Eingabewort x ist in L, dann erfuellt y=epsilon die Relation S(x,y), oder aber x ist nicht in L, dann gibt es keine Loesung. boolsche Formel: * ein Element einer Variablenmenge V ODER * ein String der Form "~x", wenn x eine boolsche Formel ist ODER * ein String der Form "(x /\ y)", wenn x,y eine boolsche Formeln sind ODER * ein String der Form "(x \/ y)", wenn x,y eine boolsche Formeln sind ODER * der String "f" ODER * der String "t" Damit ist eine boolsche Formel ein logischer Ausdruck, den man bei einer Variablenbelegung zu "true" oder "false" auswerten kann. Fuer eine boolsche Formel phi mit den Variablen v[i] schreibt man auch phi(v[1], v[2], ... v[n]). Boolsche Formeln werden im Folgenden mit "phi" oder "psi" bezeichnet, Variablen mit v[i]. Die Klammerung in /\-Sequenzen oder \/-Sequenzen wird oft weggelassen. Literal: Eine boolsche Formel der Form "v" oder "~v", wobei v eine Variable ist. Klausel: Eine boolsche Formel der Form "(v[1] \/ v[2] ... \/ v[n])", wobei die v[i] Variablen sind. Boolsche Formel in konjunktiver Normalform: Eine boolsche Formel der Form "(x[1] /\ x[2] ... /\ x[n])", wobei die x[i] Klauseln sind. Jede boolsche Formel laesst sich unter Erhalt ihrer Interpretation (s.u.) in Normalform bringen. Menge aller boolschen Formeln: Die Menge aller boolschen Formeln ueber einer Variablenmenge V wird mit B(V) bezeichnet. Variableninterpretation: Eine Funktion I:V -> {0,1}, die jeder Variablen einen Wahrheitswert 0 ("false") oder 1 ("true") zuordnet. Damit ist I eine Variablenbelegung. Formelinterpretation: Eine Funktion I*:B(V) -> {0,1}, die boolschen Formeln ueber einer Variablenmenge V einen Wahrheitswert zuordnet. Fuer eine gegebene Variablenbelegung I:V->{0,1} berechnet sich I* von einer boolschen Formel wie folgt: * I*(t)=1 * I*(f)=0 * I*(v)=I(v) fuer alle Variablen v aus V * I*(~psi) = 1-I*(psi) * I*(psi /\ phi) = min { I*(phi), I*(psi) } * I*(psi \/ phi) = max { I*(phi), I*(psi) } Mit diesen Regeln erhalten die ueblichen Aequivalenzumformungen einer boolschen Formel phi den Wert von I*(phi). Implikation: Ein boolscher Operator "=>" mit I*(a => b) == I*(~a \/ b). Gegenseitige Implikation fuehrt zu Gleichheit: I*( (a => b) /\ (b => a) ) == I*( (~a /\ ~b) \/ (a /\ b) ) Erfuellende Variableninterpretation: Fuer eine boolsche Formel phi eine Variablenbelegung I, mit der I*(phi)=1 gilt. Erfuellbare boolsche Formel: Eine boolsche Formel, fuer die es eine erfuellende Variableninterpretation gibt. Erfuellbare Menge boolscher Formeln: Eine Menge boolscher Formeln, fuer die es eine einzige Variablenbelegung I gibt, welche alle Formeln der Menge erfuellt. Erfuellbarkeitsproblem der Aussagenlogik: Das Suchproblem mit der Vereinigung aller boolschen Formeln B(V) mit endlichem V als Instanzenmenge und der Suchrelation, die einer Formel ihre erfuellenden Variablenbelegungen zuordnet. Die Aufgabe ist also, zu einer gegebenen boolschen Formel eine erfuellende Variablenbelegung zu suchen. Variablen-Einsetzen: Das Anwenden der folgenden Produktionen auf eine boolsche Formel phi (v[j] ist dabei eine vorgegebene Variable, w ein vorgegebener Wert aus {"t","f"}): * v[j] -> w * ~t -> f * ~f -> t * (psi /\ f) -> f * (f /\ psi) -> f * (psi /\ t) -> psi * (t /\ psi) -> psi * (psi \/ f) -> psi * (f \/ psi) -> psi * (psi \/ t) -> t * (t \/ psi) -> t Fuer das Ergebnis schreibt man phi(v[1], v[2], ... v[j-1], w, v[j+1], ..., v[n]). Es gilt I*(phi(v[1],... w, ..., v[n])) = I*(phi(v[1], ...v[n]) fuer einen Wahrheitswert w, d.h. eine erfuellende Variablenbelegung bleibt auch mit der richtigen Wahl fuer v[j] erfuellend. Suche nach erfuellenden Interpretationen: Haette man einen Algorithmus, der in polynomieller Zeit entscheidet, ob eine boolsche Formel erfuellbar ist, so koennte man in polynomieller Zeit eine erfuellende Variablenbelegung finden. Beweis: Dazu muss man lediglich die erste Variable probeweise durch "t" ersetzen. Ist die entstehende Formel erfuellbar, so macht man bei der zweiten Variablen weiter, andernfalls probiert man, die erste Variable durch "f" zu ersetzen. Dies fuehrt man bis zur letzten Variablen fort. Anmerkung: Leider gibt es bislang keinen solchen polynomiellen Entscheidungsalgorithmus und man vermutet, dass es auch keinen geben kann. Suchprobleme und Sprachen: Die obige "Suche nach einer erfuellenden Interpretation" laesst sich in vielen Faellen auf andere NP-Sprachen uebertragen: Gaebe es einen polynomiellen NP-Entscheidungsalgorithmus, so koennte man einen polynomiellen Suchalgorithmus angeben. Optimierungsproblem: Ein Tupel aus * einer polynomiell entscheidbaren Instanzenmenge I < T* * einer polynomiell entscheidbaren und polynomiell ausgegelichenen Suchrelation S < T* x T*, wobei es zu jedem x aus I mindenstens ein y aus T* gibt mit S(x,y). * einer polynomiell berechenbaren Zielfunktion c:S->N, die jedem (x,y) aus S eine natuerliche Zahl zuordnet * einem Modus aus {MIN, MAX} Es handelt sich also um ein erweitertes Suchproblem, bei dem zu einer Instanz nicht nur irgendeine passende Loesung gefunden werden soll, sondern eine "optimale". Die Guete eines Instanz-Loesung-Paares wird mit der Funktion c berechnet: Ist der Modus MAX, so ist ein groesserer Wert besser (c ist dann eine Wertfunktion), ist der Modus MIN, so ist ein kleinerer Wert besser (c ist dann eine Kostenfunktion). MIN- und MAX-Optimierungsprobleme sind ineinander umwandelbar, dazu muss lediglich die Kostenfunktion negiert werden. polynomiell loesbares Optimierungsproblem: Ein Optimierungsproblem, zu dem es einen Algorithmus gibt, der in polynomieller Zeit eine optimale Loesung findet. Extremumproblem eines Optimierungsproblems: Die Frage nach dem optimalen Wert c(x,y) eines Optimierungsproblems. Ein das Extremumproblem loesender Extremumalgorithmus berechnet also nicht die optimale Loesung, sagt aber, welche Kosten bzw. welchen Nutzen die optimale Loesung hat. Oft gilt: Hat man einen polynomiellen Extremumalgorithmus, so kann man die optimale Loesung des Optimierungsproblems in polynomieller Zeit bestimmen. Entscheidungsproblem eines Optimierungsproblems: Das Entscheidungsproblem, ob es zu gegebener Instanz x und gegebener Oberschranke m eine Loesung y gibt, sodass S(x,y) und c(x,y)== m fuer Modus MAX). Ein polynomieller Extremumalgorithmus impliziert natuerlich die polynomielle Loesbarkeit dieses Entscheidungsproblems (man muss das Ergebnis des Extremumalgorithmus' lediglich mit m vergleichen). Umgekehrt impliziert aber auch die polynomielle Loesbarkeit des Entscheidungsproblems die polynomielle Loesbarkeit des Extremumproblems. Beweis fuer MIN-Optimierungsprobleme: Zunaechst findet man eine Obergrenze fuer das Minimum der Kostenfunktion fuer die Eingabe x. Wegen der polynomiellen Ausgeglichenheit von S laesst sich auch y polynomiell begrenzen. Da c sodann selbst polynomiell berechenbar ist, laesst sich auch das Ergebnis c(x,y) anhand von x und y polynomiell begrenzen. Nun werden anhand binaerer Suche alle positiven Zahlen unter dieser Obergrenze durchsucht, bis man dasjenige m gefunden hat, ab dem der Entscheidungsalgorithmus gerade mit "ja " antwortet. m ist das gesuchte Minimum. Beweis fuer MAX-Optimierungsprobleme: Jedes MAX-Optimierungsproblem ist ein MIN-Optimierungsproblem mit negierter Kostenfunktion. Optimierungsprobleme und Sprachen: Da sich zu jedem Optimierungsproblem ein zugehoeriges Entscheidungsproblem angeben laesst, lassen sich Optimierungsprobleme auf Sprachen zurueckfuehren. Polynomiell reduzierbare Sprache: Eine Sprache L1 ist polynomiell reduzierbar auf eine Sprache L2, wenn es eine polynomielle Funktion f:L1->L2 gibt, sodass x in L1 liegt genau dann wenn f(x) in L2 liegt. f ist dann die "polynomielle Reduktion" von L1 auf L2. Man schreibt: L1 = ( (L1 in NP) == (L2 in NP) ) & ( (L1 in P) == (L2 in P) ) = f(x) in L2 Damit wird gezeigt: Auch die andere Sprache ist NP-vollstaendig. Plausibilitaet: Waere L2 polynomiell entscheidbar, so koennte man einfach polynomiell schnell f(x) bilden, herausfinden, ob f(x) in L2 ist und haette somit die Zugehoerigkeit von x zu L1 polynomiell schnell entschieden. Die Reduktion f muss allgemeingueltig fuer alle x durchgefuehrt werden und auch fuer x nicht aus L1 definiert sein (in diesem Falle wird f tunlichst ein Dummywort liefert, welches nicht in L2 ist). Ordnung der Sprachen: NPC sind die "groessten" Probleme im Sinne von = (L1 \/ L2)) /\ ((L1 \/ L2) => H) /\ (H \/ L3 \/ D) bzw. nach Aequivalenzumformungen: (~H \/ L1 \/ L2) /\ (~L1 \/ H \/ H) /\ (~L2 \/ H \/ H) /\ (H \/ L3 \/ D) Diesen Prozess wiederholt man, bis keine Klausel mehr als 3 Literale enthaelt. Da lediglich Aequivalenzumformungen durchgefuehrt wurden, gilt I*(phi)=I*(f(phi)) fuer alle I* und fuer alle phi. Fuer syntaktisch inkorrekte Formeln phi setzt man f(phi)=phi, sodass f(phi) nicht in 3SAT sein kann. Damit kann 3SAT von SAT reduziert werden und ist NP-vollstaendig. komplementaeres Paar: Zwei Literale, von denen das eine eine Variable ist und das andere das Negat dieser Variablen. Clique: Eine Clique im Sinne der theoretischen Informatik ist eine Teilmenge von Knoten eines Graphen, bei der jeder Knoten mit jedem verbunden ist. *-* |X| *-* Clique-Problem: Das Entscheidungsproblem, ob es zu einem Graphen eine Clique gibt, die mindestens eine bestimmte Anzahl Knoten umfasst. Das Clique-Problem ist NP-vollstaendig. Beweis: Es laesst sich von 3SAT reduzieren. Dazu konstruiert man einen Graphen mit einem Knoten fuer jedes Literal. Sodann verbindet man all diejenigen Literale mit einer Kante, die erstens nicht in derselben Klausel stehen und zweitens kein komplementaeres Paar bilden (sprich: gleichzeitig erfuellt sein koennen). Die Zahl n der Cliquenmitglieder sei die Anzahl der Klauseln. Wenn nun eine Formel erfuellbar ist, so hat der Graph eine Clique von genau n Mitgliedern -- denn Erfuellbarkeit bedeutet, dass jede Klausel ein wahres Literal enthalten muss. Die wahren Literale schliessen sich also nicht aus, sind somit im Graphen verbunden und bilden die gesuchte Clique. Wenn nun umgekehrt eine Clique von n Mitgliedern existiert, so ist die Formel auch erfuellbar: Dann muss naemlich jede Knotenteilmenge, die einer Klausel entspricht, ein beteiligtes Literal haben. Diese setzt man auf "true" und erhaelt eine widerspruchslose Formel. Klausel1 Klausel2 *----------* ________/ */ __* *=======´--* Knapsack-Problem, Rucksackproblem: Das Suchproblem, zu einer Menge von natuerlichen Zahlen eine Teilmenge davon zu finden, deren Summe gleich einer vorgegebenen Zahl ist. Das zugehoerige NP-Entscheidungsproblem ist die Frage, ob es eine solche Teilmenge ueberhaupt gibt. Das Knapsack-Problem ist NP-vollstaendig. Beweis: Es laesst sich von 3SAT reduzieren, 3SAT = L3={3,2,1,2,2,4,3,5}= *** ** * ** ** **** ** ***** Auch mehrelementige Teilmengen von L1 koennen mit einer einelementigen Teilmenge von L2 gematcht werden (und andersrum). Das zugehoerige NP-Entscheidungsproblem ist NP-vollstaendig. Beweis: Es laesst sich vom Partition-Problem reduzieren, Partition = *-*-*-*-*-* 1-> | | | | * * * * | | | | 2-> *-*-*-*-*-* 2-> Nun werden alle Dreiecke und alle Weichen wie folgt mit Bruecken verbunden: Jede Kante eines Dreiecks, die fuer ein positives Literal steht, wird mit der t-Kante der zugehoerigen Weiche verbunden. Jede Kante eines Dreiecks mit negativem Literal wird mit der f-Kante der zugehoerigen Weiche verbunden. Nun wird der Start-Knoten durch eine einfache Kante mit einem Knoten der ersten Weiche verbunden, und alle Weichen werden durch einfache Kanten aneinander gehaengt. Letzter Knoten der Schlange ist ein Dummy-Knoten. Der andere Dummy-Knoten wird mit dem Zielknoten verbunden. S | * * + + * / \_____/ \ * * * + * \ / / \ + * * + * + * *-----* * * * + * | + + * * ^-- andere Knoten, die das noch / \ nicht begriffen haben \ / * | D1 D2--Z End-Knoten eines Hamiltonpfades muessen S und Z sein, da sie mit keinem "Ausgang" versehen sind. Ein Weg wuerde also bei S beginnen, bei jeder Weiche den t- oder f-Pfad waehlen und bei Z enden. Werden die Bruecken von einer Weiche aus abgeklappert, so verfolgt der weitere Pfad zwangslaeufig die Weiche weiter. Wird eine Bruecke von der Seite eines Dreiecks besucht, so fuehrt der Pfad ebenfalls zurueck zum Dreieck. Ist der Weg S->D1 besucht, so beginnt nun das Abklappern der Dreiecke. Nur wenn mindestens eine anschliessende Bruecke bereits besucht wurde, besteht noch die Chance, wirklich alle Knoten genau einmal zu besuchen. Sind naemlich alle Bruecken unbesucht, so fuehrt das Besuchen aller 3 Bruecken in eine Sackgasse. Wenn die Formel erfuellbar war, so ist kann man den Weg S->D1 gemaess der Variablenbelegung abfahren und jedes Dreieck erhaelt auf diese Weise mindestens eine schon befahrene Bruecke. Andererseits fuehrt jeder Hamiltonpfad zu einer gueltigen Interpretation der Formel. Damit ist das 3SAT-Problem auf das HP-Problem reduzierbar. HC-Problem, Hamiltonian Circuit Problem, Hamilton-Kreis-Problem: Die Entscheidungsfrage, ob es zu einem Graphen einen Hamilton-Kreis gibt. Dieses Problem ist NP-vollstaendig. Beweis: Es laesst sich von 3SAT reduzieren. Der Beweis geht aehnlich wie beim HP-Problem, nur wird eine Kante zwischen S und Z eingefuegt. DHP-Problem, Directed Hamiltonian Path Problem: Die Entscheidungsfrage, ob es zu einem gerichteten Graphen einen Hamilton-Pfad gibt. Dieses Problem ist NP-vollstaendig. Beweis: Es laesst sich von 3SAT reduzieren. Der Beweis geht aehnlich wie beim HP-Problem, nur wird jede ungerichtete Kante durch zwei wechselseitig gerichtete Kanten ersetzt. DHC-Problem, Directed Hamiltonian Circuit Problem: Die Entscheidungsfrage, ob es zu einem gerichteten Graphen einen Hamilton-Kreis gibt. Dieses Problem ist NP-vollstaendig. Beweis: Es laesst sich von 3SAT reduzieren. Der Beweis geht aehnlich wie beim HP-Problem, nur wird eine Kante zwischen S und Z eingefuegt und jede ungerichtete Kante durch zwei wechselseitig gerichtete Kanten ersetzt. Travelling Salesman Problem, Travelling Saleswoman Problem, Travelling Salesperson Problem, TSP: Das Optimierungsproblem, zu einem gewichteten Graphen einen Weg zu finden, der alle Knoten genau einmal besucht und dessen Kosten minimal sind. Hat man einen polynomiellen Extremumalgorithmus, so kann man den optimalen Weg in polynomieller Zeit berechnen. Beweis: Dazu geht man wie folgt vor: Man berechnet die die minimalen Kosten c mit dem Extremumalgorithmus. Nun waehlt man einen Startknoten und setzt eine beliebige davon ausgehende Kante auf die Kosten c+1. Von dem resultierenden Graphen berechnet man wiederum die minimalen Kosten. Sind diese Kosten gleich geblieben, so benutzt die optimale Loesung die blockierte Kante offensichtlich nicht, denn wuerde sie benutzt, so waeren die Kosten ja mindestens c+1. Auf diese Weise schliesst man der Reihe nach immer mehr Kanten aus, bis keine neue Blockade mehr minimale Kosten von c erlaubt. Die resultierenden Kanten sind der gesuchte Rundweg. Das TS-Problem ist NP-vollstaendig. Beweis: Es laesst sich vom Hamilton-Kreis-Problem reduzieren, TSP = (~a -> b) <=> (~b -> a). Diese kann man in einem Graphen von Variablen und Negaten als gerichtete Kanten anordnen. Einfaches Verfolgen der endlich vielen Kanten offenbart dann eventuelle Widersprueche. Bipartite Matching Problem: Die Entscheidungsfrage, ob es zu 2 gleichgrossen disjunkten Mengen und einer Relation ein perfektes Matching gibt. Dieses Problem ist polynomiell loesbar. Grad eines Knotens: Die Anzahl der Kanten, die der Knoten hat. Isolierter Knoten: Ein Knoten vom Grad 0. Eulerkreis: Ein Weg durch einen unegerichteten Graphen, der jede Kante genau einmal besucht. Ein Graph hat genau dann einen Eulerkreis, wenn 1. jeder Knoten geraden Grad hat (je zwei Kanten werden ja fuer jeden Besuch des Knotens als Eingang und Ausgang benoetigt) 2. Es zu je zwei nicht isolierten Knoten einen Pfad vom einen zum anderen gibt (denn ein Eulerkreis wuerde alle Kanten und damit alle nicht isolierten Knoten ablaufen). D.h. der Graph ist zusammenhaengend. EC Problem, Euler Circuit Problem, Eulerkreis-Problem: Das Entscheidungsproblem, ob es zu einem Graphen einen Eulerkreis gibt. Dieses Problem ist polynomiell loesbar. Beweis: Erfuellt der Graph nicht die Kriterien unter "Eulerkreis", so hat er keinen solchen. Man starte nun in einem Knoten und gehe einen beliebigen Kreis im Graphen. Dies ist moeglich, weil jeder nicht isolierte Knoten mindestens einen Ein- und einen Ausgang hat. Nun kann man zu jedem Knoten A, der noch Kanten uebrig hat, einen Sub-Kreis einflechten, der den urspruenglichen Pfad ueber A unterbricht, eine noch unbenutzte Kante als Ausgang wahelt, ein paar Knoten abklappert und eine andere (notwendigerweise vorhandene) Kante wieder als Eingang zu A benutzt. Dann wird der urspruengliche Kreis fortgesetzt. Dieses Verfahren wiederholt man rekursiv mit jedem Knoten, der noch freie Kanten hat. Auf diese Weise erfasst man alle Kanten, denn gibt es eine unbenutzte Kante, so gibt es auch in dem momentanen Kreis eine unbenutzte Kante, die man zum Anbauen eines Sub-Kreises nutzen kann -- andernfalls waere der Graph nicht zusammenhaengend. Schnitt, Cut: Eine echte, nichtleere Teilmenge der Knoten eines Graphen. Size eines Cuts: Die Anzahl der Kanten, die einen Knoten in dem Schnitt mit einem Knoten ausserhalb des Schnittes verbinden. MINCUT-Problem: Die Entscheidungsfrage, ob es zu einem gegebenen Graphen einen Schnitt mit einer Size gibt, die geringer als eine vorgegebene Schranke ist. Das MINCUT-Problem ist polynomiell loesbar. MAXCUT-Problem: Die Entscheidungsfrage, ob es zu einem gegebenen Graphen einen Schnitt mit einer Size gibt, die groesser als eine vorgegebene Schranke ist. Das MAXCUT-Problem ist NP-vollstaendig. MAX-2SAT: Die Entscheidungsfrage, ob es zu einer 2SAT-Klausel eine Variablenbelegung gibt, die mindestens so viele Klauseln wahr macht wie eine gegebene untere Schranke angibt. Dieses Problem ist NP-vollstaendig.