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.

• Formale (Meta-)Sprache zur Beschreibung von formalen Sprachen
• Symbole: ::=, |, {}

• 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.

• 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
• δ^*: Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X^*
  • δ^*(s₀, w) ∈ S | w = x₁, x₂, …, x_n, x_i ∈ X
  • δ^*(s, ε) = s | s ∈ S, ε leeres Wort
  • δ^*(s, x_i) = δ(s, x_i) | x_i ∈ X, ein Zeichen
  • δ^*(s, x) = δ^*(s, x₁x₂…x_n) = δ^*(δ(s, x₁), x₂x₃…x_n)
• Konfiguration: (aktueller Zustand, restliche Eingabe)
• Arbeitsweise (Beispiel Lesekopf)
  1. Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s₀ ü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.

• Sei A = (X, S, s₀, δ, F) ein DEA. L(A) := { w ∈ X^* | δ^*(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)

• 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

• 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

• Sei A = (X, S, S₀, δ, F) ein NEA. L(A) := { w ∈ X^* | ∃ s₀ ∈ S₀ : δ^*(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)

1. Konstruiere zu gegebenem DEA einen äquivalenten NEA (direkt erfüllt, da jeder DEA schon ein NEA ist)
2. 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) (alle Mengen der Folgezustände zu q_i, die vereinigt werden müssen)
   • F^d := { Q ∈ S^d | Q ∩ F ≠ ∅}

• 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
• ⇒ uvⁱw ∈ L ∀ i ∈ N (vⁱ: v wird i-mal vervielfältigt)

Nachweis, dass folgende Sprache nicht regulär ist, durch Umkehrung des Pumping-Lemma:

L = { x ∈ {a, b} | x = aⁿbⁿ für n ∈ N}

1. wähle n entsprechend des Pumping-Lemmas
2. wähle Exemplar/Wort x ∈ L: aⁿbⁿ
3. betrachte Zerlegungen in Teilwörter x = uvw mit |uv| ≤ n, |v| ≥ 1
4. für alle Zerlegungen von x in Teilwörter mit x = uvw und v in aⁿ werden nur a's vervielfältigt ⇒ |uvⁱw|_a ≠ |uvⁱw|_b

• 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 Sprache: Menge von Wörtern bestehend aus Symbolen eines endlichen Alphabets
• Ableitung: fortgesetzte Ersetzungsschritte, die mit dem Startsymbol beginnen (Kennzeichnung ⇒^*)
• 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^* | S ⇒^* 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^*, 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

• 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

• 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?