Chomsky-Normalform t1n tik K=1 k=2 K=3 k=4 i = 1 A Ø…

Aufgabe 1 Sei Σ = {0,1} ein Alphabet und L = { w ∈ Σ,…

Tipp vom Prof: Aufgabe 1 kommt nicht in der Klausur dran… –> Sollte…

3. Grammatiken 3.1 Chomsky-Hierarchie Grammatik Automaten/Maschinen ℒ0 Turingmaschinen ℒ1 Linear beschränkte Automaten…

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  …

 2. Endliche Automaten und reguläre Sprachen Allgemein 2.2 Minimierungsalgorithmus

Ziele Aufgabe 1 Aufgabe 2 Äquivalenzrelationen Aufgabe 3 Äquivalenzrelationen Hiermit haben wir bewiesen,…

1.2 Zwei Beispiele Optimierungsproblem Clique Entscheidungsproblem Clique Optimierungsproblem Saturability ( Sat )…