Index

Wahlthemen

Automaten (4)


Erkennende Automaten

Die Aufgabe eines Automaten besteht häufig darin, die erfolgte Eingabe auf ihre Korrektheit zu überprüfen. Kriterium dafür, ob ein Eingabewort, d.h. eine Folge von Zeichen aus dem Eingabealphabet, akzeptiert wird, ist das Erreichen eines Endzustands. Die Eingabe der Zeichenfolge beginnt im Anfangszustand s0. Das Wort wird Zeichen für Zeichen gelesen und der Automat durchläuft verschiedene Zustände gemäß der Übergangsfunktion. Der Automat akzeptiert das Eingabewort genau dann, wenn er sich nach dem Einlesen des ganzen Wortes in einem Endzustand befindet; eine Ausgabe muss nicht erfolgen. Einen solchen Automaten bezeichnet man als erkennenden Automaten oder Akzeptor.

Der Angabe des Anfangszustands und der Menge der Endzustände kommt bei erkennenden Automaten eine besondere Bedeutung zu.

Schematische Darstellung als Diagramm:

Diagramm: Erkenneder Automat

Das Eingabewort w = w1w2...wn-1wn, wobei w1, w2, ..., wn-1, wn Zeichen aus dem Eingabealphabet E sind, wird akzeptiert, da nach dem letzten Zeichen ein Endzustand (sF) erreicht ist.


Hinweis

Zur Simulation des erkennenden Automaten kann das Java-Programm "JFlap" verwendet werden. JFlap ist ein Programm zur Simulation verschiedener Automatentypen, das als Applet oder Applikation genutzt werden kann. Man findet die neueste Version von JFlap unter
http://www.jflap.org/
im Internet.


Beispiele
Die folgenden Beispiele akzeptierender Automaten sind so gewählt (und z.T. konstruiert), dass man ihre Eigenschaften kennenlernen kann, ohne die Komplexität realer Automaten in Kauf zu nehmen.

  1. Worterkennung
  2. Ungerade Binärzahlen
  3. Syntaxanalyse bei Pascal
  4. HTML-Syntax
  5. Außergewöhnliche Automaten

[Index] [Zurück/Automaten 3] [Fortsetzung/Automaten 5]


Autor: Jürgen Dehmer
Letzte Änderung: