Theoretische Informatik (Vorlesung 7)

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

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

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 }