close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

3.0 VU Formale Modellierung Was Sie letzte Woche hörten

EinbettenHerunterladen
Was Sie letzte Woche hörten
3.0 VU Formale Modellierung
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Gernot Salzer
20.3.2012
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
1
Äquivalenz, Konsequenz und Gültigkeit
2
Was Sie letzte Woche hörten
Semantische Äquivalenz
Zwei Formeln F und G heißen äquivalent, geschrieben F = G,
wenn valI (F ) = valI (G) für alle Interpretationen I gilt.
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
F = G gilt genau dann, wenn F ≡ G eine gültige Formel ist.
B, and, or, not, 0, 1 ist eine Boolesche Algebra.
F1 , . . . , Fn |=I G: „Aus valI (F1 ) = · · · = valI (Fn ) = 1 folgt valI (G) = 1.“
Logische Konsequenz
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Die Formel G folgt aus den Formeln F1 , . . . , Fn , geschrieben
F1 , . . . , Fn |= G, wenn F1 , . . . , Fn |=I G für alle Interpretationen I gilt.
F1 , . . . , Fn |= G gilt genau dann, wenn (F1 ∧ · · · ∧ Fn ) ⊃ G gültig ist.
3
4
Von der Funktion zur Formel
Was Sie letzte Woche hörten
Gegeben: Funktion f : Bn → B (z.B. als Wahrheitstafel)
Gesucht: Formel, die f darstellt
A1 A2 A3
Db
b
f (b)
Kb
1
1
1
1 A1 ∧ A2 ∧ A3 =: K111
1
1
0
0
¬A1 ∨ ¬A2 ∨ A3
0
1
0
1
¬A1 ∨ A2 ∨ ¬A3
1
0
0
1 A1 ∧ ¬A2 ∧ ¬A3 =: K100
0
1
1
1 ¬A1 ∧ A2 ∧ A3 =: K011
0
1
0
0
A1 ∨ ¬A2 ∨ A3
0
0
1
0
A1 ∨ A2 ∨ ¬A3
0
0
0
0
A1 ∨ A2 ∨ A3
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
=: D110
=: D101
=: D010
=: D001
=: D000
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
DNFf = K111 ∨ K100 ∨ K011
KNFf = D110 ∧ D101 ∧ D010 ∧ D001 ∧ D000
6
5
Normalformen
Konstruktion von DNFs/KNFs – Semantische Methode
Literal: Variable oder negierte Variable, also A, ¬A, B, ¬B, . . .
Gegeben: Aussagenlogische Formel F
Gesucht: Äquivalente Formel in DNF/KNF
Negationsnormalform (NNF)
Literale sowie
und ⊥ sind in NNF.
(F ∧ G) und (F ∨ G) sind in NNF, wenn F und G in NNF sind.
Keine Formel sonst ist in NNF.
1
Stelle die zu F gehörige Funktion f als Wahrheitstafel dar.
2
Konstruiere DNFf bzw. KNFf .
A1 A2 A3 F := (A1 ⊃ (A2 ≡ A3 )) ∧ (¬A1 ⊃ (A2 ∧ A3 ))
Disjunktive Normalform (DNF)
1
1
1
1
0
0
0
0
, ⊥ sowie Disjunktionen von Konjunktion von Literalen:
((¬)A1,1 ∧ (¬)A1,2 ∧ (¬)A1,3 ∧ · · · ) ∨ ((¬)A2,1 ∧ (¬)A2,2 ∧ (¬)A2,3 ∧ · · · ) ∨ · · ·
Konjunktive Normalform (KNF)
, ⊥ sowie Konjunktionen von Disjunktion von Literalen:
( A1,1 ∨ (¬)A1,2 ∨ (¬)A1,3 ∨ · · · ) ∧ ((¬)A2,1 ∨ (¬)A2,2 ∨ (¬)A2,3 ∨ · · · ) ∧ · · ·
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
0
K111
K100
K011
D110
D101
D010
D001
D000
DNF: F = K111 ∨ K100 ∨ K011
KNF: F = D110 ∧ D101 ∧ D010 ∧ D001 ∧ D000
(¬)
7
8
Konstruktion von DNFs/KNFs – Algebraische Methode
Was Sie letzte Woche hörten
Gegeben: Aussagenlogische Formel F
Gesucht: Äquivalente Formel in DNF/KNF
1
2
Ersetze alle Junktoren durch ∧, ∨ und ¬.
3. Aussagenlogik
Verschiebe Negationen nach innen, eliminiere Doppelnegationen.
3
Wende das Distributivgesetz an.
4
Eliminiere
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
und ⊥.
((A1 ↑ A2 ) ⊃ ¬A2 ) ∧ (¬A1 ⊃ (A2 ∧ ⊥))
1
2
3
4
(¬(¬A1 ∨ ¬A2 ) ∨ ¬A2 ) ∧ (¬¬A1 ∨ (A2 ∧ ⊥))
((A1 ∧ A2 ) ∨ ¬A2 ) ∧ (A1 ∨ (A2 ∧ ⊥))
Wahl des Distributivgesetzes je nach Normalform
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
DNF: (A1 ∧ A2 ) ∨ (¬A2 ∧ A1 ) ∨ (A1 ∧ A2 ∧ ⊥) ∨ (¬A2 ∧ A2 ∧ ⊥)
KNF: (A1 ∨ ¬A2 ) ∧ (A2 ∨ ¬A2 ) ∧ (A1 ∨ A2 ) ∧ (A1 ∨ ⊥)
A1
9
10
Das Erfüllbarkeitsproblem der Aussagenlogik
P = NP?
Erfüllbarkeitsproblem (Satisfiability, SAT)
P: Klasse der Probleme, deren Lösungen sich polynomiell finden lassen.
Gegeben: aussagenlogische Formel F
Frage: Ist F erfüllbar, d.h., gibt es ein I ∈ I, sodass valI (F ) = 1?
NP: Klasse jener Probleme, deren Lösungen sich polynomiell verifizieren
lassen; die Suche nach der Lösung kann aber aufwändig sein.
Effiziente Verfahren zur Lösung von SAT sind wichtig in der Praxis:
P versus NP
Viele praktische Aufgaben sind Probleme der Aussagenlogik.
Gilt P = NP oder P = NP (gleichbedeutend mit P
Aussagenlogische Fragen lassen sich auf SAT zurückführen.
NP)?
SAT ist in NP: Gegeben I, lässt sich valI (F ) = 1 leicht überprüfen.
Die Suche nach so einem I scheint aber aufwändig (exponentiell?).
Unbrauchbare Verfahren:
Wahrheitstafel: Prüfe, ob es Interpretation mit Ergebnis 1 gibt.
Umwandlung in DNF: Antwort „nein“, wenn man ⊥ erhält, sonst „ja“.
SAT-Solver: Programme, die SAT lösen.
Lösen SAT mit fortgeschrittenen Methoden und Datenstrukturen.
SAT ist NP-vollständig: SAT gehört zu den schwierigsten Problemen in NP.
Kann man ein NP-vollständiges Problem effizient lösen, dann kann man
alle Probleme in NP effizient lösen.
SAT polynomiell lösbar =⇒ P = NP
Können SAT für Formeln mit Millionen von Variablen lösen.
SAT nicht polynomiell lösbar =⇒ P = NP
Aber: immer noch ineffizient für bestimmte Formeltypen.
11
12
Was Sie letzte Woche hörten
Obst, Schachteln und Aufschriften
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
1
Auf dem Tisch stehen drei Schachteln.
2
Jede Schachtel enthält Äpfel, Bananen oder Orangen.
3
Keine zwei Schachteln enthalten dasselbe Obst.
4
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Jede Schachtel trägt die Aufschrift „Äpfel“, „Bananen“ oder
„Orangen“.
5
Keine zwei Schachteln tragen dieselbe Aufschrift.
6
In keiner Schachtel ist drin, was drauf steht.
7
Sie öffnen die Schachtel mit der Aufschrift „Orangen“ und finden
darin Äpfel.
Welches Obst verbirgt sich hinter den anderen Aufschriften?
F2 , F3 , F4 , F5 , F6 , F7 , F8 |= Ab ∧ Bo
F2 , F3 , F6 , F7 |= Ab ∧ Bo
13
Was Sie letzte Woche hörten
Die Schachtel „Äpfel“ enthält Bananen,
die Schachtel „Bananen“ enthält Orangen.
14
Dualität von Funktionen, Operatoren und Formeln
Duale Funktionen
Zwei n-stellige Funktionen f und g heißen dual zueinander, wenn gilt:
not f (x1 , . . . , xn ) = g(not x1 , . . . , not xn ).
3. Aussagenlogik
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
Duale Operatoren
Was ist Logik?
Aussagenlogische Funktionen
Syntax und Semantik der Aussagenlogik
Von der Funktion zur Formel
Normalformen
Das Erfüllbarkeitsproblem
Beispiel: Obst, Schachteln und Aufschriften
Dualität von Funktionen, Operatoren und Formeln
Zwei Operatoren heißen dual, wenn die zugehörigen Funktionen dual sind.
Duale Formeln
Zwei Formeln F [A1 , . . . , An ] und G[A1 , . . . , An ] heißen dual zueinander,
wenn gilt: ¬F [A1 , . . . , An ] = G[¬A1 , . . . , ¬An ]
¬F [¬A1 , . . . , ¬An ] ist dual zu F [A1 , . . . , An ].
Sei G die Formel, die aus F durch Ersetzen aller Operatoren durch ihre
dualen hervorgeht. Dann ist G dual zu F .
15
F = G gilt genau dann, wenn F ∗ = G ∗ gilt.
16
Was Sie heute erwartet
Dr. House
3. Aussagenlogik
Max wird mit hohem Fieber und ausgeprägten Gliederschmerzen in das
Spital eingeliefert. Dr. House diskutiert die Diagnose mit einer Kollegin.
4. Endliche Automaten
House: „Wenn der Patient Fieber hat, handelt es sich um Grippe oder
Erkältung.“
3.9. Beispiel: Dr. House
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
Cameron: „Wenn er keine starken Gliederschmerzen hat, dann hat er auch
keine Grippe.“
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
House: „Jedenfalls weisen hohes Fieber und starke Gliederschmerzen
immer auf Grippe hin.“
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Cameron: “Er hat sicher nicht beide Krankheiten gleichzeitig.“
Wie lautet die Diagnose?
Wie lässt sie sich mit Hilfe der Aussagenlogik finden und begründen?
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
4.7. Büchi-Automaten
17
18
Dr. House – Wahl der Aussagenvariablen
Dr. House – Wahl der Aussagenvariablen
Aussagenvariablen können nur Aussagen repräsentieren, die einen
Wahrheitswert besitzen.
Einzelnen Haupt-, Zeit- oder Eigenschaftswörter sind keine Aussagen!
Dr. House diskutiert die Diagnose mit einer Kollegin.
Falsch: A = „krank“ oder A = „Fieber“.
Wenn der Patient Fieber hat, handelt es sich um Grippe oder Erkältung.
„Dr. House diskutiert . . . mit einer Kollegin“ = D?
„Der Patient hat Fieber“ = E ?
Möglich: A = „Max ist krank“ oder A = „Der Patient hat Fieber“.
„Der Patient hat Fieber“ = „Max hat Fieber“ = A?
Max wird mit hohem Fieber und ausgeprägten Gliederschmerzen in das
Spital eingeliefert.
Cameron: “Er hat sicher nicht beide Krankheiten gleichzeitig.“
„Max wird mit . . . eingeliefert“ = A?
„Cameron sagt, dass er nicht beide Krankheiten gleichzeitig hat.“ = F ?
„Max hat hohes Fieber“ = A,
„Max hat ausgeprägte Gliederschmerzen“ = B und
„Max wird in das Spital eingeliefert“ = C ?
„Max kann nicht beide Krankheiten gleichzeitig haben.“ = F ?
„Max hat hohes Fieber“ = „Max hat Fieber“ = A und
„Max hat ausgeprägte Gl.schmerzen“ = „Max hat Gl.schmerzen“ = B?
19
20
Dr. House – Wahl der Aussagenvariablen
Elimination von Abkürzungen und Referenzen
„Er hat beide Krankheiten“ = „P. hat Grippe“ + „P. hat Erkältung“
Max wird mit hohem Fieber und ausgeprägten Gliederschmerzen in das
Spital eingeliefert. Dr. House diskutiert die Diagnose mit einer Kollegin.
Generalisierung: Zusammenfassen von gleichartigen Aussagen
Abstraktion: Weglassen von Details
House: „Wenn der Patient Fieber hat, handelt es sich um Grippe oder
Erkältung.“
Konzentration auf das Wesentliche: Identifikation der relevanten
Teilaussagen
Cameron: „Wenn er keine starken Gliederschmerzen hat, dann hat er auch
keine Grippe.“
Aber:
Was zusammengefasst wurde, kann nicht mehr getrennt analysiert
werden.
House: „Jedenfalls weisen hohes Fieber und starke Gliederschmerzen
immer auf Grippe hin.“
Was weggelassen wurde, kann nicht für die Argumentation verwendet
werden.
Cameron: “Er hat sicher nicht beide Krankheiten gleichzeitig.“
Was nicht zusammenfasst wurde, aber zusammengehört, muss durch
zusätzliche Formeln in Beziehung gesetzt werden.
Was kann man zusammenfassen? Was weglassen? Was ist wesentlich?
F
S
G
E
...
...
...
...
„Max/Patient hat (hohes) Fieber.“
„Max/Patient hat starke/ausgeprägte Gliederschmerzen.“
„Max/Patient hat eine Grippe.“
„Max/Patient hat eine Erkältung.“
21
Dr. House – aussagenlogische Modellierung
Max wird mit hohem Fieber und
ausgeprägten Gliederschmerzen in das
Spital eingeliefert. Dr. House diskutiert die
Diagnose mit einer Kollegin.
F1 := F ∧ S
House: „Wenn der Patient Fieber hat,
handelt es sich um Grippe oder Erkältung.“
F2 := F ⊃ (G ∨ E )
Cameron: „Wenn er keine starken
Gliederschmerzen hat, dann hat er auch
keine Grippe.“
F3 := ¬S ⊃ ¬G
House: „Jedenfalls weisen hohes Fieber und
starke Gliederschmerzen immer auf Grippe
hin.“
F4 := (F ∧ S) ⊃ G
Cameron: “Er hat sicher nicht beide
Krankheiten gleichzeitig.“
F5 := ¬(G ∧ E )
22
Dr. House – Diagnose
Finde alle Interpretationen I, in denen alle Formeln wahr sind.
Vereinfachung: Prüfe nur Interpretationen, in denen F1 = F ∧ S wahr ist.
F
1
1
1
1
S G
1 0
1 0
1 1
1 1
E
0
1
0
1
F1 F ⊃ (G ∨ E ) ¬S ⊃ ¬G
1
0
1
1
1
1
1
1
1
1
1
1
(F ∧ S) ⊃ G
0
0
1
1
¬(G ∧ E )
1
1
1
0
I(G) = 1, I(E ) = 0 =⇒ Die Diagnose lautet auf „Grippe“.
23
24
Was Sie heute erwartet
Endliche Automaten
Binäraddition: Überprüfung von rechts nach links
3. Aussagenlogik
0 0 1 0 1 1 = 1110
0 0 0 1 0 1 = 510
0 1 0 0 0 0 = 1610
3.9. Beispiel: Dr. House
4. Endliche Automaten
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
0 0 1
0,1,0
0 1 1
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
1
1
0
+0
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
0 1 1
1,0,1
0 0 1
+1
+0 . . . kein Übertrag
+1 . . . Übertrag
0
0
1
4.7. Büchi-Automaten
25
26
Endliche Automaten
Endliche Automaten
Binäraddition: Überprüfung von links nach rechts
Binäraddition: Berechnung von rechts nach links
0 0 1 0 1 1 = 1110
0 0 0 1 0 1 = 510
0 1 0 0 0 0 = 1610
0 0 1 0 1 1 = 1110
0 0 0 1 0 1 = 510
0 1 0 0 0 0 = 1610
0 0 1
0,1,0
0 1 1
1
1
0
+0
0/0 , 0/1 , 1/1
0
1
0
0 1 1
1,0,1
0 0 1
+1
1/0
1
+0
+0 . . . kein Übertrag
+1 . . . Übertrag
0/0 , 1/0 , 1/1
1
0
1
+1
+0 . . . kein Übertrag
+1 . . . Übertrag
0/1
0
0
0
1
27
28
Endliche Automaten
Endliche Automaten modellieren Systeme bzw. Abläufe, die nur eine
begrenzte, feste Zahl an unterscheidbaren Zuständen besitzen.
Binäraddition: Berechnung von links nach rechts
0 0 1 0 1 1 = 1110
0 0 0 1 0 1 = 510
0 1 0 0 0 0 = 1610
0/0 , 0/1 , 1/1
0
1
0
1/0
1
Kennzeichen:
endliche Menge von Zuständen
Übergänge zwischen Zuständen
Eingaben, die die Übergänge steuern.
0/0 , 1/0 , 1/1
1
0
1
+0
+1
Ausgaben oder Aktionen, die in den Zuständen oder während der
Übergänge getätigt werden.
Anfangszustand
+0 . . . kein Übertrag
+1 . . . Übertrag
Endzustände (optional)
deterministisch: Der momentane Zustand und die nächste Eingabe
bestimmen eindeutig den Folgezustand.
nichtdeterministisch: Es gibt Zustände, die manchen Eingaben
mehrere mögliche Folgezustände besitzen.
0/1
0
Achtung, Indeterminismus! Zustand „+0“ besitzt bei Eingabe
Folgezustände, ebenso Zustand „+1“ bei Eingabe
1
1
.
0
0
zwei
30
29
Arten endlicher Automaten
Englische Begriffe: automaton/automata, finite state machine,
DFA (Deterministic Finite Automaton), NFA (Non-Determinstic FA)
(Klassischer) Endlicher Automat:
Anfangs- und Endzustände
nur Eingaben (bzw. nur Ausgaben)
Ein-/Ausgaben verknüpft mit Zustandsübergängen
verarbeitet endliche Symbolfolgen
Unterarten: deterministisch, nichtdeterministisch mit/ohne
ε-Übergängen
Weitere (nicht-endliche) Automatenarten: Kellerautomaten (Push-down
automata), Turing-Maschinen, Registermaschinen etc. können Ausgaben
wieder lesen ⇒ zusätzlicher Speicher, mächtiger als endliche Automaten.
Spezifikation von Automaten:
Graphisch: Zustände sind Knoten, Übergänge sind Kanten, Ein- und
Ausgaben sind Beschriftungen von Knoten und Kanten.
Transducer: wie endlicher Automat, aber mit Ein- und Ausgaben.
Tabellarisch: Zu jedem Zustand und Eingabesymbol gibt es einen
Eintrag mit zugehöriger Ausgabe und den Folgezuständen.
Mealy-Automat: deterministischer Transducer; in der Regel keine
Endzustände, verarbeitet daher unendliche Symbolfolgen.
Moore-Automat: wie Mealy-Automat, die Ausgaben sind aber mit den
Zuständen verknüpft.
Büchi-Automat: wie endlicher Automat, verarbeitet aber unendliche
Symbolfolgen
Weitere Typen: Verallgemeinerter endlicher Automat, Muller-Automat,
Rabin-Automat, Baumautomaten, . . .
31
32
Was Sie heute erwartet
Ampelsteuerungen
Spezifikation Verkehrsampel
3. Aussagenlogik
Spezifikation Fußgängerampel
3.9. Beispiel: Dr. House
4. Endliche Automaten
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Zustände (states) werden dargestellt durch Kreise
(Graphentheorie: „Knoten“, nodes)
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Zustände können Bezeichnungen (labels) tragen: , , , , ,
Zustandsänderungen/-übergänge (transitions) dargestellt durch Pfeile
(Graphentheorie: „gerichtete Kanten“, directed edges/arcs, arrows)
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
Schleifen ermöglichen, dass Zeit ohne Zustandsänderung vergeht.
4.7. Büchi-Automaten
Die Diagramme definieren die zulässigen Abläufe/Durchläufe (runs):
33
Fußgängerkreuzung = 1 Verkehrsampel für Autos + 1 Fussgängerampel
etwa . . .
. . . oder . . .
...
34
Ampelsteuerung 2: Korrekt, fair, lebendig, aber gefährlich
Wünschenswerte Systemeigenschaften:
Korrektheit: Die Ampeln verhalten sich gemäß Spezifikation.
Sicherheit (Safety): Nichts Böses (wie
) kann passieren.
Korrekt: Jede Ampel durchläuft nur erlaubte Anzeigenfolgen.
Projektion auf Verkehrsampel:
Lebendigkeit (Liveness): Das Gute ( bzw. ) tritt immer wieder ein.
Fairness: Kein Systemteil(nehmer) wird für immer vom Fortschritt
ausgeschlossen.
Ampelsteuerung 1: Korrekt, sicher, aber tot
Projektion auf Fußgängerampel:
Sicher, da keine verbotenen Zustände auftreten.
Korrekt, da die Projektionen
entsprechen.
Nicht lebendig, da die Zustände
und
und
der Spezifikation
nie erreicht werden.
35









