Endliche automaten

ENDLICHE AUTOMATEN Einleitung - Was ist ein endlicher Automat ? Erkennender Automat Zustandstabellen Allgemeine endliche Automaten Mustersuche mittels Automaten Programmierung von Automaten FOLIEN 1) Einleitung - Endliche Automaten Ein endlicher Automat ist ein Modell zur Beschreibung von sogenannten zustandsabhängigen Systemen. Merkmale: System befindet sich immer in einem bestimmten Zustand (es gibt endlich viele unterschiedliche Zustände) Es gibt Eingaben, die bewirken, dass das System seinen Zustand wechselt Ein Automat verarbeitet Symbole aus dem Eingabealphabet (endlich viele) Regeln, welcher Folgezustand aufgrund des aktuellen Zustandes und des nächsten Eingabesymbols eingenommen werden soll Graphische Darstellung durch sogenannte Zustandsdiagramme endliche Automaten entsprechen einer regulären Grammatik (links - Hilfssymbol; rechts - Grundsymbol oder Hilfssymbol) es gibt 2 Arten von endlichen Automaten: Allgemeine Automaten Erkennende Automaten Zurück zum Start! 2) Erkennender Automat - Endliche Automaten Beispiel Beispiel: Erkenne eine Festkommazahl Erlaubt sind: 3.14 +.15 -.3 +5.987 -0.

321 Eingangsalphabet: Zahlen 0-9, +, -, . Grundsätzlicher Algorithmus (vom Startzustand beginnend) solange Eingabesymbol vorhanden entsprechenden Folgezustand einnehmen (aufgrund des aktuellen Zustandes + Eingabesymbol) end-solange wenn "Endzustand" erreicht Eingabe war richtig sonst Eingabe war falsch end-wenn Reguläre Grammatik Jedem Automat entspricht eine reguläre Grammatik und umgekehrt. Beispiel (entspricht dem ersten Beispiel) S -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B S -> +D / -D A -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B / (Ende) B -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C C -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C / (Ende) D -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B Beispiel: +.

15 S -> +D -> +.B -> +.1C -> +.15C -> +.15 (Ende) Zustandsdiagramm (Transitionsgraph) gerichteter Graph Knoten entsprechen den Zuständen des Systems Beschreibung des Zustands sollte möglich sein Bezeichnung: S0, S1, A, B, ..

. genau ein Startzustand ein oder mehrere Endzustande Kanten jede Kante entspricht einem Eingabesymbol Wechsel von "Si" zu "Sj" wenn a eingegeben wird Mehrfachkanten erlaubt unvollständiger Automat: es gibt Knoten wo Kanten fehlen bei absichtlichen Fehlern: fehlende Kanten führen zu Fehlerzustand (Falle) allgemeine endliche Automaten erzeugen auf Grund eines Eingabesymbols und abhängig vom momentanten Zustand ein bestimmtes Ausgabesymbol und nehmen darauf den Folgezustand ein. Zurück zum Start! 3) Zustandstabellen - Endliche Automaten Statt eines Graphen kann eine Tabelle für die Beschreibung eines Automaten verwendet werden Grundlage für die tabellengesteuerte Programmierung  Zurück zum Start! 4) Allgemeine endliche Automaten - Endliche Automaten Zusätzlich zum Analysieren einer Eingabe Ausführen von semantischen Aktionen Beispiel Paralleladdierer Zustände: S .. Startzustand (ohne Übertrag) U ..

Übertrag Zurück zum Start! 5) Mustersuche mittels Automaten - Endliche Automaten Bei Textverarbeitung Bilddatenverarbeitung Digitale Tonaufnahme Beispiel: Suche eine Zeichenfolge B[1...m] in einer anderen Zeichenfolge A[1...

n] Primitive Lösung for ( i=1; (i<=m)&&(A[j]==B[k]; j++,k++); if(k==m+1) gefunden=1; } Aufwand: n*m Schritte Suche mittels Automat Aufwand: n+m Schritte Suche erfolgt in 2 Schritten: Konstruktion des Automaten durch das Suchprogramm Eigentliche Suche mittels Automat E={a,b} Suche "aabaabb" Skelettautomat   erweiterter Automat  Zurück zum Start! 6) Programmierung von Automaten - Endliche Automaten Die Programme beziehen sich auf die Zustandstabelle in Punkt 3! Programmgesteuert Pseudocode: Zustand = S // Startzustand solange (Eingabesymbol <> Ende) case Zustand wenn S: case Eingabesymbol wenn Ziffer: Zustand A wenn Punkt: Zustand B wenn +/-: Zustand D wenn A: case Eingabesymbol wenn Ziffer: Zustand A wenn Punkt: Zustand B wenn B: case Eingabesymbol wenn Ziffer: Zustand C . . . end-case end-solange   wenn (Zustand = A oder Zustand = C) alles in Ordnung sonst ist ein Fehler aufgetreten (möglicherweise Falle einbauen!) end-wenn Semantische Aktionen können im jeweiligen CASE-Zweig realisiert werden. Vorteile: sehr leicht verständlich für Speziallösungen geeignet Nachteile: umfangreicher Programmcode jeder Automat ist neu zu programmieren   Tabellengesteuert Die Funktion des Automaten wird mit Hilfe von zweidimensionalen Arrays verwirklicht, wobei die Elemente die jeweiligen Folgezustände enthalten. Definitionen der Konstanten (Zustände und Eingabesymbole) z.

