Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Automatentheorie
- Einleitung
- Deterministische endliche Automaten (DEA)
  - Sprache eines DEA

Automatentheorie

Einleitung

Einordung "Automatentheorie"
- Formalisierung reaktiver Systeme (diskrete Systeme)
- diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische 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₁, x₂, …, x_n }
- werden akzeptiert, wenn Automat im Endzustand ist
Ausgaben: Zeichenfolgen über Alphabet Y = { y₁, y₂, …, y_n }
Zustände (states): unterscheidbare Stadien der Verarbeitung von Eingaben
- Zustandsmenge S = { s₁, s₂, …, s_n }
- Partizipien weisen auf Zustände hin: "Taste gedrückt" etc.

Deterministische endliche Automaten (DEA)

Definition: A = (X, S, s₀, δ, F)

X: Eingabealphabet
S: Zustandsmenge
s₀: Anfangszustand

δ: Zustandsübergangsfunktion

S x X → S

δ(s_i, x_j) → s_k (Folgezustand zu s_i)

* δ<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> | δ^*(s₀, 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₀, δ, F)
* X: Eingabealphabet
* S: Zustandsmenge
* S₀: Menge der Anfangszustände, S₀ ⊆ S
* δ: Zustandsübergangsfunktion
* S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich
* δ(s_i, x_j) → S_k (Folgezustände zu s_i, 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₀, δ, F) → A^d = (X, S^d, s₀^d, δ^d, F^d)
* S^d := P(S) (alle möglichen Teilmengen von S)
* s₀^d := S₀ (Menge der Anfangszustände des NEA ist ein Element von P(S))
* δ(Q, x) := U_{q ∈ Q}δ(q, x)
* F^d := { Q ∈ S^d | 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ⁱw ∈ L ∀ i ∈ N (vⁱ: v wird i-mal vervielfältigt)

===== ToDo =====
* Skript Herold lesen}

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

**Dies ist eine alte Version des Dokuments!**