Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- se:automatentheorie [2008-12-01 14:20]
stefan angelegt
+++ se:automatentheorie [2008-12-01 15:17]
stefan
@@ 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)
+==== Ü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)
+    * F<sup>d</sup> := { Q ∈ S<sup>d</sup> | Q ∩ F ≠ ∅}
+===== Pumping-Lemma =====
+  * 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>
+===== ToDo =====
+  * Skript Herold lesen

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge