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 über Σ = {0,1} für
L1 = {w ∈ Σ*; w hat Präfix 01}
L2 = {w ∈ Σ*; w hat Suffix 10}
L1
A = (Q, Σ, q0, d, F)
d: Q x Σ → Q
d(q0, 0) = q1
d(q0, 1) = q3
L(A) = {w ∈ Σ*; d*(q0, w) ∈ F}
L2
Einschub (Zum festigen des Stoffes)
Entwickeln sie einen DEA für Präfix 00 und einen DEA für Suffix 00
Aufgabe 3 (stark klausurrelevant)
Konstruieren Sie einen DEA für die Sprache L = { w ∈ Σ*; w hat Präfix 01 und Suffix 10} mittels Produktautomat L = L1 ∧ L2
A1 = (Q, Σ, q0, d1, F1)
A2 = (Z, Σ, z0, d2, F2)
Produktautomat (Definition / Erinnerung)
A = (Q x Z, Σ, (q0, z0), d, F1 x F2)
- Q x Z = {(q,z) ; q ∈ Q, z ∈ Z}
- d: (Q x Z) x Σ → Q x Z; ((q, z), a) → (d1(q, a), d2(z, a))
weiter mit A3…
Aufgabe 4
Konstruieren Sie einen DEA für L1 = {w ∈ {0,1}* ; w enthält nicht das Teilwort 11}
L2 = {w ∈ {0,1}*; |w| > 0}
A = (Q, Σ, q0, d, F) mit L(A) = L
¬L = Σ*\L ¬A = (Q, Σ, q0, d, ¬F) ist ein DEA für ¬L
Automat für
¬L1 = {w ∈ {0,1}*; w enthält das Teilwort 11} → Komplementautomat