41-wiederholung
Formale Sprachen und Komplexität
Theoretische Informatik für Medieninformatiker
Sommersemester 2021
Wiederholung und Fragestunde
Prof. Dr. David Sabel
LFE Theoretische Informatik
Letzte Änderung der Folien: 13. Juli 2021
Erinnerung / Organisatorisches
Online-Hausarbeit
Anmeldung bis Mi 14 Jul 2021 23:59 im uni2work
Nachholprüfung:
Termin noch nicht genau fest:
Wunsch ist im Zeitraum 04.10. bis 12.10.
Termin wird bekannt gegeben, sobald IfI-Planung uns Ok zurückmeldet
TCS | Wiederholung und Fragestunde | SoSe 2021 2/39
Inhaltsübersicht
Teil I: Formale Sprachen und Automatentheorie
Chomsky-Grammatiken und die Chomsky-Hierarchie
Reguläre Sprachen: DFAs, NFAs, reguläre Ausdrücke, Äquivalenz der
Formalismen, Pumping-Lemma, Satz von Myhill-Nerode, Minimierung von DFAs,
Abschlusseigenschaften, Entscheidbarkeitsresultate
Kontextfreie Sprachen: Chomsky-Normalform, (Greibach-Normalform),
Pumping-Lemma, CYK-Algorithmus, Kellerautomaten (PDA und DPDA),
Abschlusseigenschaften und Entscheidbarkeitsresultate
Kontextsensitive und Typ 0-Sprachen: Kuroda-Normalform, Turingmaschinen
(DTM und NTM), LBAs, Abschlusseigenschaften
TCS | Wiederholung und Fragestunde | SoSe 2021 3/39
Inhaltsübersicht
Teil II: Berechenbarkeitstheorie
Berechenbarkeit
Turingmaschinen und Turingberechenbarkeit
LOOP-, WHILE-, GOTO-Programme und Berechenbarkeit
Primitiv-rekursive und µ-rekursive Funktionen
Unentscheidbarkeit: Halteproblem
Reduktionen, PCP, Satz von Rice
TCS | Wiederholung und Fragestunde | SoSe 2021 4/39
Inhaltsübersicht
Teil III: Komplexitätstheorie
P und NP
NP-Vollständigkeit
Polynomialzeitreduktionen
Satz von Cook
NP-vollständige Probleme
TCS | Wiederholung und Fragestunde | SoSe 2021 5/39
Eingesendete Fragen
Frage
Wird die Fragestunde aufgezeichnet, wenn man zeitlich verhindert ist?
Ja, sogar auch wenn man nicht zeitlich verhindert ist.
TCS | Wiederholung und Fragestunde | SoSe 2021 6/39
Eingesendete Fragen
Frage
Welche Notation für die Komplementbildung soll man bei der Hausarbeit schreiben?
Im TestOnlineHausarbeit.txt habe ich nicht gefunden.
Komplement(L)
Bei fehlenden Notation: Notation selbst definieren
Bis zur Prüfung: Gerne aufzählen im Zulip-Chat, was noch fehlt.
TCS | Wiederholung und Fragestunde | SoSe 2021 7/39
Eingesendete Fragen
Frage
Die Frage betrifft eher die Klausur. Quellen sollen wir in unserer Abgabe ja
kennzeichnen. Gilt dies auch für Sätze aus dem Skript, Ergebnisse aus Übungsaufgaben
oder die Vorlesungsfolien?
Können alle in der Vorlesung gezeigten Beweise / Sätze als gegeben vorausgesetzt
werden (beim Bearbeiten der Klausur)?
Alles aus dem Material-Bereich und die bereitgestellten Übungsaufgaben und
Lösungsvorschläge im Uni2work kann ohne genaue Quellenangabe verwendet werden.
Bei manchen Beweisen kann es trotzdem hilfreich sein
”
siehe Satz 2.12 im Skript“ zu
schreiben, statt
”
siehe Vorlesung“.
TCS | Wiederholung und Fragestunde | SoSe 2021 8/39
Eingesendete Fragen
Frage
Bedeutet beim Pumping Lemma i = 0, dass das Wort v bzw v, x 0 mal aufgepumpt
wird oder 1 mal (weil irgendwas0 als 1 definiert ist)? Mich haben da manche Beweise
ein wenig verwirrt.
Für Symbole gilt: a0 = ε Daher: 0 mal.
TCS | Wiederholung und Fragestunde | SoSe 2021 9/39
Eingesendete Fragen
Frage
Wie lassen sich epsilon und leere Menge bei beispielsweise Angaben von akzeptierten
Sprachen genau unterscheiden?
L(M) = {} leere Sprache
L(M) = {ε} oder L(M) = {epsilon}
TCS | Wiederholung und Fragestunde | SoSe 2021 10/39
Eingesendete Fragen
Frage
Gibt es empfehlenswerte Text-Editoren im Hinblick auf eine möglichst effiziente
Eingabe mathematischer Unicode-Zeichen?
Aus der Angabe kopieren?
TCS | Wiederholung und Fragestunde | SoSe 2021 11/39
Eingesendete Fragen
Frage
Warum fasst man beim letzten Schritt der Berechnung der Chomsky NF (Zerlegen der
rechten Seiten) gleiche Produktionen nicht zusammen, sondern erstellt immer wieder
ein neues Symbol? In der Vorlesung wurde beim Beispiel für A2A1 C1, C3, und C4
verwendet.
Ist nur
”
Faulheit“ des Algorithmus. Man könnte auch nur eine Produktion verwenden.
TCS | Wiederholung und Fragestunde | SoSe 2021 12/39
Eingesendete Fragen
Frage
Muss man in der Klausur 2 getrennte Abgaben machen, eine im TXT-Format, die den
automatischen Teil enthält und eine als PDF, die die restlichen Lösungen enthält ?
Nein es wird genau eine Text-Datei abgegeben.
Alle Aufgaben werden in TXT-Format bearbeitet.
PDFs und Grafiken usw. sind nicht erlaubt.
TCS | Wiederholung und Fragestunde | SoSe 2021 13/39
Klassiker:
”
Rechenaufgaben“
Transformation NFA in DFA mit Potenzmengenkonstruktion
Minimierung von DFAs
Chomsky-Normalform berechnen
CYK-Algorithmus ausführen
TCS | Wiederholung und Fragestunde | SoSe 2021 14/39
Beispielaufgabe zu endlichen Automaten
Gegeben sei der folgende NFA über Σ = {a, b}.
z0
z1z2 z3
a, b
a b
a
b
a) Welche Sprache erkennt der gezeigte NFA?
b) Geben Sie die Sprache durch einen regulären Ausdruck an.
c) Erzeugen Sie einen äquivalenten DFA durch die Potenzmengenkonstruktion
(erreichbare Zustände reichen aus).
d) Minimieren Sie den DFA (Rechenweg erforderlich (Tabelle)).
TCS | Wiederholung und Fragestunde | SoSe 2021 15/39
Beispielaufgabe zu endlichen Automaten
Gegeben sei der folgende NFA über Σ = {a, b}.
z0
z1z2 z3
a, b
a b
a
b
a) Welche Sprache erkennt der gezeigte NFA?
L = {a, b} ∪ {bia | i ≥ 0} ∪ {aib | i ≥ 0}
= {bia | i ≥ 0} ∪ {aib | i ≥ 0}
b) Geben Sie die Sprache durch einen regulären Ausdruck an.
L = L(α) mit α = a∗b|b∗a
TCS | Wiederholung und Fragestunde | SoSe 2021 16/39
Beispielaufgabe zu endlichen Automaten
Gegeben sei der folgende NFA über Σ = {a, b}.
z0
z1z2 z3
a, b
a b
a
b
z0, z1, z2
z1, z3
a
z2, z3
b
z1
a
z3
b
z2
b
a
b
a
a
b
∅
a, b
a, b
c) Erzeugen Sie einen äquivalenten DFA durch Potenzmengenkonstruktion (erreichbare
Zustände reichen aus)
TCS | Wiederholung und Fragestunde | SoSe 2021 17/39
Beispielaufgabe zu endlichen Automaten
Gegeben sei der folgende DFA über Σ = {a, b}.
z0, z1, z2
z1, z3
a
z2, z3
b
z1
a
z3
b
z2
b
a
b
a
a
b
∅
a, b
a, b
A
DB
G
C
E F
B ×1
C ×1 ×2
D ×1 ×2 ×2
E ×2 ×1 ×1 ×1
F ×2 ×1 ×1 ×1 ×2
G ×2 ×1 ×1 ×1 ×2 ×2
A B C D E F
Alle Paare nicht-äquivalent,
Automat war schon minimal!
d) Minimieren Sie den DFA (Rechenweg erforderlich (Tabelle)).
TCS | Wiederholung und Fragestunde | SoSe 2021 18/39
Beispielaufgabe zu Minimierung
Gegeben sei der folgende DFA über Σ = {a, b}.
A
B
C
D
E
F
G
H
a
b
b
a
a
a
b
a b
b
a
b
b
a
a, b
B ×2
C ×2 ×2
D ×1 ×1 ×1
E ×1 ×1 ×1 ×2
F ×1 ×1 ×1 ×2
G ×1 ×1 ×1 ×2 ×2
H ×3 ×2 ×2 ×1 ×1 ×1 ×1
A B C D E F G
Das Paar (D,G) und das Paar (E,F) sind äquivalent
Minimieren Sie den DFA (Rechenweg erforderlich (Tabelle)).
TCS | Wiederholung und Fragestunde | SoSe 2021 19/39
A
B
C
D
E
F
G
H
a
b
b
a
a
a
b
a b
b
a
b
b
a
a, b A
B
C
D,G
E,F
H
a
b
ba
a
b
a
b
a
b
a, b
TCS | Wiederholung und Fragestunde | SoSe 2021 20/39
Chomsky-Normalform berechnen
Sei G = (V,Σ, P, S) mit V = {S,A,B,C}, Σ = {a, b}
P = {S → CS | C,A→ a,B → b, C → ACA | B}
Berechne die Chomsky-Normalform:
1 Entfernen von ε-Produktionen: Gibt keine.
2 Entfernen von Einheitsproduktionen: Keine Zyklen, aber Einheitsproduktionen
(topologische Sortierung S < C) Setze B → b ein: S → CS | C,A→ a,B → b, C → ACA | b Setze C → ACA und C → b ein: S → CS | ACA | b, A→ a,B → b, C → ACA | b 3 Abkürzungen einf. (wir verwenden A→ a und B → b wieder): S → CS | ACA | b, A→ a,B → b, C → ACA | b 4 Rechte Seiten auf 2 Variablen kürzen: S → CS | AN1 | b, A→ a,B → b, C → AN2 | b, N1 → CA,N2 → CA TCS | Wiederholung und Fragestunde | SoSe 2021 21/39 CYK Sei G = (V,Σ, P, S) mit V = {S,A,B,C} Σ = {a, b} P = {S → CS | b, A→ a,B → b, C → AC | b} Führe den CYK-Algorithmus für aaaaab aus. Liegt das Wort in L(G)? a a a a a b 1 2 3 4 5 6 1 A A A A A B,C,S 2 C 3 C 4 C 5 C 6 C Da unten links nicht das Startsymbol S in der Tabelle steht, liegt das Wort nicht in L(G) TCS | Wiederholung und Fragestunde | SoSe 2021 22/39 CYK Sei G = (V,Σ, P, S) mit V = {S,A,B,C} Σ = {a, b} P = {S → CS | b, A→ a,B → b, C → AC | b} Führe den CYK-Algorithmus für aaaaabb aus. Liegt das Wort in L(G)? a a a a a b b 1 2 3 4 5 6 7 1 A A A A A B,C,S B,C,S 2 C S 3 C S 4 C S 5 C S 6 C S 7 S Da unten links das Startsymbol S in der Tabelle steht, liegt das Wort L(G) TCS | Wiederholung und Fragestunde | SoSe 2021 23/39 Klassiker: ” Beweisaufgaben“ Nichtregulärität einer Sprache zeigen mit Pumping-Lemma Nichtregulärität einer Sprache zeigen mit Satz von Myhill-Nerode Nicht-Kontextfreiheit einer Sprache zeigen mit Pumping-Lemma für CFLs Unentscheidbarkeit zeigen mit Reduktion Unentscheidbarkeit zeigen mit Satz von Rice NP-Vollständigkeit zeigen, u.a. mit Polynomialzeitreduktionen TCS | Wiederholung und Fragestunde | SoSe 2021 24/39 Nichtregulärität beweisen Aufgabe Zeige L = {aj$bj | j ∈ N} ist nicht-regulär. Mit dem Pumping-Lemma: Sei n > 0 beliebig.
Sei z = an$bn. Dann gilt |z| ≥ n und z ∈ L.
Sei z = uvw ein beliebige Zerlegung von z
mit |uv| ≤ n und |v| ≥ 1.
Damit muss gelten u = ai, v = aj , w = ak$bn mit i+ j + k = n und j ≥ 1.
Dann gilt uv0w = an−j$bn 6∈ L.
Somit erfüllt L die Pumping-Eigenschaft nicht und kann daher auch nicht regulär sein.
TCS | Wiederholung und Fragestunde | SoSe 2021 25/39
Nichtregulärität beweisen
Aufgabe
Zeige L = {aj$bj | j ∈ N} ist nicht-regulär durch Verwendung des Satzes von Myhill
und Nerode.
Nerode-Relation ∼L eine Sprache L:
u ∼L v ⇐⇒ ∀w ∈ Σ∗ : uw ∈ L ⇐⇒ vw ∈ L
Satz von Myhill-Nerode: Index(∼L) endlich g.d.w. L regulär.
Für die Aufgabe: Finde unendlich viele verschiedene Äquivalenzklassen
Es gilt [aj$]∼L 6= [a
i$]∼L für alle i 6= j:
für w = bi gilt ai$w ∈ L, aber aj$w 6∈ L
damit aj$ 6∼L ai$ für i 6= j.
Es gibt unendlich viele disjunkte Äquivalenzklassen bez. ∼L:
[a1$]∼L , [a
2$]∼L , [a
3$]∼L , . . .
Das zeigt: Index(∼L) = ∞. Mit Satz von Myhill-Nerode folgt: L nicht regulär.
TCS | Wiederholung und Fragestunde | SoSe 2021 26/39
Kontextfreiheit widerlegen
Aufgabe
Zeige L = {abiabiabiabi | i ∈ N} ist nicht kontextfrei.
Sei n > 0 beliebig.
Sei z = abn︸︷︷︸
r1
abn︸︷︷︸
r2
abn︸︷︷︸
r3
abn︸︷︷︸
r4
. Dann ist |z| ≥ n und z ∈ L.
Sei z = uvwxy eine beliebige Zerlegung mit |vwx| ≤ n und |vx| > 0
Dann kann vwx nur Teilwort von r1r2, r2r3 oder r3r4 sein.
Wenn v oder x ein a enthält, dann uv2wx2y 6∈ L, da es mehr als 4 a’s enthält
Wenn v und x kein a enthalten, dann ist uv0wx0y 6∈ L, da das Löschen von b’s in 1-2 der Teilworte
r1, r2, r3, r4 passiert. D.h. es gibt noch ab
n (mindestens 2) aber es gibt auch abj mit j < n Daher erfüllt L die Pumping-Eigenschaft für CLFs nicht. Das Pumping-Lemma für CFLs zeigt nun, dass L nicht kontextfrei ist. TCS | Wiederholung und Fragestunde | SoSe 2021 27/39 Kontextfreiheit widerlegen Aufgabe Zeigen Sie, dass H0 = {w | TM Mw hält bei leerer Eingabe} nicht kontextfrei ist. Pumping-Lemma? Braucht man nicht: H0 ist unentscheidbar Daher ist H0 nicht einmal von Typ 1 Daher ist H0 auch nicht von Typ 2. TCS | Wiederholung und Fragestunde | SoSe 2021 28/39 Unentscheidbarkeit zeigen Aufgabe Sei X = {w |Mw hält genau bei Eingabe x }. Zeigen Sie die Unentscheidbarkeit mithilfe einer Reduktion. Sei H0 = {w |Mw hält bei leerer Eingabe}. Aus der VL: H0 ist unentscheidbar. Wir zeigen H0 ≤ X: Die Reduktionsfunktion f nimmt eine Turingmaschinenbeschreibung und erstellt daraus eine neue Turingmaschinenbeschreibung. Sei w ein Wort. Wenn w keine Turingmaschinenbeschreibung ist, dann sei f(w) = w. Ansonsten sei Mw die Turingmaschine zu w. f erstellt daraus eine Turingmaschine T , sodass . . . TCS | Wiederholung und Fragestunde | SoSe 2021 29/39 Unentscheidbarkeit zeigen Aufgabe Sei X = {w |Mw hält genau bei Eingabe x }. Zeigen Sie die Unentscheidbarkeit mithilfe einer Reduktion. T prüft, ob die Eingabe x ist. Falls nicht, geht T in eine Endlosschleife. T löscht das Eingabeband. T simuliert Mw bei leerer Eingabe. Wenn Mw akzeptiert, dann akzeptiert T ansonsten läuft T endlos. Es gilt: w ∈ H0 g.d.w Mw hält bei leerer Eingabe g.d.w. T = Mf(w) hält bei Eingabe x g.d.w. f(w) ∈ X Da f total und berechenbar ist, gilt H0 ≤ X. TCS | Wiederholung und Fragestunde | SoSe 2021 30/39 Unentscheidbarkeit zeigen Aufgabe Sei X = {w |Mw hält genau bei Eingabe x }. Zeigen Sie die Unentscheidbarkeit mit dem Satz von Rice. Sei S = {f ∈ R | f(x) ist definiert, f(u) = ⊥ für u 6= x} Dann ist C(S) = {w |Mw berechnet eine Funktion aus S } = {Mw akzeptiert bei Eingabe x und hält nicht für andere Eingaben} Da S nicht-trivial ist (z.B. ist f1 ∈ S mit f1(x) = x, f1(u) = ⊥ für u 6= x, aber f2 6∈ S mit f2(u) = u und f2 ∈ R), folgt nach dem Satz von Rice, dass C(S) unentscheidbar ist. TCS | Wiederholung und Fragestunde | SoSe 2021 31/39 NP-Vollständigkeit zeigen Aufgabe Das EXACT-3-SAT Problem in gegeben/gefragt-Notation ist definiert durch gegeben: Aussagenlogische Formel F in Klauselform, so dass jede Klausel aus genau 3 (paarweise disjunkten) Literalen besteht. gefragt: Ist F erfüllbar? Zeige, dass EXACT-3-SAT NP-vollständig ist (verwende 3-CNF-SAT für die Reduktion) EXACT-3-SAT ∈ NP: Rate nichtdeterministisch die Belegung aller Variablen und verifiziere, ob die Belegung die Formel wahr macht, wenn ja akzeptiere, sonst verwerfe. Verifzieren geht in determ. Polynomialzeit, da man nur die Belegung für jedes Literal anwenden muss. TCS | Wiederholung und Fragestunde | SoSe 2021 32/39 NP-Vollständigkeit zeigen (2) NP-Schwere: Wir zeigen 3-CNF-SAT ≤p EXACT-3-SAT und verwenden, dass 3-CNF-SAT bereits als NP-vollständig bekannt ist. Für synt. falsche Eingaben erzeuge f eine synt. falsche Eingabe für EXACT-3-SAT. Für eine 3-CNF F = C1∧ . . .∧Cn erzeuge f eine 3-CNF C ′1∧ . . .∧C ′ n∧KM wobei C ′i=Ci, falls Ci=l1∨l2∨l3 C ′i=l1∨l2∨¬a, falls Ci=l1∨l2 C ′i=l1∨¬a∨¬b, falls Ci=l1 KM=(a∨c∨d)∧(a∨¬c∨d)∧(a∨c∨¬d)∧(a∨¬c∨¬d) ∧(b∨c∨d)∧(b∨¬c∨d)∧(b∨c∨¬d)∧(b∨¬c∨¬d) Dabei seien a, b, c, d neue Variablen, die nicht F -vorkommen. Es gilt: In f(F ) enthält jede Klausel genau 3 Literale. Jede Belegung die f(F ) wahr macht, muss a und b auf 1 setzen und daher auch F wahr machen. Jede Belegung die F wahr macht, kann erweitert werden (indem a und b auf 1 gesetzt werden), so dass f(F ) wahr ist. f(F ) ist in Polynomialzeit berechenbar und ist total. TCS | Wiederholung und Fragestunde | SoSe 2021 33/39 Weitere typische Aufgaben Sprachen angeben in einem der vielen Formalismen: DFA, NFA, regulärer Ausdruck, reguläre Grammatik Kontextfreie Grammatik, Kellerautomat, deterministischer Kellerautomat Turingmaschine angeben Formalismen ineinander überführen, z.B. regulärer Ausdruck in DFA usw. Programme schreiben als: Turingmaschine, WHILE-, LOOP-, GOTO-Programm, primitiv rekursive Funktion, µ-rekursive Funktion Sprachen ” typisieren“ in der Chomsky-Hierarchie TCS | Wiederholung und Fragestunde | SoSe 2021 34/39 LOOP-Programm Aufgabe Seien P,Q,R LOOP-Programme. Geben Sie ein LOOP-Programm an, dass folgende Funktion berechnet: jenachdem(x) = P,wenn x = 0 Q,wenn x = 1 R, sonst xP := 1; xQ := 2; xR := 1; LOOP x DO xP := xP − 1;xQ := xQ − 1 END; LOOP xP DO xQ := 0;xR := 0;P END; LOOP xQ DO xR := 0;Q END; LOOP xR DO R END TCS | Wiederholung und Fragestunde | SoSe 2021 35/39 Primitiv rekursive Funktionen Aufgabe Seien p, q, r primitiv rekursive Funktion. Geben Sie eine primitive rekursive Funktion an die folgende Funktion berechnet: jenachdem(x) = p(x),wenn x = 0 q(x),wenn x = 1 r(x), sonst Primitive Rekursion: Wenn g : Nk−1 → N und h : Nk+1 → N primitiv rekursiv, dann ist auch f mit f(x1, . . . , xk) = { g(x2, . . . , xk), wenn x1 = 0 h(f(x1 − 1, x2, . . . , xk), x1 − 1, x2, . . . , xk), sonst primitiv rekursiv. TCS | Wiederholung und Fragestunde | SoSe 2021 36/39 Primitiv rekursive Funktionen (2) Aufgabe Seien p, q, r primitiv rekursive Funktion. Geben Sie eine primitive rekursive Funktion an die folgende Funktion berechnet: jenachdem(x) = p(x),wenn x = 0 q(x),wenn x = 1 r(x), sonst Sei jenachdem(x) = f1(x) f1(x) = { g1() wenn x = 0 h1(f1(x− 1), x− 1) sonst g1 = p(0) h1(a, b) = f2(b) f2(x) = { g2() wenn x = 0 h2(f2(x− 1), x− 1) sonst g2 = q(1) h2(a, b) = r(succ(succ(b))) TCS | Wiederholung und Fragestunde | SoSe 2021 37/39 Turingmaschine Aufgabe Geben Sie eine DTM über Σ = {1, 2} an, die auf dem Eingabeband jede 1 durch eine 2 ersetzt und dann akzeptiert. Sei M = (Z,Σ,Γ, δ, z0,2, E) mit Z = {z0, z1} Σ = {1, 2} Γ = Σ ∪ {2} δ(z0, 2) = (z0, 2, R) δ(z0, 1) = (z0, 2, R) δ(z0,2) = (z1,2, N) E = {z1} TCS | Wiederholung und Fragestunde | SoSe 2021 38/39 Kellerautomat Aufgabe Geben Sie einen Kellerautomaten an, der {aiccbi | i ∈ N} erkennt. Sei K = (Z,Σ,Γ, δ, z0,#) mit Z = {z0, z1, z2} Σ = {a, b, c} Γ = {#, A} δ(z0, a,#) = {(z0, A#)} δ(z0, a, A) = {(z0, AA)} δ(z0, c,#) = {(z1,#)} δ(z0, c, A) = {(z1, A)} δ(z1, c,#) = {(z2,#)} δ(z1, c, A) = {(z2, A)} δ(z2, b, A) = {(z2, ε)} δ(z2, ε,#) = {(z2, ε, ε)} ¨ und δ(zi, x,X) = ∅ für alle anderen Fälle. TCS | Wiederholung und Fragestunde | SoSe 2021 39/39