[ Weiter ] [ Seitenende ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]
Reguläre Sprachen und EA
Die Menge der regulären Sprachen ist gleich der Menge der von EA akzeptierten Sprachen.
Wichtige in xfst berechenbare Eigenschaften von EA
Tests bezüglich endlicher Automaten auf dem Stack
Wichtige in xfst berechenbare Beziehungen von EA
Tests bezüglich endlicher Automaten auf dem Stack (EA2 auf EA1)
Anstelle von apply up kann man auch apply down sagen. Statt test lower-universal auch upper-universal. Diese Sprechweisen hängen mit den Transduktoren zusammen, welche eine “obere” und “untere” Sprache haben. Bei den endlichen Automaten sind aber beide Sprachen gleich.
Definition 5.4.1 (Zustandsübergangsfunktion für Zeichenketten).
Die auf Zeichenketten erweiterte Übergangsfunktion δ∗ : Φ × Σ∗→ Φ bestimmt den Zustand nach dem vollständigen Lesen eines Wortes.
Die Sprache L(A) eines DEA A = 〈Φ,Σ,δ,S,F〉 ist die Menge aller Zeichenketten, für die δ∗ ausgehend vom Startzustand einen Endzustand ergibt.
Beispiel-Berechnung für δ∗ aus Beispiel 5.1.2
Beispiel-Evaluation
Siehe Abb. 5.5 auf Seite 131.
Definition 5.4.3 (Zustandsübergangsfunktion für Zeichenketten).
Die auf Zeichenketten erweiterte Übergangsfunktion δ∗ : Φ × Σ∗→ ℘(Φ) bestimmt die Menge der erreichbaren Zustände nach dem vollständigen Lesen einer Zeichenkette.
Die Sprache L(A) eines NEA A = 〈Φ,Σ,δ,S,F〉 ist die Menge aller Zeichenketten, für die δ∗ ausgehend vom Startzustand mindestens einen Endzustand enthält.
Definition 5.4.5 (Zustandsübergangsfunktion für Zeichenketten). Die auf Zeichenketten erweiterte Übergangsfunktion δ∗ : Φ × Σ∗→ ℘(Φ) bestimmt die Menge der erreichbaren Zustände nach dem vollständigen Lesen einer Zeichenkette.
Die Bestimmung der Übergangsfunktion δ∗ auf Zeichenketten setzt auf der reflexiven und transitiven Hülle der ϵ-Übergänge auf: δϵ∗.
Reflexive und transitive Hülle der ϵ-Übergänge
Definition 5.4.6. Die ϵ-Hülle δϵ∗ : Φ → ℘(Φ) eines ϵ-NEA für einen Zustand T ∈ Φ ist rekursiv definiert durch:
Äquivalenz der Sprachen von DEA, NEA und ϵ-NEA
Entfernung von ϵ-Übergängen
Für jeden ϵ-NEA lässt sich ein NEA (ohne ϵ) konstruieren, der die gleiche Sprache akzeptiert.
xfst[1]: epsilon-remove
net
Entfernung von Nicht-Determinismus
Für jeden NEA lässt sich ein DEA konstruieren, der die gleiche Sprache akzeptiert.
xfst[1]: determinize
net
Entfernung unnötiger Zustände
Für jeden DEA lässt sich ein DEA mit minimaler Anzahl Zustände konstruieren, der die gleiche
Sprache akzeptiert.
xfst[1]: minimize
net
Der Befehl minimize net beinhaltet die Entfernung von ϵ-Übergängen und die Determinisierung. D.h. ein minimisierter EA ist immer deterministisch und ohne ϵ-Übergängen.
Beispiel für äquivalente EA
Siehe Abb. 117 auf Seite 140.
[ Weiter ] [ Seitenbeginn ] [ Überkapitel ] [ Bitte Skript-Fehler melden ]