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
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.
3) Zustandstabellen
- Endliche Automaten
- Statt eines Graphen kann eine
Tabelle für die Beschreibung eines Automaten verwendet werden
- Grundlage für die tabellengesteuerte
Programmierung
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
5) Mustersuche
mittels Automaten - Endliche Automaten
- Bei Textverarbeitung
- Bilddatenverarbeitung
- Digitale Tonaufnahme
Beispiel:
Suche eine Zeichenfolge B[1m] in einer anderen Zeichenfolge A[1n]
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=
Suche 'aabaabb'
Skelettautomat
erweiterter Automat
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]=, , , , }
//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.
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 / .B
Zustandstabellen
Allgemeine endliche
Automaten
Beispiel
Paralleladdierer
Mustersuche mittels
Automaten
Beispiel:
Suche eine Zeichenfolge B[1m] in einer anderen Zeichenfolge A[1n]
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
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]=, , , , }
//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
