Reduktion und das PCP

  • Reduktion: Ein Entscheidungsproblem ist reduzierbar auf ein anderes (II1 <= II2) wenn es eine berechenbare totale Funktion gibt, die die E_P-Menge abbildet und wo x in P genau dann, wenn die Funktion von x in Q
  • Reduktionslemma: Wenn unentscheidbares Entscheidungsproblem reduziert wird, dann gilt das auch für Reduktion
  • PCP: Instanz sind 2 gleichlange Listen und eine Lösung ist eine Indexfolge, wo beide Listen gleich werden
  • MPCP: Spezielle Lösung; 1 muss am Anfang stehen
  • Unentscheidbarkeit für MPCP
  • MPCP <= PCP
  • Das Leerheitsproblem für LBAs (kontextsensitive Grammatiken) ist unentscheidbar
  • Schnitt kontextfreier Sprachen: Das Entscheidungsproblem, ob der Schnitt von den Sprachen zwei kontextfreier Grammatiken leer ist, ist unentscheidbar
  • Vollständigkeitsproblem für CFL: Das Entscheidungsproblem, ob die Sprache einer Grammatik die Gesamtheit der Wörter der Grammatik (Alphabet *) ist, ist für kontextfreie Grammatiken unentscheidbar
  • Das Äquivalenzproblem für kontextfreie Grammatiken ist unentscheidbar

Ackermann



  • Ackermann-Funktion: Bei 0 und y kommt y+1 raus, bei x und 0 kommt die Funktion für x-1 und 1 raus, wenn x größer 0 und für x und y kommt raus die Funktion von x-1 und der Funktion von x und y-1, wenn x und y größer 0
  • Für alle x und y erhält man eine Zahl für a(x,y) bei endlich vielen Anwendungen
  • Es gilt a(x,y) ist größer als y
  • a(x,y+1) ist größer als a(x,y) → Monotonie im zweiten Argument
  • 361
  • Satz von Ackermann: While, aber nicht loop-berechenbar
  • 363
  • Charakteristische Funktion: Geht von Wort zu Wort; X_L; ist erster Buchstabe, wenn das Wort in der Sprache ist und ist leeres Wort, wenn nicht
  • Turing-Entscheidbarkeit: Eine Turing-Maschine entscheidet L, wenn sie die charakteristische Funktion X_L berechnet (also A erreicht für alle Wörter die Stoppkonfiguration)
  • Turing-Akzeptierbarkeit: Wenn Stoppkonfiguration genau für die Wörter der Sprache
  • Charakterisierung der Entscheidbarkeit: Wenn die Sprache Turing-akzeptierbar und die Wortmenge ohne L Turing-akzeptierbar ist
  • Universelle Sprache:
  • Akzeptierbarkeit von U_niv
  • Unentscheidbarkeit von U_niv: Nicht Turing-entscheidbar
  • Wortproblem für DTM: Es gibt keinen Algo, der zu einer DTM entscheidet, ob sie ein Wort aus der Sprache akzeptiert
  • Das Problem „A akzeptiert e“ ist für DTM unentscheidbar
  • Entscheidungsproblem: von der Form II = (E_P, P) mit E_P als Menge der möglichen Eingaben und P echte Teilmenge von E_P


Primitive Rekursion und Mü-Rekursivität



  • Grundfunktionen: Nachfolgefunktion; Nullstellige Konstantenfunktion Wert 0; Einstellige Konstantenfunktion mit Wert 0; Projektion mit Stelligkeit und Angabe; Identitätsfunktion ist die einstellige Variante
  • Funktionskomposition: Erst h-Funktionen auf Stelliges x und dann g auf alle h; f = g ° (h1 ..hn) oder Komp(g,h1,..,hn)
  • Die Komposition von totalen Funktionen gibt wieder eine solche
  • Gleiches bei While- und bei Loop-berechenbaren Funktionen
  • Primitive Rekursion: Aus 2 anderen Funktionen; f(x,0) muss g(x) sein und f(x,y+1) muss h(x,y,f(x,y)) sein; f = PR(g,h)
  • Totalität, Loop, und While-Berechenbarkeit überträgt sich auf PR
  • Primititv-rekursive Funktion: Entweder pr Grundfunktion oder aus GF in endlich vielen Schritten durch pr und komp erzeugbar
  • Loop-Berechenbarkeit von pr Funktionen: Jede pr Funktion ist total und loop-berechenbar
  • Lemma 346
  • Eine Funktion von N hoch k auf N ist genau dann pr, wenn sie loop-berechenbar ist
  • Unbeschränkte Minimalisierung (Anwendung des Mü-Operators): Funktion von x entsteht aus partieller anderer dadurch, dass Minimum der Menge aller y genommen wird, wo g mit x und y 0 ergibt und wo bei allen kleineren Werten die Funktion ein Ergebnis hat. Ansonsten kein Ergebnis (umgedrehtes T) → Schreibweise von
  • Abschluss von While unter Mü-OP: Wenn Basis While-Berechenbar, dann auch f = Mü-OP(g)
  • Mü-Rekursivität: Eine Funktion von N hoch k nach N ist mü-rekursiv, wenn wenn sie aus den Grundfunktionen durch endliche Anwendung von Komposition, primitive Rekursion und unbeschränkte Minimalisierung entsteht
  • Funktion ist genau dann mü-rekursiv, wenn sie while-berechenbar ist

While und Loop bei TGI





  • While und Loop:
  • Wertzuweisung:
  • Programm; Programm
  • loop Variable begin Programm end
  • while Variable do begin Programm end
  • Variable : = Variable +- 1
  • Variable : = 0
  • Variable : = Variable + - Variable
  • Variable ist positive Zahl/ Ziffer ?
  • ?
  • Semantische Funktion eines While-Programms: Wenn Xi gleich Xj + 1, dann wird Xi in dem Variablentupel so ersetzt und so mit - 1, gleich 0, und Variablensumme, -differenz und Gleichsetzung auch. Wenn Programm aus 2 Stück besteht, dann ist es die Hintereinanderführung von den SF für P1 auf die Variablen und dann P2. Beim Loop wird das Programm anscheinend entsprechend der Variablen so oft angewendet (?). Bei While keine Ahnung.
  • Ausgabe ist Wert von X1
  • f tief p hoch (k)
  • Loop/while-berechenbar: falls solches Programm, das Funktion berechnet
  • Jede Loop-berechenbare Funktion ist total
  • Goto-Programm: Von 1 bis m Variablen zugeordnet. - m ist stop und jede Variable hat die Form X_j + - 1 oder if Xj=0 goto l
  • Goto-Konfigurationen: (l,n1,...)
  • Folgekonfiguration
  • P berechnet Funktion, falls bei von 1 bis m x die Funktion über dem Tupel ist und terminiert nicht, falls f undefiniert ist
  • f ist Goto-Berechenbar, falls Goto-Programm f berechnet
  • While0-Programm: While Programme mit Wertzuweisungen der Form Xj = Xj +-1 und ohne loop
  • While0-Berechenbarkeit von While-Programmen: Jede While-Berechenbare Funktion ist While0-Berechenbar
  • Goto-Berechenbarkeit von While0-Programmen
  • Turing-berechenbarkeit von Goto-Programmen
  • While-Berechenbarkeit von Turingmaschinen
  • Normalformensatz: Jede While- oder Goto-Berechenbare Funktion ist durch ein While-programm berechenbar, das nur eine while-Anweisung und Variablen und 5 Hilfsvariablen hat.


Turingmaschinen und Verwandtes



  • Turingmaschine (DTM): Abbildung von Zustand und Buchstaben aus Arbeitsalphabet (mit Blanksymbol) auf Buchstaben aus Arbeitsalphabet, links oder rechts auf Band und neuer Zustand. Zustandsmenge, Eingabealphabet als Teilmenge, Arbeitsalphabet, Anfangszustand,
  • DTM-Konfiguration: Wort aus Arbeitsalphabet-Zustand-Wort aus Arbeitsalphabet
  • Stoppkonfiguration
  • Akzeptierte Sprache: Menge aller Wörter aus Alphabet, wo von Konfiguration ab Startzustand zu Stoppkonfiguration (mit Endzustand)
  • NTM (nicht-deterministische Turingmaschine): Veränderte Übergangsfunktion: Abbildung auf Potenzmenge
  • k-Band-NTM: k Bänder und ein Kopf pro Band; Hier gibt es k-Tupel der gelesenen, geschriebenen Wörter und der Wanderungen. Zustände sind einzeln. Wanderung kann l,r und n sein.
  • Anfangskonfiguration: q0w auf Band 1 und alle anderen haben nur Blanks
  • Redundanz zusätzlicher Bänder: Jede k-Band-NTM kann durch eine 1-Band-NTM simuliert werden
  • Redundanz des Nichtdeterminismus: Wenn L von einer NTM erkannt wird, dann auch von einer DTM
  • LBA(linear beschränkter Automat): Wie NTM; aber mit linker und rechter Endmarkierung, über die das Band nicht hinausgeht und die nicht überschreibbar sind
  • Die von allgemeinen Turingmaschinenen akzeptierten Sprachen sind genau die Typ0-Sprachen
  • Die von LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen
  • Berechnung von Funktionen durch DTM: Eine DTM berechnet eine Funktion, die von einer Liste von Wörtern auf ein Wort abbildet dann, wenn für alle Worttupel aus dem Definitionsbereich gilt, dass das Wort, dass aus den Einzelworten mit Blanksymbol vom Startzustand besteht abgeleitet wird zu der Endkonfiguration mit einem Stoppzustand am Anfang und als Wort rechts daneben das Funktionswort und dass für alle Worttupel, die nicht im Definitionsbereich sind, keine Stoppkonfiguration erreicht wird
  • Funktion ist turing-berechenbar, wenn eine Turingmaschine existiert, die die Funktion berechnet
  • Sequentielle Funktionen: Jede sequentielle Funktion von Worttupel auf Wort ist Turing-berechenbar

