Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- se:automatentheorie [2008-12-01 14:54]
stefan
+++ se:automatentheorie [2008-12-02 10:18]
stefan
@@ Zeile 1: / Zeile 1: @@
 ====== 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 =====
@@ Zeile 6: / Zeile 20: @@
     * 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
+    * 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
     * Endliche erkennende Automaten
@@ Zeile 14: / Zeile 31: @@
     * 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
+  * **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) =====
+  * deterministisch = "sind determiniert", Folgezustand ist durch aktuellen Zustand und Eingabesymbol eindeutig bestimmt
   * **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
       * 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>
+    * 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, ε) = 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!
+  * **Konfiguration**: (aktueller Zustand, restliche Eingabe)
+  * Arbeitsweise (Beispiel Lesekopf)
+    - Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s<sub>0</sub> über erstem Zeichen
+    - Lesekopf in Zustand s liest aktuelles Zeichen x und geht in Zustand δ(s, x), bewegt sich eine Position nach rechts
+    - Ist das Eingabeband leer und der Automat ist in einem Endzustand, hat der Automat die Eingabe akzeptiert
+    - Der Automat springt nicht zurück an den Anfang. Neues Wort heißt neuer Automat.
 ==== 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)
+  * 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 ====
+  * Zustandsübergangsfunktion des NEA hat P(S) als Wertebereich
+    * 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
 ===== Nicht-deterministische endliche Automaten (NEA) =====
+  * 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)
-    * X: Eingabealphabet
+    * X: Eingabealphabet (endlich)
-    * S: Zustandsmenge
+    * S: Zustandsmenge (endlich)
     * 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)
