Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:automatentheorie

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Beide Seiten der vorigen Revision Vorhergehende Überarbeitung
Nächste Überarbeitung
Vorhergehende Überarbeitung
se:automatentheorie [2008-12-01 14:54]
stefan
se:automatentheorie [2014-04-05 11:42] (aktuell)
Zeile 1: Zeile 1:
 ====== Automatentheorie ====== ====== Automatentheorie ======
 +
 +===== Grundlagen =====
 +  * Ein **Alphabet** ist eine endliche nicht-leere Menge S. Ein Element s ∈ S heißt **Symbol** oder Zeichen. ​
 +  * s = s<​sub>​1</​sub>​...s<​sub>​n</​sub>,​ s<​sub>​i</​sub>​ ∈ S, i = 1...n heißt **Wort** über S.
 +  * S<​sup>​+</​sup>​ := { s | s Wort über S } Menge der Wörter über S, die aus mindestens einem Zeichen bestehen.
 +  * Sei s ∈ S<​sup>​+</​sup>​. |s| := **Länge** des Wortes := Anzahl der Symbole im Wort s.
 +  * Sei s ∈ S. |s|<​sub>​t</​sub>​ := die Anzahl des Auftretens des Symbols t im Wort s.
 +  * S<​sup>​n</​sup>​ := { s ∈ S<​sup>​+</​sup>​ | |s| = n } Menge der Wörter über S der Länge n.
 +  * **Konkatenation**:​ Seien s = s<​sub>​1</​sub>​...s<​sub>​n</​sub>​ ∈ S<​sup>​+</​sup>,​ s<​sub>​i</​sub>​ ∈ S, i = 1...n, t = t<​sub>​1</​sub>​...t<​sub>​m</​sub>​ ∈ S<​sup>​+</​sup>,​ t<​sub>​i</​sub>​ ∈ S, i = 1...m. st = s<​sub>​1</​sub>​...s<​sub>​n</​sub>​t<​sub>​1</​sub>​...t<​sub>​m</​sub>​ ∈ S<​sup>​+</​sup>​ heißt Konkatenation von s mit t. 
 +  * L ⊆ S<​sup>​*</​sup>​ heißt **(formale) Sprache** über S.
 +
 +==== Backus-Naur-Form ====
 +  * Formale (Meta-)Sprache zur Beschreibung von formalen Sprachen
 +  * Symbole: ::=, |, {}  ​
  
 ===== Einleitung ===== ===== Einleitung =====