Kellerautomaten und alles, was damit zu tun hat

  • Die kontextfreien Sprachen sind abgeschlossen unter Vereinigung, Produkt und Stern
  • Sie sind nicht abgeschlossen unter Schnitt und Komplement
  • Kellerautomat(PDA): Übergang von Zustand in anderen beim Lesen von Buchstaben oder leerem Wort, wobei Z durch y auf der Kellerspitze ersetzt wird: (q, a/e, Z, y, q'). Wenn y leer ist, ist das Pop. Sonst Push. Form (Q, AlphaEingabe, KellerAlpha, q0, Z0, Trans, Endzustände). Y kann Wort sein.
  • Konfiguration Kellerautomat: Zustand, Restwort, Kellerinhalt
  • PDA akzeptiert Wort, wenn Übergang von Konfiguration mit Startzustand und Z0 und ganzem Wort hin zu einer mit leerem Wort und Endzustand
  • Erkannte Sprache: Alle akzeptierten Wörter
  • Akzeptanz mit leerem Keller: Zustand muss kein Endzustand sein!
  • N(A): Sprache mit leerem Keller
  • Deterministischer PDA (DPDA): Wohl: Für alle Kombis höchstens eine Transition und wenn leeres Wort als Übergang, dann darf kein Buchstabe da sein
  • Zu jedem normalen PDA einen mit Kellererkennung und umgekehrt mit Äquivalenz
  • Linksableitung bei kontextfreier Grammatik: Es wird bei jedem Schritt die Variable ersetzt, die am weitesten links steht
  • Wenn ein Wort(?) in einer kontextfreien Grammatik ableitbar ist, dann ist es durch Linksableitung ableitbar
  • Zu jeder kontextfreien Grammatik lässt sich ein PDA angeben, wo N(A) = L(G)
  • e-Bedingung für kontextfreie Grammatiken: Zu jeder Grammatik nur mit Variablen auf der linken Seite kann eine gefunden werden, die die e-Sonderbedingung (ich glaube, e nur vom Startsymbol und das Startsymbol dann niemals rechts) erfüllt
  • Bei einer solchen kann man dann eine Grammatik ohne A → e finden, wo die Sprache dann der Ausgangssprache ohne e entspricht
  • PDAs sind darstellbar durch kontextfreie Grammatiken; dann ist Sprache der Grammatik gleich der N(A) (Worte, bei deren Leerheit Keller leer)
  • Abschluss unter Schnitt mit regulären Sprachen: Wenn eine Sprache durch einen DPDA erkannt wird und eine andere regulär ist, dann wird auch der Schnitt durch einen DPDA erkannt
  • Minimales L-Wort: Wenn Wort in Sprache und kein echtes Präfix in Sprache
  • MIN(L): Menge aller minimalen L-Worte
  • Wenn L deterministisch kontextfrei, dann auch MIN(L)
  • Die Sprache der Verknüpfung aller Wörter mit ihrer Umkehrung(?) ohne das leere Wort ist ncihtdeterministisch(?) kontextfrei
  • deterministische kontextfreie Sprachen sind unter Komplementbildung abgeschlossen, aber nicht unter Schnitt und Vereinigung


Ableitungsbaum und Pumping Lemma II

  • Ableitungsbaum:
  • Unbewerteter, kleiner-gleich k-verzweigter Baum: Menge von Listen, die als Maximum k hat; wo alle Präfixe aller Listen auch in der Menge und für alle Zahlen am Ende der Liste auch alle kleineren ab 1 drin
  • Alphabetbewertete Variante: Abbildung von Listenmenge auf Alphabet (also jede Liste von oben kriegt einen Buchstaben)
  • Ableitungsbaum zur kontextfreien Grammatik: Bewertet durch Variablen und Buchstaben der Grammatik; Wurzel ist mit S beschriftet und die Menge der Nachfolger leitet sich in den Regeln der Grammatik vom Vorgänger ab
  • Wortproblem für CFL: Bei einer kontextfreien Grammatik in CNF entscheidet der CYK-Algorithmus, ob ein Wort in der Sprache der Grammatik ist
  • Leerheitsproblem für CFL: Es gibt Algorithmus, der zu gegebener kontextfreier Grammatik jeweils entscheidet, ob Sprache leer
  • Unterbaum: Unterbaum einer Liste ist Menge aller Listen ohne Liste am Anfang, die mit Liste am Anfang in der Baummenge
  • Pumping-Lemma für kontextfreie Sprachen; uvwxy-Theorem: Kontextfreie Grammatik ohne einfache Regeln; k Variablen; rechte Regelseiten höchstens l mit l mindestens 2 und n ist l hoch k + 1. Dann gilt für alle Worte in der Sprache, die mindestens n sind, dass z in 5 Teile geteilt werden kann mit vx nicht leer; vwx höchstens n und die alle Potenzen von v und x in Sprache zusammen mit Rest