+    * F: Menge der Endezustände F ⊆ S
+  * 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 ====
+  - Konstruiere zu gegebenem DEA einen äquivalenten NEA (direkt erfüllt, da jeder DEA schon ein NEA ist)
+  - Konstruiere zu gegebenem NEA einen äquivalenten DEA (akzeptiert die selbe Sprache)
+    * A = (X, S, S<sub>0</sub>, δ, F) → A<sup>d</sup> = (X, S<sup>d</sup>, s<sub>0</sub><sup>d</sup>, δ<sup>d</sup>, F<sup>d</sup>)
+    * S<sup>d</sup> := P(S) (alle möglichen Teilmengen von S)
+    * s<sub>0</sub><sup>d</sup> := S<sub>0</sub> (Menge der Anfangszustände des NEA ist **ein** Element von P(S))
+    * δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) (alle Mengen der Folgezustände zu q<sub>i</sub>, die vereinigt werden müssen)
+    * F<sup>d</sup> := { Q ∈ S<sup>d</sup> | Q ∩ F ≠ ∅}
+===== Pumping-Lemma =====
+  * ab einer gewissen Länge von Wörtern (> Anzahl der Zustände) sind in diesen Zyklen enthalten, die beliebig häufig durchlaufen werden können
+  * Sei L regulär über X: ∃ n ∈ N, sodass ∀ x ∈ L mit |x| ≥ n: x = uvw (uvw = Teilwörter, u = Weg in den Zyklus, v = Zyklus, w = Weg aus dem Zyklus)
+  * Bedingung: |uv| ≤ n, |v| ≥ 1, n muss mindestens die Anzahl der Zustände sein
+  * => uv<sup>i</sup>w ∈ L ∀ i ∈ N (v<sup>i</sup>: v wird i-mal vervielfältigt)
+==== Beispiel ====
+Nachweis, dass folgende Sprache nicht regulär ist, durch Umkehrung des Pumping-Lemma:
+L = { x ∈ {a, b} | x = a<sup>n</sup>b<sup>n</sup> für n ∈ N}
+  - wähle n entsprechend des Pumping-Lemmas
+  - wähle Exemplar/Wort x ∈ L: a<sup>n</sup>b<sup>n</sup>
+  - betrachte Zerlegungen in Teilwörter x = uvw mit |uv| ≤ n, |v| ≥ 1
+  - für alle Zerlegungen von x in Teilwörter mit x = uvw und v in a<sup>n</sup> werden nur a's vervielfältigt => |uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>b</sub>
+===== 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
+    * σ: S x X → Y, σ(s<sub>i</sub>, x) = Y
+  * Moore-Automaten: Ausgabe im Zielzustand
+    * σ: S → Y
+  * Eselsbrücke: M**oo**re -> Z**u**stand, Me**a**ly -> Tr**a**nsition
+===== Formale Sprachen und Grammatiken =====
+  * **formale Sprache**: Menge von Wörtern bestehend aus Symbolen eines endlichen Alphabets
+  * **Ableitung**: fortgesetzte Ersetzungsschritte, die mit dem Startsymbol beginnen (Kennzeichnung ⇒<sup>*</sup>)
+  * **Grammatiken** erzeugen/generieren formale Sprachen: G = (N, T, S, P)
+    * N: Menge der nicht-terminalen Symbole (Großbuchstaben)
+    * T: Menge der terminalen Symbole (Kleinbuchstaben)
+    * S: Startsymbol
+    * P: Menge der Produktionen (Ersetzungsregeln)
+  * eine durch G erzeugte Sprache: L(G) = { x ∈ T<sup>*</sup> | S ⇒<sup>*</sup> x} (alle Wörter, die aus dem Startsymbol abgeleitet werden können)
+  * Chomsky-Hierarchie (Typ(i + 1) ist gleichzeitig vom Typ(i)) definiert 4 Typen von Grammatiken
+    * Typ 0 (allgemeine Grammatiken): keine Einschränkung der Produktionen
+      * Beispiele: aBc → B, B → c, bA → B, B → aaa
+      * alle Normalformen
+    * Typ 1 (nicht verkürzende Grammatiken): für Produktionen a → b gilt b ∈ (N ∪ T)<sup>+</sup> (leeres Wort ausgeschlossen) und |a| ≤ |b|
+      * aB → abA, B → ab, AB → CaB
+      * Termination, Expansion 2, doppelte Substitution
+    * Typ 2 (kontextfreie Grammatiken): für Produktionen a → b gilt a ∈ N, b ∈ (N ∪ T)<sup>+</sup>
+      * Beispiele: A → a, A → AB, AB → AC, A → abC
+      * Termination, Expansion 2
+    * Typ 3 ((rechts-)lineare Grammatiken, **reguläre Sprachen**): für Produktionen a → b gilt a ∈ N, b hat die Form tB oder t mit t ∈ T<sup>*</sup>, B ∈ N, b ≠ ε
+      * Beispiele: A → a, A → aA, A → B, A → aaaB
+      * Termination, Expansion 1
+  * **Normalformen** sind einfache Repräsentanten einer Klasse äquivalenter Grammatiken
+    * A → ε (Reduktion)
+    * A → t (Termination)
+    * A → tB (Expansion 1)
+    * A → BC (Expansion 2)
+    * AB → CD (doppelte Substitution)
+  * Sei L eine formale Sprache. L ist regulär, wenn es eine lineare Grammatik G gibt mit L = L(G) (Grammatiken vom Typ 3 erzeugen reguläre Sprachen)
+  * Um eine Grammatik vom Typ 3 durch einen Automaten abzubilden, müssen Regeln der Form A → t ersetzt werden durch A → tN<sub>ε</sub> und N<sub>ε</sub> → ε
+    * Für jede Transition in einen Endzustand müssen zwei Produktionen vorhanden sein, wenn im Endzustand weitere Eingaben erlaubt (aber nicht verpflichtend) sind: (Beispielautomat "otto" erkennen, Endzustand W) V → o | oW, W → o | t | oW | tW
+  * Typische Fragen zu Grammatiken
+    * Typ nach Chomsky? -> Produktionen untersuchen
+    * Ist G in Normalform? -> Produktionen untersuchen, Verstöße gegen Normalform suchen
+    * Ist die Ableitung des Wortes xyz möglich? -> mit den Produktionen ausgehend von S versuchen, das Wort nachzubauen
+==== Überführung einer Grammatik in Normalform ====
+  * Typ 3
+    * A → aaB ersetzen durch A → aC, C → aB
+    * A → B ersetzen durch A → w | B ⇒<sup>*</sup> w
+    * alle Regeln sind nun von der Form A → a oder A → aB
+  * Typ 2
+    * für jedes terminale Symbol t wird ein nicht-terminales Symbol T erstellt und die Produktionen um T → t erweitert
+    * A → b<sub>i</sub> ersetzen durch A → B<sub>i</sub> für jedes i
+    * A → BCD ersetzen durch A → BE, E → CD
+    * alle Regeln sind nun von der Form A → a oder A → BC
 ===== ToDo =====
-  * Skript Herold lesen
+  * Beispiele aus Vorlesung nochmal machen
+  * Aufgaben 3.5.2 machen
+  * Übung: NEA in DEA überführen
+  * <del>BNF</del>
+  * <del>Skript Herold lesen</del>
+  * <del>Definition reguläre Sprache</del>
+  * <del>Normalformen</del>
+  * Kann man Automaten mit LaTeX setzen?

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge