Theoretische Informatik (Vorlesung 7)

Wortproblem: 

• geg: Eine Sprache L und ein Wort W
• Frage: Gilt w ∈ L?

Wiederholungsaufgabe

• L = { 001w; w ∈ {0,1}* } ← Klausurrelevant Alle Wörter über dem Alphabet Σ = {0,1} mit dem Präfix 001.
• Dies ist kein DEA, weil wenn δ*(q₀, 1100) eingegeben wird. Es muss für jeden Buchstaben eine Übergangsfunktion in jeden Zustand geben. Nicht deterministische Automaten können z.B. für den selben Buchstaben zwei Ziele haben. δ(q₀,1) → q₀ oder q₁
• Begründung
  • L(A) = { w ∈ Σ*; δ* (q₀, w ) ∈ F }
  • A = ( Q, Σ, q₀, δ, F )
  • δ: QxΣ → Q (totale Funktion, d.h. δ(q,a) ist definiert für alle Paare (q,a) ∈ QxΣ.
  • δ(q₀, 0) = q₁
  • δ(q₀,1) = ?? ← Zustandswechsel fehlt
• Lösung

• Erzeugung eines Zustands zur Aufnahme eines fehlenden Zustandswechsel, sog. Papierkorb-Zustand ← Klausurrelevant
• Dauerschleife mit vollständigem Alphabet verhindert, dass man jemals in einen Endzustand kommt
• Durch den Papierkorb-Zustand wird keine neue gültige Sprache erzeugt

Aufgabe 1.1

• DEA A = ( Q, Σ, q₀, δ, F)
• Q = {q₀,q₁,q₂}, Σ = {0,1}, Anfangszustand q₀, F= {q₀}
• Übergangsfunktionen
  • δ(q₀,0) = q₀
  • δ(q₀,1) = q₁
  • δ(q₁,0) = q₂
  • δ(q₁,1) = q₀
  • δ(q₂,0) = q₁
  • δ(q₂,1) = q₁
• Welche Worte sind teil der Sprache?
  • w₁ = 101
  • w₂ = 111
  • w₃ = 110
  • δ*(q₀,101) = q₂  ( falsch )
  • δ*(q₀, 111) = q₁ ( falsch )
  • δ*(q₀, 110 ) = q₀ ( wahr )
• Was ist die akzeptierte Sprache?
  • Durch drei teilbare Zahlen ( binär )

Aufgabe 1.2

• Bestimme:
  • Q = {q₀,q₁,q₂}
  • Σ = {a,b}
  • q₀ = q₀
  • F = {q₀,q₁}
  • δ = …
    • δ(q₀,a) = q₁
    • δ(q₀,b) = q₀
    • δ(q₁,a) = q₁
    • δ(q₁,b) = q₂
    • δ(q₂,a) = q₂
    • δ(q₂,b) = q₂
• Welche Sprache wird akzeptiert?
  • L(A) = { bⁿ a^m; n,m ∈ N0 }
  • b⁰ a^m = a^m
  • bⁿ a⁰ = bⁿ
  • b⁰ a⁰ = leeres Wort // δ(q₀, leer ) = q₀ → q₀ ∈ F

Wiederholung

• L(A) = ( w ∈ Σ*; δ*(q₀,w) ∈ F }
• δ*(q, ε ) = q ← „Wer nichts liest, bleibt wo er ist“

Aufgabe 2

• Konstruktion eines DEAs über Σ = {0,1}, der die Sprache L₁ = { w ∈ {0,1}*; w hat eine gerade Anzahl von Einsen } akzeptiert.
• L‘ = { w ∈ {0,1}*; w hat eine gerade Anzahl von Einsen und mindestens eine Eins }
• Konstruktion eines DEAS über Σ = {0,1}, der die Sprache L₂ = { w ∈ {0,1}*; w hat eine gerade Anzahl von Nullen} akzeptiert.
• Ein Automat für L₁ ∩ L₂ = { w ∈ {0,1}*; w hat gerade viele Einsen und gerade viele Nullen }