Theoretische Informatik (Vorlesung 8)

Organisatorisches

• Skript wurde online gestellt
• Skript hält sich weitestgehend an die Vorlesung
• Beweise z.B. stehen im Skript genauer
• Notation ( Index ) wird nun vom Skript genommen

Klausur

1. Definitionen ( „Was ist ein DEA?“ )
2. Gegeben: A = (Q, Σ, q₀, δ, F) → Gesucht: Graph. Darstellung
3. Gegeben: Graph. Darstellung → Gesucht: A = (Q, Σ, q₀, δ, F)
4. Gegeben: Sprache → Gesucht: Konstruiere A ( Konstruktionsprinzipien Produktautomat, komplementärer Automat )
5. Gegeben: Automat → Gesucht: L(A)
6. Gegeben: Sprache → Gesucht: Warum wird diese Sprache nicht von einem DEA akzeptiert?

2.4 Das Leerheits-, Wort- und das Äquivalenzproblem

• Ein Problem heißt Entscheidbar, wenn es einen Algorithmus (z.B.: Computerprogramm) gibt, der das Problem löst, d.h.
  1. für jede Eingabe terminiert ( immer etwas ausgeben )
  2. die richtige Antwort liefert.
• Für durch DEA gegebene Sprachen sind alle drei Probleme entscheidbar.
• Leerheitsproblem:
  • Gegeben: Eine formale Sprache L.
  • Frage: Gilt L ≠ ε?
• Satz 2.23 Leerheitsproblem für DEAs
  • Gegeben: Ein DEA A = (Q, Σ, q₀, δ, F)
  • Frage: Gilt L(A) ≠ ε?
  • Dieses Problem ist entscheidbar.
• Beweis: 
  • Offensichtlich gilt L(A) ≠ ε genau dann, wenn w ∈ L(A) existiert.

• Erste Idee: Der gesuchte Algorithmus überprüft für verschiedene Wörter w ∈ Σ*, ob w ∈ L(A) gilt (d.h. er berechnet δ*(q₀, w) ∈ F?).
• Wenn der Algorithmus terminiert, hat er ein Wort w ∈ L(A) gefunden, aber der Algorithmus terminiert nicht, wenn L(A) = ∅ gilt.
• Bsp.: Für Σ = {0,1}
  • w₀ = leer
  • w₁ = 0
  • w₂ = 1
  • w₃ = 00
  • w₄ = 01
  • … usw.
• Ist A = (Q, Σ, q₀, δ, F) ein DEA mit n₀ = |Q| verschiedenen Zuständen. Dann gilt L(A) ≠ ε genau dann, wenn ein Wort der Länge höchstens n₀-1 akzeptiert wird.
  • Sei w ein Wort der Länge ≥ n₀. Dann gilt: Der Automat besucht beim Lesen des Wortes mindestens einen Zustand mehrmals.
  • graph_1
  • 01 ∈ L(A)
• Allgemein für das Leerheitsproblem:
  • Eingabe: A=(Q, Σ, q₀, δ, F)
  1. n₀ = |Q|
  2.   Σ‘ = { w ∈ Σ*; |w| = n₀-1 }
  3.   q = q₀
  4.   FOR ALL w ∈ Σ DO
  5.     FOR i=1 TO n₀-1 DO
  6.       q = δ*(q₀,w₁..w_i)
  7.       IF q ∈ F THEN
  8.         RETURN true
  9.         END
  10.       ENDIF
  11.   END FOR
  12. END FOR
  13. END FOR ALL
  14. RETURN false
• Wortproblem
  • Gegeben: Eine formale Sprache L und ein Wort w.
  • Frage: Gilt w ∈ L?
• Satz 2.24. Wortproblem für DEAs
  • Gegeben: Ein DEA A = (Q, Σ, ₀, δ, F) und w ∈ Σ*
  • Frage: Gilt w ∈ L(A)?
  • Dieses Problem ist entscheidbar.
• Beweis: 
  • Algorithmus für das Wortproblem DEA.
  • Eingabe A = (Q, Σ, q₀, δ, F) und w ∈ Σ*
    1. q = δ*(q₀,w) ↔ Wort in erweiterter Übergangsfunktion
    2. IF q ∈ F THEN  ↔ Ist es ein Endzustand?
    3. Return true
    4. else  Return false
    5. ENDIF
• Äquivalenzproblem
  • Gegeben: Zwei formale Sprachen L₁, L₂
  • Frage: Gilt L₁ = L₂?
• Satz 2.25 Äquivalenzproblem für DEAs
  • Gegeben: Zwei DEAs
  • A1 = (Q₁, Σ, q₁, d₁, F₁)
  • A2 = (Q₂, Σ, q₂, d₂, F₂)
  • Frage: Gilt L(A₁) = L(A₂)
  • Dieses Problem ist entscheidbar.
  • Wir reduzieren dieses Problem auf das Leerheitsproblem.
• Beweis:
  • Für je zwei Mengen L₁, L₂ ⊆ Σ* gilt L₁ = L₂ ↔ (L₁ ∩ ¬L₂ ) ∪ (¬L₁ ∩ L₂ ) = ∅
  • Entscheidbar mit dem Leerheitsproblem, wenn die Sprache (L₁ ∩ ¬L₂) ∪ (¬L₁ ∩ L₂ ) von einem DEA akzeptiert wird.
    1. Erst ¬L₁ ∩ L₂ beweisen
    2. Dann (L₁ ∩ ¬L₂ ) ∪ (¬L₁ ∩ L₂ ) beweisen
    3. Dadurch ist L₁ = L₂ bewiesen
