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