Entsprechen der Am













pelspezifikationen, die
möglichen Abläufe sind
darin enthalten.
Fair und lebendig, weil in jeder Projektion die Zustände
wiederkehren (niemand muss ewig warten).
und
garantiert
36
Ampelsteuerung 2: Korrekt, fair, aber gefährlich
Ampelsteuerung 4: Sicher, fair, aber defekt
Defekt: Die Verkehrsampel entspricht nicht der Spezifikation:
Gefährlich, da die verbotenen Zustände
und
auftreten.
Ampelsteuerung 5: Sicher, fair, korrekt
Ampelsteuerung 3: Korrekt, sicher, lebendig, aber unfair
Ampelsteuerung 6: Sicher, fair, korrekt, stressfrei
Unfair gegenüber Fußgängern: Es gibt einen Ablauf, in dem die Autos
immer grün und die Fußgänger immer rot haben.
37
Was Sie heute erwartet
Reelle Numerale mit Exponentialteil
Z.B. 3.14, 0.314E1 (= 0.314 · 101 ), 314.E-2 (= 314 · 10−2 )
3. Aussagenlogik
Mindestens eine Ziffer vor Dezimalpunkt
3.9. Beispiel: Dr. House
Dezimalpunkt
4. Endliche Automaten
Nachkommastellen optional
Exponentialteil optional:
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
38
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
eingeleitet durch E
Vorzeichen optional
mindestens eine Ziffer
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Endlicher Automat für die reellen Numerale
0..9
0..9
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
1
4.7. Büchi-Automaten
39
0..9
2
.
3
E
4
+
ε
-
0..9
5
0..9
6
0..9 . . . Abkürzung für 10 parallele Übergänge beschriftet mit 0 bis 9.
ε . . . Leerwort, „Nichts“
40
0..9
0..9
1
0..9
2
.
3
E
4
+
ε
-
0..9
5
0..9
Syntaxdiagramm für die rellen Numerale
+
0..9
6
0..9
.
E
0..9
-
Zustandsbeschriftungen 1–6 dienen nur der Bezugnahme, irrelevant
für das Verhalten des Automaten
0..9 . . . Abkürzung für 10 parallele Knoten beschriftet mit 0 bis 9.
Kanten sind mit Symbolen beschriftet, die gelesen/geschrieben
werden.
Die gelesenen/geschriebenen Symbole stehen bei den Knoten.
Kanten unbeschriftet, können sich verzweigen und vereinigen.
Anfangszustand (1) ist durch einen Pfeil aus dem Nichts markiert.
ein einziger Eingang (Anfang) links markiert durch Pfeil aus dem
Nichts
Endzustände (3, 6) sind durch einen Doppelkreis markiert.
Zwei Sichtweisen:
ein einziger Ausgang (Ende) rechts markiert durch Pfeil ins Nichts
Akzeptor: Der Automat liest Symbole und akzeptiert alle
Zeichenketten, die vom Anfangs- zu einem der Endzustände führen.
Syntaxdiagramme sind verwandt mit Automaten, aber nicht dasselbe.
Generator: Der Automat schreibt Symbole und generiert jene
Zeichenketten, die vom Anfangs- zu einem der Endzustände führen.
41
Was Sie heute erwartet
RLL (run-length limited) Codes
Daten werden auf Festplatten, CDs und DVDs binär kodiert.
Binär-1: Magnetisierungswechsel bzw. Vertiefung („pit“)
1er zu dicht: werden ununterscheidbar bzw. schwächen sich ab.
1er zu weit auseinander: Synchronisation geht verloren.
3. Aussagenlogik
3.9. Beispiel: Dr. House
4. Endliche Automaten
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
42
Einfache Lösung:
Wähle Bitabstand so groß, dass 1er-Folgen richtig erkannt werden.
Füge nach jedem Datenbit ein zusätzliches Synchronisationsbit ein.
Benötigt mehr Platz als notwendig.
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Idee: Nütze die „natürlichen“ 0er-Strecken und 1er im Datenstrom.
(m : n)-(d, k)-RLL-Code: m Datenbits werden so in n Codebits übersetzt,
dass zwischen zwei 1ern mindestens d und höchstens k 0er auftreten.
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
Existiert nur für bestimmte Werte von m, n, d, k
Ziel: minimiere n/m, maximiere d
4.7. Büchi-Automaten
43
DVD: (8 : 16)-(2, 10)-RLL-Code
44
(1 : 2)-(0, 1)-RLL-Code: 2 Codebits/Datenbit, max. ein 0er zwischen 1ern.
1
0
a
b
1
Zustand a: zwei Codeworte für zwei Datenbits –
reicht.
Zustand b: ein Codewort für zwei Datenbits –
reicht nicht.
1
b
11
b
1/11
10010 ⇒ 10 10 10 11 01
oder
a
11 01 01 11 01
011,101,111
010,110
a
0
a
b
1
a
110
b
101,111
Teilung von Zustand a:
101
111
oder . . .
Mealy-Automat
45
00/101
01/111
011
a2
101
111
101
111
b
110
46
Was Sie heute erwartet
3. Aussagenlogik
3.9. Beispiel: Dr. House
4. Endliche Automaten
4.1. Einleitung
4.2. Anwendungsbeispiele
Zustand a: fünf Code- für vier Datenworte –
reicht.
Zustand b: drei Code- für vier Datenworte –
reicht nicht.
10/101
11/111
101
111
010
110
a1
011
oder . . .
Zustand a: zwei Code- für vier Datenworte –
reicht nicht.
Zustand b: ein Codewort für vier Datenworte –
reicht nicht.
00/011
b
Zustand a: fünf Code- für vier Datenworte –
reicht.
Zustand b: drei Code- für vier Datenworte –
reicht nicht.
Teilung von Zustand a:
Dritte Potenz des Automaten:
011,101,111
010,110
110
101,111
(2 : 3)-(0, 1)-RLL-Code: 3 Code-/2 Datenbits, max. ein 0er zwischen 1ern.
1
Zustand a: zwei Code- für vier Datenworte –
reicht nicht.
Zustand b: ein Codewort für vier Datenworte –
reicht nicht.
Dritte Potenz des Automaten:
Zustand b: zwei Codeworte für zwei Datenbits –
reicht.
oder
b
1
Codierungsautomat (Mealy-Automat):
0/10
0/01
0/01,1/11
1/10
a
0
a
„Potenzieren“ des Automaten:
10
01, 11
Zustand a: drei Codeworte für zwei Datenbits –
10
reicht.
a
(2 : 3)-(0, 1)-RLL-Code: 3 Code-/2 Datenbits, max. ein 0er zwischen 1ern.
10/010
11/110
00/1
01
01/1
11
01/011
01
10/1
11
1
/
11
a2
4.3.
4.4.
4.5.
4.6.
a1
b
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
4.7. Büchi-Automaten
46
47
Formale Sprachen
w1 · w2 = w1 w2 . . . Verkettung der Wörter w1 , w2 ∈ Σ∗
Σ∗ , ·, ε bildet ein Monoid
Alphabet (Σ): endliche, nicht-leere Menge atomarer Symbole
D.h.: Für alle Wörter u, v , w ∈ Σ∗ gelten folgende Gleichungen:
(u · v ) · w = u · (v · w )
Assoziativität
w ·ε=ε·w =w
Neutralität
Menge aller lateinischen Buchstaben, Ziffern und Sonderzeichen
Menge aller ägyptischen Hieroglyphen
Σ = {0, 1}
Σ∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . . }
10 · ε · 11101 · 000 = 1011101000 (Klammerung irrelevant, Assoziativität!)
ε·ε·ε=ε
{ , , , , , }
{0, . . . , 9, ., E, +, -}
{0, 1}
{00, 01, 10, 11}
Formale Sprache über Σ: beliebige Teilmenge von Σ∗
Wort über Σ: (endliche) Folge von Zeichen aus dem Alphabet Σ
die Menge aller deutschen Sätze (Alphabet: Buchstaben+Satzzeichen)
ε . . . Leerwort
Σ+ = { s1 · · · sn | si ∈ Σ, 1 ≤ i ≤ n } . . . Menge aller nicht-leeren Wörter
über Σ
∗
+
Σ = Σ ∪ {ε} . . . Menge aller Wörter über Σ (inklusive Leerwort)
2Σ . . . Menge aller Sprachen über Σ = Menge aller Teilmengen von Σ∗
Einschub: Zum Ursprung der Schreibweise 2A
Was Sie heute erwartet
48
die Menge aller Java-Programme (Alphabet: ASCII-Zeichen)
∗
{}, {ε}, Σ∗
f : A → B . . . Funktion, die die Elemente der Menge A auf Elemente der
Menge B abbildet.
3. Aussagenlogik
A → B . . . Menge aller derartigen Funktionen
4. Endliche Automaten
3.9. Beispiel: Dr. House
Wieviele derartige (totale) Funktionen gibt es, wenn A, B endlich sind?
Für jedes A-Element ist ein B-Element als Ergebnis von f festzulegen.
D.h.: Jeder von |A| Plätzen ist mit einem von |B| Werten zu belegen.
=⇒ Es gibt |B||A| Funktionen des Typs A → B, d.h., |A → B| = |B||A|
Davon abgeleitet schreibt man daher auch B A anstelle von A → B.
4.1. Einleitung
4.2. Anwendungsbeispiele
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Eine Menge B ⊆ A kann als Funktion B : A → {0, 1} aufgefasst werden:
B(x ) = 1 bedeutet x ∈ B, B(x ) = 0 bedeutet x ∈
/ B.
4.3.
4.4.
4.5.
4.6.
Die Menge aller Teilmengen von A ist daher 2A , ihre Anzahl 2|A| .
4.7. Büchi-Automaten
Statt {0, 1} kann jede zweielementige Menge verwendet werden.
Verwendet man 2 als generischen Namen dafür, erhält man B : A → 2.
Schreibweisen für die Potenzmenge von A: 2A , P(A), P(A),
℘(A)
49
50
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
51
Deterministische endliche Automaten
Beispiel: 00-freie Binärstrings
Deterministischer endlicher Automat (DEA)
1
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, q0 , F , wobei
a
Q . . . endliche Menge der Zustände
0,1
0
b
0
1
A = Q, Σ, δ, q0 , F , wobei
Σ . . . Eingabealphabet (input alphabet)
δ : Q × Σ → Q . . . Übergangsfunktion (total) (transition function)
Q = {a, b, c} . . . Zustandsmenge
q0 ∈ Q . . . Anfangszustand (initial state)
Σ = {0, 1} . . . Eingabealphabet
F ⊆ Q . . . Menge der Endzustände (final states)
δ ist eine totale Funktion: Folgezustand δ(q, s) ist für jeden Zustand q ∈ Q
und jede Eingabe s ∈ Σ eindeutig definiert. =⇒ „deterministisch“
δ : Q × Σ → Q . . . Übergangsfunktion definiert durch:
δ 0 1
a b a
b c a
c c c
Erweiterte Übergangsfunktion δ ∗ : Q × Σ∗ → Q
δ ∗ (q, ε) = q, δ ∗ (q, sw ) = δ ∗ (δ(q, s), w ) für alle q ∈ Q, s ∈ Σ, w ∈ Σ∗ .
Akzeptierte/Generierte Sprache
L(A) = { w ∈ Σ∗ | δ ∗ (q0 , w ) ∈ F }
52
Beispiel: 00-freie Binärstrings
1
0
a
b
0
q0 = a . . . Anfangszustand
F = {a, b} . . . Endzustände
53
Beispiel: 00-freie Binärstrings
0,1
1
c
a
1
δ ∗ (a, 101) = δ ∗ (δ(a, 1), 01)
= δ ∗ (a, 01)
= δ ∗ (δ(a, 0), 1)
= δ ∗ (b, 1)
= δ ∗ (δ(b, 1), ε)
= δ ∗ (a, ε)
=a
c . . . „Falle“, Fehlerzustand
wird oft auch weggelassen
c
0,1
0
b
0
c
1
δ ∗ (q, sw ) = δ ∗ (δ(q, s), w )
δ ∗ (a, 001) = δ ∗ (δ(a, 0), 01)
= δ ∗ (b, 01)
= δ ∗ (δ(b, 0), 1)
= δ ∗ (c, 1)
= δ ∗ (δ(c, 1), ε)
= δ ∗ (c, ε)
=c
δ ∗ (q, ε) = q
Das Wort 101 wird von A akzeptiert/generiert, d.h., 101 ∈ L(A),
weil δ ∗ (a, 101) = a ein Endzustand ist.
δ ∗ (q, sw ) = δ ∗ (δ(q, s), w )
δ ∗ (q, ε) = q
Das Wort 001 wird von A nicht akzeptiert/generiert, 001 ∈
/ L(A),
∗
weil δ (a, 001) = c kein Endzustand ist.
54
L(A) = { w ∈ {0, 1}∗ | 00 kommt nicht in w vor }
55
Beispiel: reelle Numerale
0..9
0..9
-
.
E,+
,-
3
E
.,+
,
-
0..9
4
.,
.,E,+
,
2
0..9
+,-
.,E,+,-
E
A = {1, . . . , 7}, {0, . . . , 9, ., E, +, -}, δ, 1, {3, 6} ,
wobei
δ 0 ··· 9 . E + 1 2 ··· 2 7 7 7 7
2 2 ··· 2 3 7 7 7
3 3 ··· 3 7 4 7 7
4 6 ··· 6 7 7 5 5
5 6 ··· 6 7 7 7 7
6 6 ··· 6 7 7 7 7
7 7 ··· 7 7 7 7 7
5
7
0..9
6
1
0..9
.
2
0..9
E
3
4
0..9
+,-
5
0..9
6
.,E,+,-,0..9
56
Was Sie heute erwartet
δ
AZ 1
2
EZ 3
4
5
EZ 6
7
0
2
2
3
6
6
6
7
···
···
···
···
···
···
···
···
9
2
2
3
6
6
6
7
.
7
3
7
7
7
7
7
E
7
7
4
7
7
7
7
+
7
7
7
5
7
7
7
7
7
7
5
7
7
7
56
Nichtdeterministische endliche Automaten
Nichtdeterministischer endlicher Automat (NEA)
3. Aussagenlogik
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, q0 , F , wobei
3.9. Beispiel: Dr. House
Q, Σ, q0 , F . . . siehe DEAs
4. Endliche Automaten
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
0..9
0..9
.,
E,
+,
-
0..9
1
Beispiel: reelle Numerale
δ ⊆ Q × (Σ ∪ {ε}) × Q . . . Übergangsrelation
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Erweiterte Übergangsrelation δ ∗ ⊆ Q × Σ∗ × Q
δ ∗ ist die kleinste Menge mit folgenden Eigenschaften:
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
(q, ε, q) ∈ δ ∗ für alle q ∈ Q
Wenn (q1 , w , q2 ) ∈ δ ∗ und (q2 , s, q3 ) ∈ δ, dann (q1 , ws, q3 ) ∈ δ ∗ .
Die Relation δ ∗ ist der reflexive und transitive Abschluss der Relation δ.
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
Akzeptierte/Generierte Sprache
L(A) = { w ∈ Σ∗ | (q0 , w , qf ) ∈ δ ∗ für ein qf ∈ F }
4.7. Büchi-Automaten
57
58
Unterschiede von NEAs gegenüber DEAs:
Tabellarische Darstellung der Übergangsrelation δ ⊆ Q × (Σ ∪ {ε}) × Q
Für jeden Zustand q ∈ Q und jede Eingabe s ∈ Σ ∪ {ε}:
Tabelleneintrag mit der Menge { q ∈ Q | (q, s, q ) ∈ δ } der Folgezustände
Es kann mehrere Folgezustände zu einem Zustand und einer Eingabe
geben.
Es sind Zustandswechsel ohne Eingabe möglich (ε-Übergänge).
0..9
0..9
0..9
1
2
.
3
E
4
+
ε
-
1
0..9
5
0..9
0..9
0..9
Es kann keinen Folgezustand zu einem Zustand und einer Eingabe
geben.
0..9
2
.
3
E
4
+
ε
-
6
In Zustand 4 ist ein Wechsel zu Zustand 5 ohne Eingabe möglich.
In Zustand 1 gibt es für die Eingabe E keinen Folgezustand (ebenso
wie bei allen anderen Zuständen bei „Eingabefehler“).
59
Vergleich DEA – NEA
Zu zeigen: 42.E0 ∈ L(A), wobei
DEAs und NEAs besitzen dieselbe Ausdrucksstärke.
1
0..2..9
2
.
3
E
4
+
ε
-
60
Zu jedem NEA gibt es einen DEA, der dieselbe Sprache akzeptiert.
(Lässt sich automatisch finden.)
Vorteile von NEAs:
0..9
5
6
Jeder DEA ist per Definition auch ein NEA.
L(A) = { w ∈ Σ∗ | (1, w , qf ) ∈ δ ∗ für ein qf ∈ {3, 6} }
0..9
0..9
Alternative Definition von NEAs:
Übergangsfunktion δ : Q × (Σ ∪ {ε}) → 2Q (ist total!) statt
Übergangsrelation δ ⊆ Q × (Σ ∪ {ε}) × Q
Beispiel: 42.E0 ist ein reelles Numeral
0..4..9
5
δ
0 ··· 9
.
E
+
ε
AZ 1 {1, 2} · · · {1, 2} {} {} {} {} {}
2
{} · · · {}
{3} {} {} {} {}
EZ 3 {3} · · · {3}
{} {4} {} {} {}
4
{} · · · {}
{} {} {5} {5} {5}
5 {5, 6} · · · {5, 6} {} {} {} {} {}
EZ 6
{} · · · {}
{} {} {} {} {}
In den Zuständen 1 und 5 sind für jede Ziffer jeweils zwei
Folgezustände möglich: 1 und 2 bzw. 5 und 6.
und A folgender Automat ist:
0..9
0..9
Benötigen teilweise erheblich weniger Zustände und Übergänge als
äquivalente DEAs.
Die Zustandszahl im DEA kann exponentiell größer sein als im NEA.
6
Bei Modellierungsaufgaben leichter zu konstruieren.
(q1 , w , q2 ) ∈ δ ∗ ,(q2 , s, q3 ) ∈ δ =⇒ (q1 , ws, q3 ) ∈ δ ∗
(1, ε, 1)
(1, 4, 1)
(1, 4, 1)
(1, 4, 1)
(1, 2, 2)
(1, 42, 2)
(1, 42, 2)
(2, ., 3)
(1, 42., 3)
(1, 42., 3)
(3, E, 4)
(1, 42.E, 4)
(1, 42.E, 4)
(4, ε, 5)
(1, 42.E, 5)
(1, 42.E, 5)
(5, 0, 6)
(1, 42.E0, 6)
(1, 42.E0, 6) ∈ δ ∗ , 1 ist Anfangs- und 6 Endzustand =⇒ 42.E0 ∈ L(A)
Vorteile von DEAs:
Effiziente Abarbeitung, kein Backtracking.
61
62
Beispiel: Suche nach Max und Ana
Was Sie heute erwartet
Gesucht: Automat zur Suche nach „max“ und „ana“ in einem Text
Σ = {a, m, n, x, z}
(z . . . Stellvertreter für b–l, o–w, y, z, . . . )
NEA:
2
a,m,n,x,z
6
m
,z
n,x
134
x
m
x,z
13
n
a
6
a
m
a
4.3.
4.4.
4.5.
4.6.
n
m
1
a
5
a
12
a
n
m
4.1. Einleitung
4.2. Anwendungsbeispiele
a,m,n,x,z
z
DEA:
n,x,z
4. Endliche Automaten
x
a
3
3.9. Beispiel: Dr. House
4
a
m
1
3. Aussagenlogik
a,m,n,x,z
15
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
4.7. Büchi-Automaten
z
x,
n,
63
64
Transducer
(1 : 2)-(0, 1)-RLL-Encoder als Transducer
Endlicher Transducer
A = {a, b}, {0, 1}, {01, 10, 11}, δ, {a}, {a, b}
. . . wird beschrieben durch ein 6-Tupel A = Q, Σ, Γ, δ, I, F , wobei
0/01
Q, Σ, F . . . siehe DEAs
Γ . . . Ausgabealphabet (output alphabet)
a
δ ⊆ Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) × Q . . . Übergangsrelation
δ ∗ ist die kleinste Menge mit folgenden Eigenschaften:
=⇒
b
δ
0
1
a {(01, a)} {(10, b)}
b {(10, b)} {(11, a)}
[A] = { (ε, ε),
(0, 01), (1, 10),
(00, 0101), (10, 1010), (01, 0110), (11, 1011),
(000, 010101), (100, 101010), (010, 011010), . . . }
Erweiterte Übergangsrelation δ ∗ ⊆ Q × Σ∗ × Γ∗ × Q
(q1 , w , w , q2 ) ∈ δ ∗ , (q2 , s, s , q3 ) ∈ δ
0/10
1/11
I ⊆ Q . . . Anfangszustände
(q, ε, ε, q) ∈ δ ∗ für alle q ∈ Q
1/10
(q1 , ws, w s , q3 ) ∈ δ ∗
Nichtdeterminismus: Im Allgemeinen mehrere Ausgaben zu einer Eingabe!
Übersetzungsrelation [A] ⊆ Σ∗ × Γ∗
[A] = { (w , w ) ∈ Σ∗ × Γ∗ | (i, w , w , f ) ∈ δ ∗ für ein i ∈ I und ein f ∈ F }
65
66
Was Sie heute erwartet
Mealy-Automat
. . . wird beschrieben durch ein 6-Tupel A = Q, Σ, Γ, δ, γ, q0 , wobei
3. Aussagenlogik
Q, Σ, δ, q0 . . . siehe DEAs
3.9. Beispiel: Dr. House
Γ . . . Ausgabealphabet (output alphabet)
4. Endliche Automaten
γ : Q × Σ → Γ . . . Ausgabefunktion (output function)
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
Erweiterte Übergangsfunktion δ ∗ : Q × Σ∗ → Q siehe DEA.
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Erweiterte Ausgabefunktion γ ∗ : Q × Σ∗ → Γ∗
γ ∗ (q, ε) = ε
γ ∗ (q, sw ) = γ(q, s) · γ ∗ (δ(q, s), w )
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
für alle q ∈ Q, s ∈ Σ, w ∈ Σ∗
Übersetzungsfunktion [A] : Σ∗ → Γ∗
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
[A](w ) = γ ∗ (q0 , w )
4.7. Büchi-Automaten
68
67
Mealy-Automaten sind ein Spezialfall von Transducern:
Detektor für fallende Flanken
Nur ein Anfangszustand: I = {q0 }
Die Übergangsrelation ist deterministisch:
Ausgabe 1, wenn in der Eingabe ein Wechsel von 1 auf 0 stattfindet.
1/0
0/0
1/0
w : 00110001010 · · ·
a
b
[A](w ): 000010001010 · · ·
0/1
Der Folgezustand δ(q, s) ist eindeutig durch q und s bestimmt.
Keine ε-Übergänge
Relationstupel: (q, s, γ(q, s), δ(q, s))
Alle Zustände sind Endzustände: F = Q
(1 : 2)-(0, 1)-RLL-Encoder als Mealy-Automat
A = {a, b}, {0, 1}, {01, 10, 11}, δ, γ, a
δ 0 1
a a b
b b a
γ
a
b
0 1
01 10
10 11
0/01
1/10
a
Detektor für 111-Blöcke
Ausgabe 1, wenn in der Eingabe drei 1er aufeinander folgen.
0/0
1/1
0/0
0/10
b
a
1/11
w : ε 0 1 00
10
01
11
000
100
···
[A](w ): ε 01 10 0101 1010 0110 1011 010101 101010 · · ·
1/0
0/0
69
b
1/0
c
w : 00110111110101110 · · ·
[A](w ): 00000001110000010 · · ·
70
Was Sie heute erwartet
Moore-Automat
. . . wird beschrieben durch ein 6-Tupel A = Q, Σ, Γ, δ, γ, q0 , wobei
3. Aussagenlogik
Q, Σ, δ, q0 . . . siehe DEAs
3.9. Beispiel: Dr. House
Γ . . . Ausgabealphabet (output alphabet)
4. Endliche Automaten
γ : Q → Γ . . . Ausgabefunktion (output function)
4.1. Einleitung
4.2. Anwendungsbeispiele
4.3.
4.4.
4.5.
4.6.
(Mealy: γ : Q × Σ → Γ)
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Erweiterte Übergangsfunktion δ ∗ : Q × Σ∗ → Q siehe DEA.
Erweiterte Ausgabefunktion γ ∗ : Q × Σ∗ → Γ∗
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
für alle q ∈ Q, s ∈ Σ, w ∈ Σ∗
γ ∗ (q, ε) = ε
γ ∗ (q, sw ) = γ(δ(q, s)) · γ ∗ (δ(q, s), w )
(Mealy: γ ∗ (q, sw ) = γ(q, s) · γ ∗ (δ(q, s), w ))
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
Übersetzungsfunktion [A] : Σ∗ → Γ∗
4.7. Büchi-Automaten
[A](w ) = γ ∗ (q0 , w )
72
71
Moore-Automaten sind ein Spezialfall von Transducern:
Nur ein Anfangszustand: I = {q0 }
Alle Übergange in einen Zustand geben dasselbe Symbol aus.
Die Übergangsrelation ist deterministisch:
Der Folgezustand δ(q, s) ist eindeutig durch q und s bestimmt.
Keine ε-Übergänge
Relationstupel: (q, s, γ(δ(q, s)), δ(q, s))
Alle Zustände sind Endzustände: F = Q
Vergleich von Moore- und Mealy-Automaten
Die Ausgabe erfolgt
. . . bei Moore-Automaten beim „Betreten“ des Zustandes, unabhängig
von der Herkunft. Die Ausgabe hängt nur vom Zustand ab.
. . . bei Mealy-Automaten beim Zustandswechsel, der durch
Ursprungszustand und Eingabe festgelegt ist.
Moore- und Mealy-Automaten besitzen dieselbe Ausdrucksstärke, sind
aber schwächer als Transducer.
Moore-Automaten haben in der Regel mehr Zustände als
73
Mealy-Automaten.
(1 : 2)-(0, 1)-RLL-Encoder als Moore-Automat
A = {a1 , a2 , b}, {0, 1}, {01, 10, 11}, δ, γ, a
0
δ 0 1
γ
a1 a1 b
a1 01
0
a2 a1 b
a2 11
a1
b b a2
b 10
01
a2
11
1
1
1
0
b
10
w : ε 0 1 00
10
01
11
000
100
···
[A](w ): ε 01 10 0101 1010 0110 1011 010101 101010 · · ·
Zum Vergleich: Mealy-Automat
δ 0 1
a a b
b b a
γ
a
b
0 1
01 10
10 11
0/01
1/10
a
0/10
b
1/11
74
Relevanz von Mealy- und Moore-Automaten
Detektor für fallende Flanken
Ausgabe 1, wenn in der Eingabe ein Wechsel von 1 auf 0 stattfindet.
1
0
a2
1
0
1
w : 00110001010 · · ·
a1
b
0
[A](w ): 000010001010 · · ·
1
0
0
Mealy-Schaltwerk
Moore-Schaltwerk
Detektor für 111-Blöcke
Ausgabe 1, wenn in der Eingabe drei 1er aufeinander folgen.
0
1
0
0
a
0
1
b
0
1
c1
0
0
w : 00110111110101110 · · ·
[A](w ): 00000001110100010 · · ·
1
c2
„inputs“ stammen aus dem Eingabealphabet Σ
„outputs“ stammen aus dem Ausgabealphabet Γ
Flip-Flops speichern den Zustand aus Q; Reset: Anfangszustand q0
„combination logic“: realisiert die Übergangsfunktionen δ und γ.
1
75
Was Sie heute erwartet
Graphiken: Ken Reid, Indiana University – Purdue University Indianapolis
Büchi-Automaten
Deterministischer Büchi-Automat
3. Aussagenlogik
3.9. Beispiel: Dr. House
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, q0 , F , wobei
4.1. Einleitung
4.2. Anwendungsbeispiele
Σω . . . Menge aller unendlichen Wörter (= ω-Wörter) über Σ
Q, Σ, δ, q0 , F wie bei DEAs definiert sind.
4. Endliche Automaten
4.3.
4.4.
4.5.
4.6.
76
Akzeptanz von Wörtern
4.2.1. Ampelsteuerungen
4.2.2. Reelle Numerale
4.2.3. RLL Codes
Ein deterministischer Büchi-Automat A akzeptiert ein Wort
s1 s2 s3 · · · ∈ Σω , wenn es Zustände q0 , q1 , q2 , q3 , · · · ∈ Q gibt, sodass
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
q0 ∈ Q der Startzustand ist,
δ(qi−1 , si ) = qi für alle i ∈ N gilt und
es unendlich viele i gibt, sodass qi ein Endzustand ist (qi ∈ F ).
4.6.1. Endlicher Transducer
4.6.2. Mealy-Automaten
4.6.3. Moore-Automaten
Akzeptierte/Generierte Sprache
4.7. Büchi-Automaten
77
L(A) = { w ∈ Σω | w wird von A akzeptiert }
78
Faire Verkehrsampel
Nichtdeterministischer Büchi-Automat
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, I, F , wobei
b
a
Q, Σ, F . . . siehe DEA
c
I ⊆ Q . . . Anfangszustände
δ ⊆ Q × Σ × Q . . . Übergangsrelation
d
h
g
Akzeptanz von Wörtern
e
f
Der Automat akzeptiert genau jene Wörter aus
immer wieder grün wird.
{a, . . . , h}ω ,
Ein nichtdeterministischer Büchi-Automat A akzeptiert ein Wort
s1 s2 s3 · · · ∈ Σω , wenn es Zustände q0 , q1 , q2 , q3 , · · · ∈ Q gibt, sodass
bei denen es
q0 ∈ Q ein Startzustand ist (q0 ∈ I),
(qi−1 , si , qi ) ∈ δ für alle i ∈ N gilt und
es unendlich viele i gibt, sodass qi ein Endzustand ist (qi ∈ F ).
Akzeptierte/Generierte Sprache
L(A) = { w ∈ Σω | w wird von A akzeptiert }
79
Nur endlich viele 1er
Gesucht: Ein Büchi-Automat, der genau jene ω-Wörter über {0, 1}
akzeptiert, die nur eine endliche Anzahl an 1ern enthalten.
0
0,1
a
0
b
Kein deterministischer Büchi-Automaten akzeptiert diese Sprache.
=⇒ Nichtdeterministische Büchi-Automaten sind ausdrucksstärker als
deterministische!
81
80
Document
Kategorie
Gesundheitswesen
Seitenansichten
10
Dateigröße
538 KB
Tags
1/--Seiten
melden