Benutzer-Werkzeuge
se:automatentheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
|
se:automatentheorie [2008-12-01 14:54] stefan |
se:automatentheorie [2014-04-05 11:42] |
||
|---|---|---|---|
| Zeile 1: | Zeile 1: | ||
| - | ====== Automatentheorie ====== | ||
| - | |||
| - | ===== Einleitung ===== | ||
| - | * Einordung "Automatentheorie" | ||
| - | * Formalisierung reaktiver Systeme (diskrete Systeme) | ||
| - | * diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische Kybernetik ∈ [[http://de.wikipedia.org/wiki/Kybernetik|Kybernetik]] (Wissenschaft von der Funktion komplexer Systeme) | ||
| - | * Funktion endlicher Automaten: Eingaben → (innere) Zustände → Ausgaben | ||
| - | * Klassifizierung | ||
| - | * Endliche erkennende Automaten | ||
| - | * am weitesten reduzierte Automaten | ||
| - | * keine Äußerungen nach außen | ||
| - | * nächste Stufe: minimale Reaktion (binär, z.B. Lampe an/aus) | ||
| - | * **Eingaben**: Zeichenfolgen über Alphabet X = { x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub> } | ||
| - | * werden akzeptiert, wenn Automat im Endzustand ist | ||
| - | * **Ausgaben**: Zeichenfolgen über Alphabet Y = { y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>n</sub> } | ||
| - | * **Zustände** (states): unterscheidbare Stadien der Verarbeitung von Eingaben | ||
| - | * Zustandsmenge S = { s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n</sub> } | ||
| - | * Partizipien weisen auf Zustände hin: "Taste gedrückt" etc. | ||
| - | |||
| - | ===== Deterministische endliche Automaten (DEA) ===== | ||
| - | * **Definition**: A = (X, S, s<sub>0</sub>, δ, F) | ||
| - | * X: Eingabealphabet | ||
| - | * S: Zustandsmenge | ||
| - | * s<sub>0</sub>: Anfangszustand | ||
| - | * δ: Zustandsübergangsfunktion | ||
| - | * S x X → S | ||
| - | * δ(s<sub>i</sub>, x<sub>j</sub>) → s<sub>k</sub> (Folgezustand zu s<sub>i</sub>) | ||
| - | * δ<sup>*</sup>: Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X<sup>*</sup> | ||
| - | * δ<sup>*</sup>(s<sub>0</sub>, w) ∈ S | w = x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, x<sub>i</sub> ∈ X | ||
| - | * δ<sup>*</sup>(s, ε) = s | s ∈ S, ε leeres Wort | ||
| - | * δ<sup>*</sup>(s, x<sub>i</sub>) = δ(s, x<sub>i</sub>) | x<sub>i</sub> ∈ X, **ein** Zeichen | ||
| - | * δ<sup>*</sup>(s, x) = δ<sup>*</sup>(s, x<sub>1</sub>x<sub>2</sub>...x<sub>n</sub>) = δ<sup>*</sup>(δ(s, x<sub>1</sub>), x<sub>2</sub>x<sub>3</sub>...x<sub>n</sub>) | ||
| - | * Im DEA gibt es **für jeden Zustand für jedes Eingabezeichen eine Transition** in seinen Folgezustand! | ||
| - | |||
| - | ==== Sprache eines DEA ==== | ||
| - | * L(A) := { w ∈ X<sup>*</sup> | δ<sup>*</sup>(s<sub>0</sub>, w) ∈ F} (Menge aller Wörter, die vom Anfangszustand in einen Endzustand führen) | ||
| - | * durch endliche Automaten akzeptierbar/definierbar, falls es einen DEA gibt, der sie akzeptiert | ||
| - | |||
| - | ===== Nicht-deterministische endliche Automaten (NEA) ===== | ||
| - | * **Definition**: A = (X, S, S<sub>0</sub>, δ, F) | ||
| - | * X: Eingabealphabet | ||
| - | * S: Zustandsmenge | ||
| - | * S<sub>0</sub>: Menge der Anfangszustände, S<sub>0</sub> ⊆ S | ||
| - | * δ: Zustandsübergangsfunktion | ||
| - | * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | ||
| - | * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, leere Menge, ein oder mehrere Zustände) | ||
| - | |||
| - | ===== ToDo ===== | ||
| - | * Skript Herold lesen | ||
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
