Spicker - Aufgaben aus der Prüfung mit Lösungen. Zum Strg + F drücken. PDF

Preview

Summary

KEStichpunkte: MengengleichheitZeigen Sie, dass alle Kodierungen in Kodierungen mit dem Alphabet Σ1 = {a} umgewandeltwerden können.Stichpunkte: Binärbaum, unbeschriftet, DFS-Tour,Chomsky NormalformKontextfreie PumpinglemmaTuringmaschineAufzählbar: Nach Satz 4 ist eine Sprache genau dann aufzählbar, ...

Description

KE1 Stichpunkte: Mengengleichheit

Zeigen Sie, dass alle Kodierungen in Kodierungen mit dem Alphabet Σ1 = {a} umgewandelt werden können.

Stichpunkte: Binärbaum, unbeschriftet, DFS-Tour,

Sprachen: regulär, abzählbar, endlich, komplement ist entscheidbar

Endlich : NEIN Entscheidbar: JA Komplement der Sprache entscheidbar: JA abzählbar: JA regulär:NEIN

Di eSpr ac hei s ts ehrähnl i c hz u{ a^ nb^ n|n, m >0} .Ei nDEAderLer k ennenwür dek önnt el ei cht umgebautwer den,s odas seral l eb' si gnor i er t( Über gängel ös cht )undc' swi eb' sbehandel n wür de.Dersoumgebaut eDEAwür de{ a^ nb^ n|n, m >0}er k ennen,wasaberni chtsei nk ann, dadi es eSpr acheni c htr egul äri s t .Fol gl i c hi s tauc hLni c htr egul är . Li stni c htendl i ch,wei lesf üral l en>0dasWor ta^ nbc ^ ni nderSpr ac heent hal t eni s t . Li stent s c hei dbar ,daoffensi c ht l i c hk ont ext f r ei .Dami ti s tauc hdasKompl ementv onL ent sc hei dbar ,denndi eent s c hei dbar enSpr ac hens i ndunt erKompl ementabges c hl oss en. Si gma^ *i s tabz ähl bar ,al s oauc hj edeTei l mengedav on( wi eL ) .

Alle regulären Sprachen sind auch Kontextfrei! Pumping Lemma: Wi rbewei sendi eAus s ageüberdasPumpi ngl emma.Daj agi l tpumpbar[ nurwenn]r egul är ,r ei c ht esausz uz ei gen,dassLni c htpumpbari s t .Seikdi ePumpl änge,dannwähl enwi rdasWor tw= a^ kbi n( k)i nAbhängi gk ei tz uk .Dasf unkt i oni er t ,dadi esesWor tausderSpr ac hev onLi s tund [ ei neLängegr ößergl ei c hkhat ] .Egalwi enunw=xy zget ei l twi r d( nac hdenVor gabender Pumpbar Ei gens c haf t ) ,mus s[ y ]ni cht l eersei nundnurausdenZei chenabes t ehen.Somi ti s tf ür [ i=2]dasWor tx y^ i zni c htausLunddami ti s tdi eseSpr ac heni c htpumpbarunddami tni c ht r egul är

(a) (1) Jede reguläre Menge über E ist eine Typ-O-Sprache. Richtig. Jede reguläre Menge ist eine Typ-3-Sprache, und die Typ-3- Sprachen sind einer Teilklasse der Typ-O-Sprachen (s. Satz 9.4.8). (2) Die Sprache L = {a'bman | Z,ra,n G N} über dem Alphabet T := {a, b} ist eine Typ-3Sprache. Richtig. Man kann leicht einen endlichen Automaten angeben, der die Sprache akzeptiert. (3) Die endlichen Sprachen über E sind unter Komplementbildung abge schlossen. Falsch. Die Komplemente der endlichen Teilmengen von E* sind un endliche Mengen. (4) Die Typ-3-Sprachen über E sind unter Vereinigungsbildung abgeschlos sen. Richtig. Siehe Satz 8.4.1. (5) Das Äquivalenzproblem für reguläre Mengen über E ist unentscheidbar. Falsch. Siehe Satz 8.4.2. (b) (1) Zu jeder kontextfreien Grammatik G gibt es eine Grammatik G' in Chomsky-Normalform mit L(G) = L(Gf). Falsch. Dies gilt nicht, falls e G L(G). (2) Gibt es zu einer Sprache L C E* ein p G N, so dass man jedes Wort z G L mit lg(z) > p so in Teilworte u, v} w,x, y zerlegen kann, dass (i) z = uvwxy, (ii) vx ^ e, (iii) lg(vwx) < p und (iv) Vi > 0. uvzwx%y G L gilt, dann ist L kontextfrei. Falsch. Nur die umgekehrte Implikation gilt. (3) Jede Sprache, die von einem determinierten Kellerautomaten erkannt wird, ist kontextfrei. Richtig. Die deterministisch kontextfreien Sprachen sind eine Teilklas se aller kontextfreien Sprachen. (4) Die deterministisch kontextfreien Sprachen sind unter Komplement bildung abgeschlossen. Richtig. Siehe Satz 9.6.5. (5) Das Äquivalenzproblem für kontextfreie Sprachen ist unentscheidbar. Richtig. Siehe Satz 9.7.3. (c) (1) GAP ist eine Typ-1-Sprache. Richtig. Siehe Satz 7.4.1. (2) Es seiL C E* einekontextsensitive Sprache. Dann ist ihr Komplement E* \ L eine entscheidbare Menge. Richtig. Nach Korollar 7.4.2 ist L entscheidbar. Damit ist auch E* \L entscheidbar. (3) Jede rekursiv-aufzählbare Menge L C E* ist eine Typ-O-Sprache. Richtig. Siehe Satz 7.2.2. (4) Das Wortproblem für Typ-O-Sprachen ist entscheidbar. Falsch. Dies ist (im Wesentlichen) das Halteproblem für Turingmaschinen, und das ist bekanntermaßen unentscheidbar.

