Chomsky-Normalform t1n tik K=1 k=2 K=3 k=4 i = 1 A Ø Ø S (t14 = t1n) i =2 A S C – i =3 B…
Aufgabe 1 Sei Σ = {0,1} ein Alphabet und L = { w ∈ Σ, w ist ein palindrom}.Geben Sie eine Grammatik für L an. S → 0S0…
Tipp vom Prof: Aufgabe 1 kommt nicht in der Klausur dran… –> Sollte nochmal nachgefragt werden, um sicher zu gehen… Aufgabe 2 konstruieren Sie einen DEA…
3. Grammatiken 3.1 Chomsky-Hierarchie Grammatik Automaten/Maschinen ℒ0 Turingmaschinen ℒ1 Linear beschränkte Automaten ( beschränkte Turingmaschinen) ℒ2 Kellerautomaten (DEA mit zusätzlichem Speicher) ℒ3 DEA 3.2 Grammatiken…
Organisatorisches Klausur 2.4 Das Leerheits-, Wort- und das Äquivalenzproblem 3. Grammatiken
Wortproblem: Wiederholungsaufgabe Aufgabe 1.1 Aufgabe 1.2 Wiederholung Aufgabe 2
2.3) Pumping-Lemma ε (leeres Wort) 0 1 1 0 0 0 q0 q1 q1 q1 q2 q1 q2 ∈ F ( w = aa…ab …..b…
2. Endliche Automaten und reguläre Sprachen Allgemein 2.2 Minimierungsalgorithmus
Ziele Aufgabe 1 Aufgabe 2 Äquivalenzrelationen Aufgabe 3 Äquivalenzrelationen Hiermit haben wir bewiesen, dass die definierte Relation eine Äquivalenzrelation ist. Äquivalenzklasse
1.2 Zwei Beispiele Optimierungsproblem Clique Entscheidungsproblem Clique Optimierungsproblem Saturability ( Sat ) Entscheidungsproblem Saturability ( Sat ) 1.3 Optimierungs-, Entscheidungs- und Wortprobleme und formale Sprachen…