|
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
o entsprechen den Zuständen des Systems
o Beschreibung des Zustands sollte möglich sein
o Bezeichnung: S0, S1, A, B, ...
o genau ein Startzustand
o ein oder mehrere Endzustande
. Kanten
o jede Kante entspricht einem Eingabesymbol
o Wechsel von \"Si\" zu \"Sj\" wenn a eingegeben wird
o 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 |
