Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
se:automatentheorie [2008-12-01 16:55] stefan |
se:automatentheorie [2014-04-05 11:42] (aktuell) |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== Automatentheorie ====== | ====== Automatentheorie ====== | ||
+ | |||
+ | ===== Grundlagen ===== | ||
+ | * Ein **Alphabet** ist eine endliche nicht-leere Menge S. Ein Element s ∈ S heißt **Symbol** oder Zeichen. | ||
+ | * s = s<sub>1</sub>...s<sub>n</sub>, s<sub>i</sub> ∈ S, i = 1...n heißt **Wort** über S. | ||
+ | * S<sup>+</sup> := { s | s Wort über S } Menge der Wörter über S, die aus mindestens einem Zeichen bestehen. | ||
+ | * Sei s ∈ S<sup>+</sup>. |s| := **Länge** des Wortes := Anzahl der Symbole im Wort s. | ||
+ | * Sei s ∈ S. |s|<sub>t</sub> := die Anzahl des Auftretens des Symbols t im Wort s. | ||
+ | * S<sup>n</sup> := { s ∈ S<sup>+</sup> | |s| = n } Menge der Wörter über S der Länge n. | ||
+ | * **Konkatenation**: Seien s = s<sub>1</sub>...s<sub>n</sub> ∈ S<sup>+</sup>, s<sub>i</sub> ∈ S, i = 1...n, t = t<sub>1</sub>...t<sub>m</sub> ∈ S<sup>+</sup>, t<sub>i</sub> ∈ S, i = 1...m. st = s<sub>1</sub>...s<sub>n</sub>t<sub>1</sub>...t<sub>m</sub> ∈ S<sup>+</sup> heißt Konkatenation von s mit t. | ||
+ | * L ⊆ S<sup>*</sup> heißt **(formale) Sprache** über S. | ||
+ | |||
+ | ==== Backus-Naur-Form ==== | ||
+ | * Formale (Meta-)Sprache zur Beschreibung von formalen Sprachen | ||
+ | * Symbole: ::=, |, {} | ||
===== Einleitung ===== | ===== Einleitung ===== | ||
Zeile 6: | Zeile 20: | ||
* diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische Kybernetik ∈ [[http://de.wikipedia.org/wiki/Kybernetik|Kybernetik]] (Wissenschaft von der Funktion komplexer 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 | * Funktion endlicher Automaten: Eingaben → (innere) Zustände → Ausgaben | ||
+ | * Automaten werden von außen bedient, interagieren also mit ihrer Umwelt. | ||
+ | * Sie reagieren auf Eingaben mit bestimmten zugeordneten Ausgaben. | ||
+ | * Ihre Arbeitsweise ist gekennzeichnet durch die Abfolge unterscheidbarer Schritte und Stadien der Bearbeitung der Ein- und Ausgaben. | ||
* Klassifizierung | * Klassifizierung | ||
* Endliche erkennende Automaten | * Endliche erkennende Automaten | ||
Zeile 21: | Zeile 38: | ||
* deterministisch = "sind determiniert", Folgezustand ist durch aktuellen Zustand und Eingabesymbol eindeutig bestimmt | * deterministisch = "sind determiniert", Folgezustand ist durch aktuellen Zustand und Eingabesymbol eindeutig bestimmt | ||
* **Definition**: A = (X, S, s<sub>0</sub>, δ, F) | * **Definition**: A = (X, S, s<sub>0</sub>, δ, F) | ||
- | * X: Eingabealphabet | + | * X: Eingabealphabet (endlich) |
- | * S: Zustandsmenge | + | * S: Zustandsmenge (endlich) |
- | * s<sub>0</sub>: Anfangszustand | + | * s<sub>0</sub>: Anfangszustand s<sub>0</sub> ∈ S |
* δ: Zustandsübergangsfunktion | * δ: Zustandsübergangsfunktion | ||
* S x X → S | * S x X → S | ||
- | * δ(s<sub>i</sub>, x<sub>j</sub>) → s<sub>k</sub> (Folgezustand zu s<sub>i</sub>) | + | * δ(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> | + | * F: Menge der Endezustände F ⊆ S |
+ | * δ<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<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, ε) = s | s ∈ S, ε leeres Wort | ||
Zeile 40: | Zeile 58: | ||
==== Sprache eines DEA ==== | ==== 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 mehrerer möglicher Endzustände führen) | + | * Sei A = (X, S, s<sub>0</sub>, δ, F) ein DEA. L(A) := { w ∈ X<sup>*</sup> | δ<sup>*</sup>(s<sub>0</sub>, w) ∈ F} heißt die durch A akzeptierte Sprache (Menge aller Wörter, die vom Anfangszustand in einen mehrerer möglicher Endzustände führen) |
- | * durch endliche Automaten akzeptierbar/definierbar, falls es einen DEA gibt, der sie akzeptiert | + | * Eine Sprache L ist durch einen endlichen Automaten definierbar (oder **regulär**), falls es einen DEA A gibt mit L = L(A) (Automat akzeptiert die Sprache) |
==== Unterschied DEA / NEA ==== | ==== Unterschied DEA / NEA ==== | ||
- | * Im DEA gibt es **für jeden Zustand für jedes Eingabezeichen eine Transition** in seinen Folgezustand! | + | * Zustandsübergangsfunktion des NEA hat P(S) als Wertebereich |
- | * DEA: nur eindeutige Transitionen, NEA: mehrdeutige Transitionen möglich | + | * Im DEA gibt es **für jeden Zustand für jedes Eingabezeichen eine Transition** in seinen Folgezustand! |
+ | * DEA: nur eindeutige Transitionen, NEA: mehrdeutige (oder keine) Transitionen möglich | ||
+ | * NEA hat evtl. mehrere Anfangszustände | ||
* im NEA können alle Transitionen in Fehlerzustände im Gegensatz zum DEA weggelassen werden | * im NEA können alle Transitionen in Fehlerzustände im Gegensatz zum DEA weggelassen werden | ||
===== Nicht-deterministische endliche Automaten (NEA) ===== | ===== Nicht-deterministische endliche Automaten (NEA) ===== | ||
- | * Folgezustand zu aktuellem Zustand und Eingabesymbol wird durch nicht näher bestimmtes Verfahren aus evtl. mehreren möglichen gewählt | + | * Eigenschaften |
+ | * kann mehrere Startzustände enthalten | ||
+ | * Folgezustand zu aktuellem Zustand und Eingabesymbol wird durch nicht näher bestimmtes Verfahren aus evtl. mehreren möglichen gewählt | ||
+ | * es muss keinen Folgezustand geben | ||
+ | * es kann mehrere Folgezustände zum gleichen Eingabesymbol geben | ||
* **Definition**: A = (X, S, S<sub>0</sub>, δ, F) | * **Definition**: A = (X, S, S<sub>0</sub>, δ, F) | ||
- | * X: Eingabealphabet | + | * X: Eingabealphabet (endlich) |
- | * S: Zustandsmenge | + | * S: Zustandsmenge (endlich) |
* S<sub>0</sub>: Menge der Anfangszustände, S<sub>0</sub> ⊆ S | * S<sub>0</sub>: Menge der Anfangszustände, S<sub>0</sub> ⊆ S | ||
* δ: Zustandsübergangsfunktion | * δ: Zustandsübergangsfunktion | ||
* S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | * 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) | * δ(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) | ||
+ | * F: Menge der Endezustände F ⊆ S | ||
* werden zwei NEA zusammengefasst, bilden sie ein logisches Oder bzw. die Vereinigungsmenge | * werden zwei NEA zusammengefasst, bilden sie ein logisches Oder bzw. die Vereinigungsmenge | ||
+ | |||
+ | ==== Sprache eines NEA ==== | ||
+ | * Sei A = (X, S, S<sub>0</sub>, δ, F) ein NEA. L(A) := { w ∈ X<sup>*</sup> | ∃ s<sub>0</sub> ∈ S<sub>0</sub> : δ<sup>*</sup>(s<sub>0</sub>, w) ∩ F ≠ ∅ } heißt die durch A akzeptierte Sprache (Menge aller Wörter, die von einem Anfangszustand in eine Zustandsmenge führen, die wenigstens einen Endezustand enthält) | ||
+ | * Eine Sprache L ist durch einen endlichen Automaten definierbar (oder **regulär**), falls es einen DEA A gibt mit L = L(A) (Automat akzeptiert die Sprache) | ||
==== Überprüfung, ob NEA und DEA äquivalent ==== | ==== Überprüfung, ob NEA und DEA äquivalent ==== | ||
Zeile 85: | Zeile 114: | ||
===== Automaten mit Ausgabe ===== | ===== Automaten mit Ausgabe ===== | ||
+ | * **Definition**: A = (X, Y, S, s<sub>0</sub>, δ, σ) | ||
+ | * X: Eingabealphabet | ||
+ | * Y: Ausgabealphabet | ||
+ | * S: Zustandsmenge (endlich) | ||
+ | * s<sub>0</sub>: Startzustand s<sub>0</sub> ⊆ S | ||
+ | * δ: Zustandsübergangsfunktion S x X → S | ||
+ | * σ: Ausgabefunktion | ||
* Mealy-Automaten: Ausgabe bei Transition | * Mealy-Automaten: Ausgabe bei Transition | ||
- | * δ: S x X → Y, δ(s<sub>i</sub>, x) = Y | + | * σ: S x X → Y, σ(s<sub>i</sub>, x) = Y |
* Moore-Automaten: Ausgabe im Zielzustand | * Moore-Automaten: Ausgabe im Zielzustand | ||
- | * δ: S → Y | + | * σ: S → Y |
* Eselsbrücke: M**oo**re -> Z**u**stand, Me**a**ly -> Tr**a**nsition | * Eselsbrücke: M**oo**re -> Z**u**stand, Me**a**ly -> Tr**a**nsition | ||
+ | |||
===== Formale Sprachen und Grammatiken ===== | ===== Formale Sprachen und Grammatiken ===== | ||
Zeile 139: | Zeile 176: | ||
===== ToDo ===== | ===== ToDo ===== | ||
- | * Übung: NEA in DEA überführen | + | * <del>Beispiele aus Vorlesung nochmal machen</del> |
- | * Skript Herold lesen | + | * Aufgaben 3.5.2 machen |
- | * Kann man Automaten mit LaTeX setzen? | + | * <del>Übung: NEA in DEA überführen</del> |
- | * Beispiele aus Vorlesung nochmal machen | + | * <del>BNF</del> |
- | * Aufgaben 3.5.2 machen | + | * <del>Skript Herold lesen</del> |
+ | * <del>Definition reguläre Sprache</del> | ||
+ | * <del>Normalformen</del> | ||
+ | * <del>Kann man Automaten mit LaTeX setzen?</del> |