Zeile 6: Zeile 20:
     * diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische Kybernetik ∈ [[http://​de.wikipedia.org/​wiki/​Kybernetik|Kybernetik]] (Wissenschaft von der Funktion komplexer Systeme)     * diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische Kybernetik ∈ [[http://​de.wikipedia.org/​wiki/​Kybernetik|Kybernetik]] (Wissenschaft von der Funktion komplexer Systeme)
   * Funktion endlicher Automaten: Eingaben → (innere) Zustände → Ausgaben   * 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   * Klassifizierung
     * Endliche erkennende Automaten     * Endliche erkennende Automaten
Zeile 14: Zeile 31:
     * 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 ​(endlich) 
-    * S: Zustandsmenge +    * S: Zustandsmenge ​(endlich) 
-    * s<​sub>​0</​sub>:​ Anfangszustand+    * s<​sub>​0</​sub>:​ Anfangszustand ​s<​sub>​0</​sub>​ ∈ S
     * δ: Zustandsübergangsfunktion     * δ: Zustandsübergangsfunktion
       * S x X → S       * S x X → S
-      * δ(s<​sub>​i</​sub>,​ x<​sub>​j</​sub>​) → s<​sub>​k</​sub>​ (Folgezustand zu s<​sub>​i</​sub>​) ​                    ​ +      * δ(s<​sub>​i</​sub>,​ x<​sub>​j</​sub>​) → s<​sub>​k</​sub>​ (Folgezustand zu s<​sub>​i</​sub>​) 
-    * δ<​sup>​*</​sup>:​ Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X<​sup>​*</​sup>​+    ​* F: Menge der Endezustände F ⊆ S 
 +  ​* δ<​sup>​*</​sup>:​ Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X<​sup>​*</​sup>​
       * δ<​sup>​*</​sup>​(s<​sub>​0</​sub>,​ w) ∈ S | w = x<​sub>​1</​sub>,​ x<​sub>​2</​sub>,​ ..., x<​sub>​n</​sub>,​ x<​sub>​i</​sub>​ ∈ X       * δ<​sup>​*</​sup>​(s<​sub>​0</​sub>,​ w) ∈ S | w = x<​sub>​1</​sub>,​ x<​sub>​2</​sub>,​ ..., x<​sub>​n</​sub>,​ x<​sub>​i</​sub>​ ∈ X
       * δ<​sup>​*</​sup>​(s,​ ε) = s | s ∈ S, ε leeres Wort       * δ<​sup>​*</​sup>​(s,​ ε) = s | s ∈ S, ε leeres Wort
       * δ<​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) +  * Sei A = (X, S, s<​sub>​0</​sub>,​ δ, F) ein DEA. L(A) := { w ∈ X<​sup>​*</​sup>​ | δ<​sup>​*</​sup>​(s<​sub>​0</​sub>,​ 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) 
-  * durch endliche ​Automaten ​akzeptierbar/​definierbar,​ falls es einen DEA gibt, der sie akzeptiert+  * Eine Sprache L ist durch einen endlichen ​Automaten definierbar ​(oder **regulär**), falls es einen DEA 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) ===== ===== 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<​sub>​0</​sub>,​ δ, F)   * **Definition**:​ A = (X, S, S<​sub>​0</​sub>,​ δ, F)
-    * X: Eingabealphabet +    * X: Eingabealphabet ​(endlich) 
-    * S: Zustandsmenge+    * S: Zustandsmenge ​(endlich)
     * S<​sub>​0</​sub>:​ Menge der Anfangszustände,​ S<​sub>​0</​sub>​ ⊆ S      * S<​sub>​0</​sub>:​ Menge der Anfangszustände,​ S<​sub>​0</​sub>​ ⊆ S 
     * δ: Zustandsübergangsfunktion     * δ: Zustandsübergangsfunktion
       * 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) ​                    
 +    * 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<​sub>​0</​sub>,​ δ, F) ein NEA. L(A) := { w ∈ X<​sup>​*</​sup>​ | ∃ s<​sub>​0</​sub>​ ∈ S<​sub>​0</​sub>​ : δ<​sup>​*</​sup>​(s<​sub>​0</​sub>,​ 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<​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 =====
 +  * **Definition**:​ A = (X, Y, S, s<​sub>​0</​sub>,​ δ, σ)
 +    * X: Eingabealphabet
 +    * Y: Ausgabealphabet
 +    * S: Zustandsmenge (endlich)
 +    * s<​sub>​0</​sub>:​ Startzustand s<​sub>​0</​sub>​ ⊆ S 
 +    * δ: Zustandsübergangsfunktion S x X → S
 +    * σ: Ausgabefunktion ​   ​
 +  * 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 =====
-  * Skript Herold lesen+  * <​del>​Beispiele aus Vorlesung nochmal machen</​del>​ 
 +  * Aufgaben 3.5.2 machen 
 +  * <​del>​Übung:​ NEA in DEA überführen</​del>​ 
 +  * <​del>​BNF</​del>​ 
 +  * <del>Skript Herold lesen</​del>​ 
 +  * <​del>​Definition reguläre Sprache</​del>​ 
 +  * <​del>​Normalformen</​del>​ 
 +  * <​del>​Kann man Automaten mit LaTeX setzen?</​del>​
  
se/automatentheorie.1228139645.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)