Akzeptor
|
endlicher erkennender Automat
|
|
|
Bestandteile
|
5-Tupel
|
|
A = (I, Q, δ, q0, F)
|
|---|
|
|
I
|
Eingabealphabet
|
|
|
Q
|
Zustandsmenge (nichtleer, endlich)
|
|
|
q0
|
Anfangszustand
|
|
|
F
|
Endzustandsmenge
|
|
F ⊆ Q
|
|---|
|
|
δ
|
Übergangsfunktion
|
|
δ : Q x I → Q
|
|---|
|
|
|
δ ist im Allgemeinen nur partiell definiert
|
|
|
|
deterministischer endlicher Automat
|
|
|
Verallgemeinerung
|
δ Relation
|
|
δ : Q x I → ℘ Q
|
|---|
oder
|
δ : Q x I → Q -set
|
|
|
|
δ total definiert
|
|
|
|
nichtdeterministischer endlicher Automat
|
|
|
akzeptierte Sprache L(A)
|
L(A) = { w ∈ I* | (q0, w) |—* q, q ∈ F}
|
|
|
(q0, w) |—* q
|
der Anfangszustand q0 wird durch Eingabe von w in den Endzustand q ∈ F überführt
|
|
|
|
bei deterministischen Automaten muss δ für jedes Zeichen aus w definiert sein
|
|
bei nichtdeterminsitischen Automaten muss es eine Möglichkeit geben, einen Endzustand zu erreichen
|
|
|
|
deterministische endliche Automaten erkennen ein Wort w in einer Zeit proportional zu |w|
|
|
|
|
zu jedem nichtdeterministischen endlichen Automaten gibt es einen gleichwertigen deterministischen endlichen Automaten
|
|
|
?
|
Was heißt gleichwertiger Automat?
|
|
|
Zustands- Übergangs- Diagramm
|
grafische Darstellung eines Automaten
|
|
|
|---|
|
|
Compilerbau & Formale Sprachen: Endliche Automaten
