Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:automatentheorie

Automatentheorie

Grundlagen

  • Ein Alphabet ist eine endliche nicht-leere Menge S. Ein Element s ∈ S heißt Symbol oder Zeichen.
  • s = s1…sn, si ∈ S, i = 1…n heißt Wort über S.
  • S+ := { s | s Wort über S } Menge der Wörter über S, die aus mindestens einem Zeichen bestehen.
  • Sei s ∈ S+. |s| := Länge des Wortes := Anzahl der Symbole im Wort s.
  • Sei s ∈ S. |s|t := die Anzahl des Auftretens des Symbols t im Wort s.
  • Sn := { s ∈ S+ | |s| = n } Menge der Wörter über S der Länge n.
  • Konkatenation: Seien s = s1…sn ∈ S+, si ∈ S, i = 1…n, t = t1…tm ∈ S+, ti ∈ S, i = 1…m. st = s1…snt1…tm ∈ S+ heißt Konkatenation von s mit t.
  • L ⊆ S</sup> heißt (formale) Sprache über S. ==== Backus-Naur-Form ==== * Formale (Meta-)Sprache zur Beschreibung von formalen Sprachen * Symbole: ::=, |, {}
    ===== 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 * 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 * 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 (endlich) * S: Zustandsmenge (endlich) * s0: Anfangszustand s0 ∈ S * δ: Zustandsübergangsfunktion * S x X → S * δ(si, xj) → sk (Folgezustand zu si) * F: Menge der Endezustände F ⊆ S * δ</sup>: Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X</sup> * δ</sup>(s0, w) ∈ S | w = x1, x2, …, xn, xi ∈ X * δ</sup>(s, ε) = s | s ∈ S, ε leeres Wort * δ</sup>(s, xi) = δ(s, xi) | xi ∈ X, ein Zeichen * δ</sup>(s, x) = δ</sup>(s, x1x2…xn) = δ</sup>(δ(s, x1), x2x3…xn) * Konfiguration: (aktueller Zustand, restliche Eingabe) * Arbeitsweise (Beispiel Lesekopf) - Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s0 ü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 ==== * Sei A = (X, S, s0, δ, F) ein DEA. L(A) := { w ∈ X</sup> | δ</sup>(s0, 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) * 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, S0, δ, F) * X: Eingabealphabet (endlich) * S: Zustandsmenge (endlich) * 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)
    * 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, S0, δ, F) ein NEA. L(A) := { w ∈ X</sup> | ∃ s0 ∈ S0 : δ</sup>(s0, 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, 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 ===== * Definition: A = (X, Y, S, s0, δ, σ) * X: Eingabealphabet * Y: Ausgabealphabet * S: Zustandsmenge (endlich) * s0: Startzustand s0 ⊆ S * δ: Zustandsübergangsfunktion S x X → S * σ: Ausgabefunktion
    * 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)) 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)+ (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ε → ε
    * 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 ⇒* 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 → 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 ===== * Beispiele aus Vorlesung nochmal machen * Aufgaben 3.5.2 machen * Übung: NEA in DEA überführen * BNF * Skript Herold lesen * Definition reguläre Sprache * Normalformen * Kann man Automaten mit LaTeX setzen?
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)