ENDLICHE AUTOMATEN

ENDLICHE AUTOMATEN

1. Einleitung - Was ist ein endlicher Automat ?
2. Erkennender Automat
3. Zustandstabellen
4. Allgemeine endliche Automaten
5. Mustersuche mittels Automaten
6. Programmierung von Automaten
7. 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) 11873lpn96oup8o

end-solange

wenn "Endzustand" erreicht

Eingabe war richtig

sonst pu873l1196ouup

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:

1. Konstruktion des Automaten durch das Suchprogramm

2. 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 pu873l1196ouup

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 pu873l1196ouup

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) 11873lpn96oup8o

end-solange

wenn "Endzustand" erreicht

Eingabe war richtig

sonst pu873l1196ouup

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

Zurü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 pu873l1196ouup

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 pu873l1196ouup

ist ein Fehler aufgetreten (Falle!)

end-wenn

Zurück zum Start!