Benutzer-Werkzeuge
se:automatentheorie
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
| Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung Nächste Überarbeitung Beide Seiten der Revision | ||
|
se:automatentheorie [2008-12-01 14:54] stefan |
se:automatentheorie [2008-12-01 16:55] stefan |
||
|---|---|---|---|
| Zeile 14: | Zeile 14: | ||
| * werden akzeptiert, wenn Automat im Endzustand ist | * werden akzeptiert, wenn Automat im Endzustand ist | ||
| * **Ausgaben**: Zeichenfolgen über Alphabet Y = { y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>n</sub> } | * **Ausgaben**: Zeichenfolgen über Alphabet Y = { y<sub>1</sub>, y<sub>2</sub>, ..., y<sub>n</sub> } | ||
| - | * **Zustände** (states): unterscheidbare Stadien der Verarbeitung von Eingaben | + | * **Zustände** (states): **unterscheidbare** Stadien der Verarbeitung von Eingaben |
| * Zustandsmenge S = { s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n</sub> } | * Zustandsmenge S = { s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n</sub> } | ||
| * Partizipien weisen auf Zustände hin: "Taste gedrückt" etc. | * Partizipien weisen auf Zustände hin: "Taste gedrückt" etc. | ||
| ===== Deterministische endliche Automaten (DEA) ===== | ===== Deterministische endliche Automaten (DEA) ===== | ||
| + | * deterministisch = "sind determiniert", Folgezustand ist durch aktuellen Zustand und Eingabesymbol eindeutig bestimmt | ||
| * **Definition**: A = (X, S, s<sub>0</sub>, δ, F) | * **Definition**: A = (X, S, s<sub>0</sub>, δ, F) | ||
| * X: Eingabealphabet | * X: Eingabealphabet | ||
| Zeile 31: | Zeile 32: | ||
| * δ<sup>*</sup>(s, x<sub>i</sub>) = δ(s, x<sub>i</sub>) | x<sub>i</sub> ∈ X, **ein** Zeichen | * δ<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>) | * δ<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>) | ||
| - | * Im DEA gibt es **für jeden Zustand für jedes Eingabezeichen eine Transition** in seinen Folgezustand! | + | * **Konfiguration**: (aktueller Zustand, restliche Eingabe) |
| + | * Arbeitsweise (Beispiel Lesekopf) | ||
| + | - Eingabeband enthält endlich viele Eingabesymbole des Eingabealphabets, Lesekopf in s<sub>0</sub> ü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 ==== | ==== Sprache eines DEA ==== | ||
| - | * L(A) := { w ∈ X<sup>*</sup> | δ<sup>*</sup>(s<sub>0</sub>, w) ∈ F} (Menge aller Wörter, die vom Anfangszustand in einen Endzustand führen) | + | * L(A) := { w ∈ X<sup>*</sup> | δ<sup>*</sup>(s<sub>0</sub>, 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 | * 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) ===== | ===== 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, S<sub>0</sub>, δ, F) | * **Definition**: A = (X, S, S<sub>0</sub>, δ, F) | ||
| * X: Eingabealphabet | * X: Eingabealphabet | ||
| Zeile 45: | Zeile 57: | ||
| * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | * S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich | ||
| * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, leere Menge, ein oder mehrere Zustände) | * δ(s<sub>i</sub>, x<sub>j</sub>) → S<sub>k</sub> (Folgezustände zu s<sub>i</sub>, 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, S<sub>0</sub>, δ, F) → A<sup>d</sup> = (X, S<sup>d</sup>, s<sub>0</sub><sup>d</sup>, δ<sup>d</sup>, F<sup>d</sup>) | ||
| + | * S<sup>d</sup> := P(S) (alle möglichen Teilmengen von S) | ||
| + | * s<sub>0</sub><sup>d</sup> := S<sub>0</sub> (Menge der Anfangszustände des NEA ist **ein** Element von P(S)) | ||
| + | * δ(Q, x) := U<sub>q ∈ Q</sub>δ(q, x) (alle Mengen der Folgezustände zu q<sub>i</sub>, die vereinigt werden müssen) | ||
| + | * F<sup>d</sup> := { Q ∈ S<sup>d</sup> | 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 | ||
| + | * => uv<sup>i</sup>w ∈ L ∀ i ∈ N (v<sup>i</sup>: 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 = a<sup>n</sup>b<sup>n</sup> für n ∈ N} | ||
| + | |||
| + | - wähle n entsprechend des Pumping-Lemmas | ||
| + | - wähle Exemplar/Wort x ∈ L: a<sup>n</sup>b<sup>n</sup> | ||
| + | - 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 a<sup>n</sup> werden nur a's vervielfältigt => |uv<sup>i</sup>w|<sub>a</sub> ≠ |uv<sup>i</sup>w|<sub>b</sub> | ||
| + | |||
| + | ===== Automaten mit Ausgabe ===== | ||
| + | * Mealy-Automaten: Ausgabe bei Transition | ||
| + | * δ: S x X → Y, δ(s<sub>i</sub>, x) = Y | ||
| + | * Moore-Automaten: Ausgabe im Zielzustand | ||
| + | * δ: S → Y | ||
| + | * Eselsbrücke: M**oo**re -> Z**u**stand, Me**a**ly -> Tr**a**nsition | ||
| + | |||
| + | ===== 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>*</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>*</sup> | S ⇒<sup>*</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)<sup>+</sup> (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)<sup>+</sup> | ||
| + | * 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>*</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<sub>ε</sub> und N<sub>ε</sub> → ε | ||
| + | * 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 ⇒<sup>*</sup> 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<sub>i</sub> ersetzen durch A → B<sub>i</sub> 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 ===== | ===== ToDo ===== | ||
| + | * Übung: NEA in DEA überführen | ||
| * Skript Herold lesen | * Skript Herold lesen | ||
| + | * Kann man Automaten mit LaTeX setzen? | ||
| + | * Beispiele aus Vorlesung nochmal machen | ||
| + | * Aufgaben 3.5.2 machen | ||
se/automatentheorie.txt · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)
Seiten-Werkzeuge
Falls nicht anders bezeichnet, ist der Inhalt dieses Wikis unter der folgenden Lizenz veröffentlicht: CC Attribution-Noncommercial-Share Alike 4.0 International
