Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:automatentheorie

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

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 = { x1, x2, …, xn }
    • werden akzeptiert, wenn Automat im Endzustand ist
  • Ausgaben: Zeichenfolgen über Alphabet Y = { y1, y2, …, yn }
  • Zustände (states): unterscheidbare Stadien der Verarbeitung von Eingaben
    • Zustandsmenge S = { s1, s2, …, sn }
    • 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, s0, δ, F)
    • X: Eingabealphabet
    • S: Zustandsmenge
    • s0: Anfangszustand
    • δ: Zustandsübergangsfunktion
      • S x X → S
      • δ(si, xj) → sk (Folgezustand zu si)
        * δ<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>) 

        * Konfiguration: (aktueller Zustand, restliche Eingabe)

  • Arbeitsweise (Beispiel Lesekopf)
    1. Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s0 über erstem Zeichen
    2. Lesekopf in Zustand s liest aktuelles Zeichen x und geht in Zustand δ(s, x), bewegt sich eine Position nach rechts
    3. Ist das Eingabeband leer und der Automat ist in einem Endzustand, hat der Automat die Eingabe akzeptiert
    4. Der Automat springt nicht zurück an den Anfang. Neues Wort heißt neuer Automat.

Sprache eines DEA

  • L(A) := { w ∈ X</sup> | δ*(s0, w) ∈ F} (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 ==== Unterschied DEA / NEA ==== * Im DEA gibt es für jeden Zustand für jedes Eingabezeichen eine Transition in seinen Folgezustand! * DEA: nur eindeutige Transitionen, NEA: mehrdeutige Transitionen möglich * im NEA können alle Transitionen in Fehlerzustände im Gegensatz zum DEA weggelassen werden ===== 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 * Definition: A = (X, S, S0, δ, F) * X: Eingabealphabet * S: Zustandsmenge * S0: Menge der Anfangszustände, S0 ⊆ S * δ: Zustandsübergangsfunktion * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich * δ(si, xj) → Sk (Folgezustände zu si, leere Menge, ein oder mehrere Zustände)
    * werden zwei NEA zusammengefasst, bilden sie ein logisches Oder bzw. die Vereinigungsmenge ==== Ü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, S0, δ, F) → Ad = (X, Sd, s0d, δd, Fd) * Sd := P(S) (alle möglichen Teilmengen von S) * s0d := S0 (Menge der Anfangszustände des NEA ist ein Element von P(S)) * δ(Q, x) := Uq ∈ Qδ(q, x) (alle Mengen der Folgezustände zu qi, die vereinigt werden müssen) * Fd := { Q ∈ Sd | 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 * ⇒ uviw ∈ L ∀ i ∈ N (vi: 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 = anbn für n ∈ N} - wähle n entsprechend des Pumping-Lemmas - wähle Exemplar/Wort x ∈ L: anbn - 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 an werden nur a's vervielfältigt ⇒ |uviw|a ≠ |uviw|b ===== Automaten mit Ausgabe ===== * Mealy-Automaten: Ausgabe bei Transition * δ: S x X → Y, δ(si, x) = Y * Moore-Automaten: Ausgabe im Zielzustand * δ: S → Y * Eselsbrücke: Moore → Zustand, Mealy → Transition
    ===== 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>) * 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> | S ⇒</sup> x} (alle Wörter, die aus dem Startsymbol abgeleitet werden können) * Chomsky-Hierarchie (Typ(i + 1) ist gleichzeitig vom Typ(i)) * 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)+ (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)+ * 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>, 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ε und Nε → ε
    ==== Überführung einer Grammatik in Normalform ==== * Typ 3
    * A → aaB ersetzen durch A → aC, C → aB * A → B ersetzen durch A → w | B ⇒* w * Für jede Transition in einen Endzustand müssen zwei Produktionen vorhanden sein! * 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 → bi ersetzen durch A → Bi 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 ===== * Übung: NEA in DEA überführen * Skript Herold lesen * Definition reguläre Sprache * Normalformen * Kann man Automaten mit LaTeX setzen? * Beispiele aus Vorlesung nochmal machen * Aufgaben 3.5.2 machen
se/automatentheorie.1228146022.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)