Theoretische Informatik (Vorlesung 5)

 2. Endliche Automaten und reguläre Sprachen

• A = ( Q, Σ, q₀, δ, F )
  • Q = Zustandsmenge
  • Σ = Alphabet
  • q₀ = Anfangszustand
  • δ = Übergangsfunktion
  • F = Endzustände
• Beispiel: Endlichen Automat
  • Q = { q₀, q₁, q₂ }, Σ = { 0,1 }, q₀ Anfangszustand, Endzustand F = {q₂}
  • δ: Q x Σ → Q
  • δ ( q₀, 0 ) = q₁
  • δ ( q₀, 1 ) = q₀
  • δ ( q₁, 0 ) = q₀
  • δ ( q₁,1 ) = q₁
  • δ ( q₂,0 ) = q₁
  • δ ( q₂, 1 ) = q₂

Allgemein

• ( . ) = Anfangszustand
• (   ) = Zustände
• ((  )) = Endzustände
• Für q‘ = d(q,x) kann man auch schreiben:

• Für uns interessant: Nutzung von PEAS für das Wortproblem
• Definition 2.2 ( Erweiterte Übergangsfunktion)
  • Sei A = (Q, Σ, q₀, δ, F) ein DEA.
  • Die erweiterte Übergangsfunktion: δ* : Q x Σ* (Wort) → Q wird iterativ wie folgt definiert:
    • 1. δ*(q,Σ) = q
    • 2. δ*(q, a)=δ(q, a) für alle a ∈ Σ
    • 3. δ*(q,w) = δ* ( δ( q,x ),w‘ ) mit w = x w‘ und w = Σ*, x ∈ Σ
• Beispiel:
  • δ*( q₀, 100110 )  
  • = δ* ( q₀,  00110 )
  • = δ* ( δ ( q₀, 0)  0110 )  
  • = δ* ( δ ( q₁, 0)  110 )  
  • = δ* ( δ ( q₂, 1)  10 )  
  • = δ* ( δ ( q₂, 1)  0 )  
  • = δ* ( δ ( q₂, 0)  Σ ) 
  • = δ* (q₁, Σ ) = q₁
  • δ*( q₀, 100110 ) = q₁
• Def 2.3 Akzeptierte Sprache
  • Sei A = ( Q, Σ, q₀, δ, F) ein DEA, dann heißt L(A) = { w ∈ Σ*, δ*(q,w) ∈ F } die von A akzeptierte Sprache.
  • L(A) = { w ∈ { 0,1 }*, die Anzahl der Nullen ist gerade und ungleich 0.
• Beispiel:
  • Ein DEA für die Sprache L = { w ∈ {0,1}*, w ist eine Binärdarstellung einer durch 3 teilbaren Zahl }
  • Für ein Wort w = w_n … w₁ ∈  { 0,1 }* sei nat(w) = ∑(i=1 bis n) z^(i-1)*w_i
• Wir setzen weiter:
  • nat(Σ)=0 ( Leere Menge )
  • nat (1 0 1 1 ) = ∑ (i=1 bis 4) = 2⁰ * 1+2¹ * 1+2² * 0+2³ * 1 ( Es sind dabei w4, w3, w2, w1 )
  • Für eine natürliche Zahl n ∈ ℕ gilt:
  • n mod 3 = {0,1,2}  ( 0 = Durch drei teilbar )
• Für DEAs ist das Wortproblem lösbar:Gegeben: Eine durch 3 teilbare Zahl, z.B.:
  • 11 = 3
  • 110 = 6 // hat (w0) = 2nat(w)
  • 111 = 7 // hat (w1) = 2nat(w)+1

• Gegeben: Ein DEA A und ein Wort w.
• Frage: Gilt w ∈ L(A)
• Definition 2.4
  • Sei A ein DEA, für jedes Wort aus w ∈ Σ* kann in |w| Schritten geprüft werden ( |w| = Länge von w ), ob w ∈ L(A)
  • Beweis: Berechne δ*(q₀,w) Diese Berechnung erfordert |w| Schritte, dann gilt:
  • 1) Ist δ*(q₀, w) ∈ F, so ist  w ∈ L(A)
  • 2) sonst nicht

2.2 Minimierungsalgorithmus

• Definition 2.5: 
  • Zwei DEA A und A‘ heißen äquivalent, wenn L(A) = L(A‘)
  • Zwei Automaten erzeugen die gleiche Sprache, sind aber anders aufgebaut
