Stochastische Akzeptoren
Definition
Stochastische Akzeptoren stellen eine weitere Verallgemeinerung von nicht-deterministischen
endlichen erkennenden Automaten dar. Die Möglichkeiten der Zustandsüberführungen werden hier mit
Wahrscheinlichkeiten versehen, so daß man schließlich für jedes Wort und jeden Zustand
eine Wahrscheinlichkeit angeben kann, mit der sich der Akzeptor nach der Abarbeitung des Wortes
in gerade diesem Zustand befindet.
| Definition: |
W = (A,  ) heißt stochastischer Akzeptor, wenn
 gilt, wobei folgende Eigenschaften erfüllt sind:
- Es gilt: V ist disjunkte Vereinigung von S und VT mit Zustandsalphabet
S = {s1, ..., sn} für ein n aus N und ein Eingabealphabet VT.
-
 ist eine Wahrscheinlichkeitsverteilung über S.
 heißt Anfangsverteilung.
-
Die Teilmenge S1 von S heißt Menge der Endzustände.
- M ist eine Abbildung, die jedem x aus VT eine stochastische nxn-Matrix M(x) zuordnet.
- Es gilt, daß eine reelle Zahl ist mit 0 <=
< 1.
heißt Schnittpunkt oder Schwellwert von W.
|
|---|
Ein stochastischer Akzeptor erkennt ein Wort genau dann, wenn er sich beginnend mit der
Startverteilung nach Abarbeitung des Wortes mit einer Wahrscheinlichkeit, die größer als der
Schwellwert ist, in einem Endzustand befindet. Formal wird dies durch folgende Definition
beschrieben.
| Definition: |
W = (A , ) sei ein stochastischer Akzeptor mit obigen Daten.
- Die Abbildung M werde zu einer Abbildung von VT* in die Menge der
stochastischen nxn-Matrizen durch
M(w)=M(a1)···M(ar) für alle w aus VT+
mit w = a1...ar, ai
VT und M( ) = Enxn, wobei Enxn
die n-zeilige Einheitsmatrix ist, erweitert.
- Es werden Zahlen
 aus {0,1}, i = 1,...,n, durch
= 1 für si aus S1 und
= 0 sonst gegeben. Damit wird ein Spaltenvektor
 definiert.
- Für w aus VT* setzen wir Pr(w) =
 .
-
L(W) = {w | w VT*, Pr(w) >
}
heißt die von W angenommene oder erkannte (akzeptierte) Sprache (auch stochastische Sprache
genannt).
|
|---|
Im Folgenden soll untersucht werden, welche Eigenschaften Stochastische Akzeptoren haben, speziell:
Was können Stochastische Akzeptoren?
© 1995 Gerriet Backer und
Marita Scheiwe
Letzte Änderung: