Maximilian Krieg
Wissen, Technik & Erfahrungen
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
- Definitionen ( „Was ist ein DEA?“ )
- Gegeben: A = (Q, Σ, q0, δ, F) → Gesucht: Graph. Darstellung
- Gegeben: Graph. Darstellung → Gesucht: A = (Q, Σ, q0, δ, F)
- Gegeben: Sprache → Gesucht: Konstruiere A ( Konstruktionsprinzipien Produktautomat, komplementärer Automat )
- Gegeben: Automat → Gesucht: L(A)
- 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.
- für jede Eingabe terminiert ( immer etwas ausgeben )
- 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, Σ, q0, δ, 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 δ*(q0, 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}
- w0 = leer
- w1 = 0
- w2 = 1
- w3 = 00
- w4 = 01
- … usw.
- Ist A = (Q, Σ, q0, δ, F) ein DEA mit n0 = |Q| verschiedenen Zuständen. Dann gilt L(A) ≠ ε genau dann, wenn ein Wort der Länge höchstens n0-1 akzeptiert wird.
- Sei w ein Wort der Länge ≥ n0. 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, Σ, q0, δ, F)
- n0 = |Q|
- Σ‘ = { w ∈ Σ*; |w| = n0-1 }
- q = q0
- FOR ALL w ∈ Σ DO
- FOR i=1 TO n0-1 DO
- q = δ*(q0,w1..wi)
- IF q ∈ F THEN
- RETURN true
- END
- ENDIF
- END FOR
- END FOR
- END FOR ALL
- 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, Σ, 0, δ, F) und w ∈ Σ*
- Frage: Gilt w ∈ L(A)?
- Dieses Problem ist entscheidbar.
- Beweis:
- Algorithmus für das Wortproblem DEA.
- Eingabe A = (Q, Σ, q0, δ, F) und w ∈ Σ*
- q = δ*(q0,w) ↔ Wort in erweiterter Übergangsfunktion
- IF q ∈ F THEN ↔ Ist es ein Endzustand?
- Return true
- else Return false
- ENDIF
- Äquivalenzproblem
- Gegeben: Zwei formale Sprachen L1, L2
- Frage: Gilt L1 = L2?
- Satz 2.25 Äquivalenzproblem für DEAs
- Gegeben: Zwei DEAs
- A1 = (Q1, Σ, q1, d1, F1)
- A2 = (Q2, Σ, q2, d2, F2)
- Frage: Gilt L(A1) = L(A2)
- Dieses Problem ist entscheidbar.
- Wir reduzieren dieses Problem auf das Leerheitsproblem.
- Beweis:
- Für je zwei Mengen L1, L2 ⊆ Σ* gilt L1 = L2 ↔ (L1 ∩ ¬L2 ) ∪ (¬L1 ∩ L2 ) = ∅
- Entscheidbar mit dem Leerheitsproblem, wenn die Sprache (L1 ∩ ¬L2) ∪ (¬L1 ∩ L2 ) von einem DEA akzeptiert wird.
- Erst ¬L1 ∩ L2 beweisen
- Dann (L1 ∩ ¬L2 ) ∪ (¬L1 ∩ L2 ) beweisen
- Dadurch ist L1 = L2 bewiesen
- Satz 2.21 ( laut Skript )
- Werden L1, L2 von DEA akzeptiert, dann auch ¬L1, L1 ∩ L2 ( Produktautomat ), L1 ∪ L2
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.
- L = { an bn; n ∈ ℕ0 }
- L = { an bm; n ≠ m }
- Aber L = { an bm; n, m ∈ ℕ0 } 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= {an bn; n ∈ ℕ0 }
- 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 → a3 b3
- Definition 3.2 Grammatik
- Eine Grammatik ist von der Form G = (N, Σ, P, S), wobei:
- N und Σ endliche Alphabete mit Σ n N = ∅ sind (disjunkt )
- Die Elemente von N heißen Nichtterminalsymbole
- Die Elemente von Σ heißen Terminalsymbole
- S ∈ N das Startsymbol ist,
- P ⊆ ( N u Σ )+ x ( N u Σ)* eine endliche Menge von Ersetzungsregeln ( Produktionen )
- Σ* { w = w1 … wn, n ∈ ℕ mit wi ∈ Σ für alle i<= n } u { ε}
- ( N u Σ )*
- ( N u Σ )+ = ( N u leer )* \ { ε}
- N und Σ endliche Alphabete mit Σ n N = ∅ sind (disjunkt )
- Eine Grammatik ist von der Form G = (N, Σ, P, S), wobei:
- (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 an bn
- 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 } = { an bn cn, 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 x1, x2 ∈ ( N u Σ)* und eine Produktion u → v ∈ P mit x = x1 u x2 und y = x1 v x2 existiert
- a S B c ⱵG a a b c B c
- x1 u x2 ⱵG x1 v x2 // somit wird u → v
- y ist aus x in n ∈ ℕ Schritten ableitbar ( x ⱵGn y ), wenn x0, x1, .., xn ∈ ( N u Σ )* so existieren, dass x=x0, xn=y und xi ⱵG xi+1 für alle 0 ≤ i ≤ n
- y ist aus x ableitbar ( x ⱵG* y ), wenn n ∈ ℕ mit x ⱵGn 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
- S ⱵG abc ( Weil abc ∈ Σ* gilt abc ∈ L(G) )
- S Ⱶ_G aSBc ( ∈ L(G)? → nein, weil S und B ∉ Σ* ) ⱵG aaabcBcBc ⱵG aaabBccBc ⱵG2 aaabbBccc ⱵG aaabbBccc ⱵG aaabbbccc = a3 b3 c3
- Wir zeigen: Für alle n ∈ ℕ gilt S ⱵG* an bn cn
- Für n=1 gilt S ⱵG* a1 b1 c1
- Sei n > 1:
- S ⱵGn-1 an-1 S ( Bc)n-1 … .. ⱵG an-1 abc (Bc)n-1 .. .. ⱵG* an b Bn-1 cn .. .. ⱵG* an bn cn
- ( 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 { an bn cn; n ∈ ℕ } ⊆ L(G) Wir haben nicht gezeigt L(G) ⊆ { an bn cn; n ∈ ℕ }