• Beispiel 1:
• Beispiel 2:Die Sprache L(A) lautet wie folgt:
  • L(A)=(a+ba)* bb (a+b)*
  • L(A) = { w ∈ {a,b}, w enthält das Teilwort bb}
  • L(A, q₀) = L(A)
  • L(A, q₁) = L(A) u {bw, w ∈ Σ*}
  • L(A,q₂) = {a,b}*
  • Es gibt keine äquivalenten Zustände ( nichts zu kürzen)
• 
  Wie konstruiert man einen minimalen DEA für eine Sprache. ( Minimal in der Anzahl der Zustände )Die Sprache L(A‘) lautet ebenso:
  • L(A‘) = (a+ba)*bb(a+b)*
  • A und A‘ sind somit äquivalent.

• Erste Beobachtung: q₇ kann vom Anfangszustand q₀ nicht erreicht werden und kann somit gestrichen werden
• Zweite Beobachtung: Für alle w ∈ {a,b}* gilt δ*(q₃,w) ∈ F und δ* (q₅, w) ∈ F. Wir können also die Zustände geeignet zusammenfassen, ohne dass sich an der akzeptierten Sprache etwas ändert. 

• L(A, q₃) = {a,b}*
• L(A, q₅) = {a,b}*
• d.h. q₃ ~ q₅ ( Äquivalenz ist gegeben! )

• Definition 2.6:
  • Sei A = (Q, Σ, q₀, δ, F) ein DEA. Ein Zustand heißt erreichbar, falls ein Wort w ∈ Σ* mit δ* (q₀, w ) = q existiert. Sonst heißt q nicht erreichbar.
• Definition 2.7:
  • Sei A = (Q, Σ, q₀, δ, F) ein DEA. Zwei Zustände heißen äquivalent (q₁~q₂), wenn L(A, q₁) = L(A,q₂), dabei ist L(A,q) = {w ∈ Σ*; δ(q,w) ∈ F} (d.h. die von A akzeptierte Sprache, wenn q der Anfangszustand wäre)
• Definition 2.8:
  1. Es gilt ~ ist eine Äquivalenzrelation, d.h.
     1. reflexiv ( d.h. q ~ q für alle q ∈ Q )
     2. symmetrisch ( d.h. aus  q₁ ~ q₂ → q₂ ~ q₁)
     3. transitiv ( d.h. aus q₁ ~ q₂ und q₂ ~ q₃ → q₁ ~ q₃)
  2. ~ ( die Relation) ist verträglich  mit der Übergangsfunktion, d.h. ist q₁ ~ q₂ ↔ d (q₁, a) ~ d(q₂, a) für alle a ∈ Σ.
• Beweis: 
  • 1A) Wegen L(A, q) = L(A, q) gilt q ~ q.
  • 1B) Ist q₁ ~ q₂, dann gilt L(A, q₁) = L(A, q₂), also q₂ ~ q₁
  • 1C) Ist q₁~q₂ und q₂~q₃, dann gilt L(A,q₁)  = L(A, q₂) = L(A,q₃). Insbesondere gilt also L(A, q₁) = L(A,q₃), d.h. q₁~q₃.
  • 2) Es gilt nämlich q₁ ~ q₂ ↔ L(A,q₁) = L(A,q₂) ↔ ∀ w ∈ Σ* : δ*(q₁,w) ∈ F ↔ δ*(q₂, w) ∈ F ↔ ∀ a ∈ Σ ∀ v ∈ Σ* : [ d* (δ(q₁, a),v) ∈ F  ↔ δ*(δ(q₂, a), v) ∈ F] ( setze einfach w=av; v = Wort; a= Buchstabe ) ↔ ∀ a ∈ Σ : L(A,δ(q₁,a))=L(A,δ(q₂,a)) ↔ δ(q₁,a) ~ δ(q₂,a)
• Definition 2.9 Quotientenautomat
  • Sei A = (Q, Σ, q₀, δ, F) ein DEA.
  • Der Quotientenautomat A^~ = ( Q^~, E, q^~, d^~, F^~) mit
    1.  Q^~ = {q~, q ∈ Q } wobei q^~ = { q‘ ∈ Q; q ~ q‘ }
    2. d^~(q^~,a) = d~~~(q,a)
    3. F^~ = {q^~, q ∈ F }
  • q~ = { q‘ ∈ Q; q ~ q‘ } ( Die Äquivalenzklasse von q ) ( q₀^~ = Äquivalenzklasse von q₀ → für / mit allen Elementen aus q₀ )
  • q₀^~ = { q₀ }
  • q₁^~ = { q₁ }
  • q₂^~ = { q₂ }