• Satz 2.21 ( laut Skript )
  • Werden L₁, L₂ von DEA akzeptiert, dann auch ¬L₁, L₁ ∩ L₂ ( Produktautomat ), L₁ ∪ L₂

3. Grammatiken

• Grammatiken werden genutzt, um Wörter zu erzeugen. Hierzu werden Regeln benutzt, die es erlauben ein Wort aus einem anderen Wort abzuleiten.
• Es gibt eine Reihe von Sprachen, die nicht von DEAs akzeptiert werden.
  1. L = { aⁿ bⁿ; n ∈ ℕ₀ }
  2. L = { aⁿ b^m; n ≠ m }
  3. Aber L = { aⁿ b^m; n, m ∈ ℕ₀ } wird von einem DEA akzeptiert. Der Begriff / das Berechnungsmodell DEA ist nicht besonders mächtig.
• Beispiel 3.1: Eine Grammatik für die Sprache L= {aⁿ bⁿ; n ∈ ℕ₀ }
  • S → a S b
  • S → ε
  • S → a S b → a a S b b → a a a S b b b → a a a ε b b b → a³ b³
• Definition 3.2 Grammatik
  • Eine Grammatik ist von der Form G = (N, Σ, P, S), wobei:
    1. N und Σ endliche Alphabete mit Σ n N = ∅ sind (disjunkt )
       • Die Elemente von N heißen Nichtterminalsymbole
       • Die Elemente von Σ heißen Terminalsymbole
    2. S ∈ N das Startsymbol ist,
    3. P ⊆ ( N u Σ )⁺  x ( N u Σ)^* eine endliche Menge von Ersetzungsregeln ( Produktionen )
    • Σ* { w = w₁ … w_n, n ∈ ℕ mit w_i ∈ Σ für alle i<= n } u { ε}
    • ( N u Σ )^*
    • ( N u Σ )⁺ = ( N u leer )* \ { ε}
• (u,v) ∈ P schreiben wir auch u → v
• Beispiel 3.3:
  • N = {S}, Σ = {a,b}, P = { S → a S b, S → ε }
  • Startsymbol S
  • Sprache ist somit aⁿ bⁿ
• Weiteres Beispiel
  • G = ( N, Σ, P, S )
  • N = {S,B}
  • E = {a,b,c}
  • Produktionen P = {
    • S → a S B c,
    • S → a b c,
    • cB → Bc,
    • bB → bb } = { aⁿ bⁿ cⁿ, n ∈ ℕ }
• Defintion 3.4:
  • Sei G = ( N, Σ, P, S ) eine Grammatik und x,y ∈ ( N u Σ )
  • y ist aus x direkt ableitbar ( x Ⱶ_G y ) wenn x₁, x₂ ∈ ( N u Σ)* und eine Produktion u → v ∈ P mit x = x₁ u x₂ und y = x₁ v x₂ existiert
    • a  S  B c Ⱶ_G a  a b c B c
  • x₁ u x2   Ⱶ_G  x₁    v    x2  // somit wird u → v
  • y ist aus x in n ∈ ℕ Schritten ableitbar ( x Ⱶ_Gⁿ y ), wenn x₀, x₁, .., x_n ∈ ( N u Σ )* so existieren, dass x=x₀, x_n=y und x_i Ⱶ_G x_i+1 für alle 0 ≤ i ≤ n
  • y ist aus x ableitbar ( x Ⱶ_G^* y ), wenn n ∈ ℕ mit x Ⱶ_Gⁿ y existiert.
  • Die Sprache L(G) = { w ∈ Σ*; S Ⱶ_G^* } heißt die von G erzeugte Sprache.
  • Wir sind nur an Σ* Wörtern aus S interessiert.
• Beispiel 3.5
  1. S Ⱶ_G abc ( Weil abc ∈ Σ* gilt abc ∈ L(G) )
  2. S Ⱶ_G aSBc ( ∈ L(G)? → nein, weil S und B ∉ Σ* ) Ⱶ_G aaabcBcBc Ⱶ_G aaabBccBc Ⱶ_G² aaabbBccc Ⱶ_G aaabbBccc Ⱶ_G aaabbbccc = a³ b³ c³
• Wir zeigen: Für alle n ∈ ℕ gilt S Ⱶ_G^* aⁿ bⁿ cⁿ
  1. Für n=1 gilt S Ⱶ_G^* a¹ b¹ c¹
  2. Sei n > 1:
     • S  Ⱶ_G^n-1 a^n-1 S ( Bc)^{n-1 …} .. Ⱶ_G a^n-1 abc (Bc)^{n-1 ..} .. Ⱶ_G^* aⁿ b B^n-1 c^{n ..} .. Ⱶ_G^* aⁿ bⁿ cⁿ
• ( Wiederholtes Anwenden der Produktion S → aSBc ) ( Einmalige Anwendung der Regel S → abc ) ( Wiederholtes Anwenden von cB → Bc ) ( Wiederholte Anwendung von bB → bb ) 
• Wir haben gezeigt { aⁿ bⁿ cⁿ; n ∈ ℕ } ⊆ L(G) Wir haben nicht gezeigt L(G) ⊆ { aⁿ bⁿ cⁿ; n ∈ ℕ }