Automatentheorie

Ein Alphabet ist eine endliche nicht-leere Menge S. Ein Element s ∈ S heißt Symbol oder Zeichen.

s = s₁…s_n, s_i ∈ 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.

Sⁿ := { s ∈ S⁺ | |s| = n } Menge der Wörter über S der Länge n.

Konkatenation: Seien s = s₁…s_n ∈ S⁺, s_i ∈ S, i = 1…n, t = t₁…t_m ∈ S⁺, t_i ∈ S, i = 1…m. st = s₁…s_nt₁…t_m ∈ S⁺ heißt Konkatenation von s mit t.

L ⊆ S 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 = { 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) ===== * deterministisch = "sind determiniert", Folgezustand ist durch aktuellen Zustand und Eingabesymbol eindeutig bestimmt * Definition: A = (X, S, s₀, δ, F) * X: Eingabealphabet (endlich) * S: Zustandsmenge (endlich) * s₀: Anfangszustand s₀ ∈ S * δ: Zustandsübergangsfunktion * S x X → S * δ(s_i, x_j) → s_k (Folgezustand zu s_i) * F: Menge der Endezustände F ⊆ S * δ</sup>: Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X</sup> * δ</sup>(s₀, w) ∈ S | w = x₁, x₂, …, x_n, x_i ∈ X * δ</sup>(s, ε) = s | s ∈ S, ε leeres Wort * δ</sup>(s, x_i) = δ(s, x_i) | x_i ∈ X, ein Zeichen * δ</sup>(s, x) = δ</sup>(s, x₁x₂…x_n) = δ</sup>(δ(s, x₁), x₂x₃…x_n) * Konfiguration: (aktueller Zustand, restliche Eingabe) * Arbeitsweise (Beispiel Lesekopf) - Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s₀ ü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, s₀, δ, F) ein DEA. L(A) := { w ∈ X</sup> | δ</sup>(s₀, 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, S₀, δ, F) * X: Eingabealphabet (endlich) * S: Zustandsmenge (endlich) * 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)
* 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₀, δ, F) ein NEA. L(A) := { w ∈ X</sup> | ∃ s₀ ∈ S₀ : δ</sup>(s₀, 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₀, δ, F) → Ad = (X, Sd, s₀d, δd, Fd) * Sd := 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) (alle Mengen der Folgezustände zu q_i, 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, s₀, δ, σ) * X: Eingabealphabet * Y: Ausgabealphabet * S: Zustandsmenge (endlich) * s₀: Startzustand s₀ ⊆ S * δ: Zustandsübergangsfunktion S x X → S * σ: Ausgabefunktion
* Mealy-Automaten: Ausgabe bei Transition * σ: S x X → Y, σ(s_i, 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 → b_i ersetzen durch A → B_i 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?</sup>