B. S = 0; A = 1; B = 2; C = 3; D = 4; Ziffer = 0; Punkt = 1; +/- = 2; ZustandsTab[][4]={ {A, B, D}, {A, B, -}, {C, -, -}, {C, -, -}, {A, B, -}} //Tabellendefinition Pseudocode Zustand = S solange (Eingabesymbol <> Ende) Zustand = ZustandsTab[Zustand][Eingabesymbol] end-solange   wenn (Zustand = A) alles in Ordnung sonst ist ein Fehler aufgetreten (Falle!) end-wenn Semantische Aktionen werden mit Hilfe eines Zusatzes über die gewünschte Aktion beim Element gespeichert. Dieser Zusatz ist entweder eine Zahl, die die Aktion bezeichnet, oder ein Zeiger auf die gewünschte Funktion.Zurück zum Start! FOLIEN Endliche AUTOMATEN Erkennender Automat Zustandsdiagramm Eingangsalphabet: Zahlen 0-9, +, -, . Grundsätzlicher Algorithmus solange Eingabesymbol vorhanden entsprechenden Folgezustand einnehmen (aufgrund des aktuellen Zustandes + Eingabesymbol) end-solange wenn "Endzustand" erreicht Eingabe war richtig sonst Eingabe war falsch end-wenn Reguläre Grammatik S -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .B S -> +D / -D A -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .

B / (Ende) B -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C C -> 0C / 1C / 2C / 3C / 4C / 5C / 6C / 7C / 8C / 9C / (Ende) D -> 0A / 1A / 2A / 3A / 4A / 5A / 6A / 7A / 8A / 9A / .BZurück zum Start! Zustandstabellen   Allgemeine endliche Automaten Beispiel Paralleladdierer Zurück zum Start! Mustersuche mittels Automaten Beispiel: Suche eine Zeichenfolge B[1...m] in einer anderen Zeichenfolge A[1..

.n] Primitive Lösung for ( i=1; (i<=m)&&(A[j]==B[k]; j++,k++); if(k==m+1) gefunden=1; } Aufwand: n*m Schritte Suche mittels Automat Aufwand: n+m Schritte Suche "aabaabb" Skelettautomat   erweiterter Automat  Zurück zum Start! Programmierung von Automaten Programmgesteuert Pseudocode: Zustand = S // Startzustand solange (Eingabesymbol <> Ende) case Zustand wenn S: case Eingabesymbol wenn Ziffer: Zustand A wenn Punkt: Zustand B wenn +/-: Zustand D wenn A: case Eingabesymbol wenn Ziffer: Zustand A wenn Punkt: Zustand B . . . end-case end-solange   wenn (Zustand = A oder Zustand = C) alles in Ordnung sonst ist ein Fehler aufgetreten (möglicherweise Falle einbauen!) end-wenn   Tabellengesteuert Definitionen der Konstanten (Zustände und Eingabesymbole) S = 0; A = 1; B = 2; C = 3; D = 4; Ziffer = 0; Punkt = 1; +/- = 2; ZustandsTab[][4]={ {A, B, D}, {A, B, -}, {C, -, -}, {C, -, -}, {A, B, -}} //Tabellendefinition Pseudocode Zustand = S solange (Eingabesymbol <> Ende) Zustand = ZustandsTab[Zustand][Eingabesymbol] end-solange   wenn (Zustand = A) alles in Ordnung sonst ist ein Fehler aufgetreten (Falle!) end-wenn Zurück zum Start!

Suchen artikel im kategorien
Schlüsselwort    Kategorien    - kategorien - astronomiebiographienbiologiechemiedeutschenglischfranzosischgeographiegeschichtehauswirtschaftinformatikitalienischkunstlateinliteraturmathematikmusikphilosophiephysikpolitikpsychologierechtsozialkundesporttechnikwirtschaft	•  Zusammenfassung Der Vorleser  •  sachtextanalyse  •  interpretation zwist  •  Fabel interpretation  •  literarische charakteristik  •  interpretation bender heimkehr  •  felix lateinbuch  •  interpretation der taucher von schiller  •  textbeschreibung  •  charakterisierung eduard selicke

Anmerkungen: * Name: * Email: URL: * Diskussion: (NO HTML)

| impressum | datenschutz