Chomsky Normalform

Kontextfreie Pumpinglemma

Turingmaschine

Der Logarithmus einer Zahl ist die Anzahl, wie häufig die Zahl durch 2 geteilt werden kann (der Rest 1 kann dabei ignoriert werden). Die Idee ist nun, dies zu nutzen. Bei jedem Durchlauf teilen wir also die Anzahl der as durch zwei mit Rest, wobei der Rest ignoriert 1 wird, formal: von n-vielen as, behalten wir bn/2c viele. Die anderen ersetzten wir durch x. Wir starten genau so viele Durchläufe wie es bs gibt. Wenn am Ende nur noch ein a auf dem Band steht, akzeptieren wir. 1. Teste, ob die Eingabe leer ist, falls ja, stoppe verwerfend. 2. Teste, ob die Eingabe so aufgebaut ist, dass zuerst as dann bs kommen. Falls nein stoppe verwerfend, ansonsten fahre fort. 3. Teste, ob die Eingabe nur noch ein a enthält (alle anderen as und bs sind durch x ersetzt). Falls ja, stoppe akzeptierend. 4. Teste, ob noch ein b in der Eingabe steht und ersetzte es durch x. Falls nein, stoppe verwerfend. 5. Ersetzte jedes zweite a durch x, wobei wir beim linkesten a anfangen (damit ignorieren wir den Rest, denn wenn eine ungerade Anzahl n an as auf dem Band steht, dann streichen wir (n + 1/2)). 6. Führe mit Schritt 2 fort.

Eine Einmal-Turingmaschine ist eine Variante einer Turingmaschine, die sich dadurch von einer normalen Turingmaschine unterscheidet, dass jede Zelle des Eingabebandes nur einmal überschrieben werden darf (inklusive der Eingabe, das heißt, die Zellen, auf denen die Eingabe steht, dürfen auch noch genau einmal neu beschrieben werden). Zeigen Sie: Einmal-Turingmaschinen können die gleichen Sprachen erkennen wie Turingmaschinen. Hinweis: Versuchen Sie zuerst, eine Zweimal-Turingmaschine zu erstellen, das heißt, jede Zelle darf genau zweimal verändert werden.

Eine Zweimal-Turingmaschine simuliert einen Schritt einer „normalen“ Turingmaschine, indem sie die komplette Eingabe einfach nochmal hinter die aktuelle Eingabe schreibt. Während des Kopierens führt man bereits die Bandmodifikation des aktuellen Befehls aus. Man kann die beiden Eingaben mit einem Sonderzeichen trennen (dies ist aber nicht unbedingt nötig). Jede Zelle wird genau zweimal beschrieben, das erste mal, um das Zeichen daraufzuschreiben und das zweite mal, um sie beim Umkopieren zu markieren. Dies ist nötig, da wir ansonsten nicht wissen, welche Zeichen bereits markiert sind. Die Zelle, die den Kopf enthält, muss ebenfalls markiert sein, so dass beim Umkopieren der Schritt der Orginalturingmaschine simuliert werden kann. Die Zweimal-Turingmaschine kann durch eine Einmal-Turingmaschine simuliert werden, indem man einfach jede Zelle beim Umkopieren durch einen Block von zwei aufeinander folgenden Zellen darstellt. In der ersten Zelle steht das Zeichen und die zweite ist dafür da, um zu markieren, ob man die Zelle schon umkopiert hat. Der Rest verläuft analog zur Simulation einer Turingmaschine durch eine Zweimal-Turingmaschine. Beachte: Zu Beginn ist die Eingabe nicht in diesem 2-Zellenformat, beim ersten Umkopieren werden einfach die Zeichen in der Zelle markiert (die Zellen, auf denen zu Beginn die Eingabe stand, dürfen ja auch nochmal überschrieben werden).

Aufzählbar: Nach Satz 4.4 ist eine Sprache genau dann aufzählbar, wenn sie erkennbar ist. Wir zeigen, dass die Sprache L erkennbar ist, indem wir eine Turingmaschine M0 angeben, die L erkennt. Diese Turingmaschine bekommt also eine Eingabe hMi. Wir müssen nun testen, 2 ob M auf mindestens einer Eingabe w hält. Dazu verfahren wir ähnlich wie im Beweis von Satz 4.4.

Wir testen wieder für alle Wörter aus Σ ∗ , ob M bei Eingabe eines dieser Wörter hält. Für die Simulation von M(w) nutzen wir ein Unterprogramm analog zur universellen Turingmaschine. Wir können natürlich nicht alle Wörter der Reihe nach probieren, da die Simulation bei einer Eingabe zykeln könnte. Um dieses Problem zu umgehen, arbeiten wir wieder in Runden. In der Runde i werden wir die ersten i Eingaben maximal i Schritte auf M simulieren. Wenn eine Eingabe von M akzeptiert wird, dann gehört hMi zu L und wir akzeptieren. Falls M gar kein Wort akzeptiert, dann wird unsere Simulationsschleife endlos laufen. In diesem Falle würde M0 zykeln und wir würden hMi deshalb nicht akzeptieren.

Aufzählbar, abzählbar Finden Sie eine Sprache, die nicht aufzählbar, aber abzählbar ist. Gibt es auch eine Sprache, die aufzählbar, aber nicht abzählbar ist?

(a) L1 ist nicht entscheidbar. Die Eigenschaft, ob eine Sprache ε enthält, ist nicht trivial. Folglich kann man den Satz von Rice anwenden.

Wahr Falsch (a) Jede kontextfreie Sprache hat unendlich viele Klassen in ihrer Myhill-Nerode Relation. Falsch: Reguläre Sprachen haben endlich viele Klassen in ihrer Myhill-Nerode Relation. Reguläre Sprachen sind aber auch kontextfrei. (b) Die Vereinigung von einer kontextfreien und einer nicht kontextfreien Sprache ist nie kontextfrei. Falsch: Betrachten wir folgende Sprachen A = Σ ∗ und B = {a nb nc n | n ≥ 0}. A ist kontextfrei und B ist nicht kontextfrei. Die Vereinigung A ∪ B = Σ ∗ ist aber kontextfrei.

(c) Die Sprache ATM ist erkennbar. Wahr: Eine Turingmaschine, die ATM erkennt, ist die universelle Turingmaschine. (Diese Aussage ist auch im Kurstext (Satz 4.7) bewiesen.) (d) Jede endliche Sprache ist kontextfrei. Wahr: Jede endliche Sprache ist regulär und jede reguläre Sprache ist kontextfrei (e) Es sei A ein DEA mit n Zuständen. Wenn A mindestens ein Wort der Länge mindestens n erkennt, dann ist L(A) unendlich. Wahr: Zum Abarbeiten eines Wortes der Länge n muss der Automat A n+1 Zustände durchlaufen. Das bedeutet aber, dass mindestens ein Zustand zweimal durchlaufen wurde. Es gibt also eine Schleife auf einem Weg in A, der zu einem akzeptierenden Zustand führt. Damit erkennt A unendlich viele Wörter, L(A) ist folglich unendlich. (f) Es sei A eine Sprache über dem Alphabet Σ. Wenn A aufzählbar und kontextfrei ist, dann ist A entscheidbar. Wahr: A ist kontextfrei und damit entscheidbar. Dies wurde im Kurstext gezeigt. Ein Entscheider kann durch den CYK-Algorithmus realisiert werden. (g) Ist eine Sprache L kontextfrei, dann ist auch die Sprache {w1w2w3 | w1,w2,w3 ∈ L} kontextfrei. Wahr: Kontextfreie Sprachen sind über Konkanetation abgeschlossen. Sei G eine Grammatik für L mit Startvariable S, dann ist S 0 → SSS zusammen mit allen Regeln von G eine Grammatik für die Sprache {w1w2w3 | w1,w2,w3 ∈ L}.

(a) Sei L1 eine Sprache über dem Alphabet Σ, deren Myhill-Nerode Relation endlich viele Klassen hat. Dann ist L1 kontextfrei. Wahr: Aus dem Kurstext ist bekannt, dass eine Sprache, deren MN-Relation endlichen Index (also nur endlich viele Äquivalentklassen) hat, regulär ist. Also ist L1 insbesondere kontextfrei. (b) Die Sprache L = {hMi | L(M) = {a k | k ist Primzahl}} ist entscheidbar. Falsch: Die Eigenschaft U = {{a k | k ist Primzahl}} ⊆ is nicht trivial. Somit ist L nach den Satz von Rice nicht entscheidbar. (c) Wenn Sie für eine Sprache L ∈ NP zeigen können, dass L in P liegt, dann haben Sie bewiesen, dass P = NP gilt. Falsch: Da P ⊆ NP, gibt es sehr viele Sprachen in NP, die auch in P liegen. Dennoch könnte P =/ NP gelten. (d) Es gibt Turingmaschinen, die ihre eigene Codierung ausgeben können. Wahr: Im Kurstext wurde eine Quine Turingmaschine vorgestellt.

Sprache Tabelle regulär abzählbar entscheidbar...