Endlicher Automat

Endliche Automaten spielen insbesondere beim Parsen von Dokumenten eine wichtige Rolle.

Inhaltsverzeichnis

1 Beschreibung 2 Typen 3 Werkzeuge 4 Siehe auch 5 Weblinks

Beschreibung

Abhängig von seinem Programm besitzt der eine bestimmte endliche Anzahl von Zuständen in denen er sich befinden kann. Beginn befindet er sich in einem speziell Startzustand .

Beim Lesen der Eingabe und Schreiben Ausgabe geht der Automat schrittweise vor wobei in jedem Schritt das jeweils nächste Symbol Eingabewortes liest. Abhängig von diesem Eingabesymbol und momentanen Zustandes produziert er dann in einem eine endliche Folge von Ausgabesymbolen (und erweitert die Ausgabe) und geht in einen neuen über.

Jede durch einen endlichen Automaten erkennbare Sprache ist regulär (vgl. Chomsky-Hierarchie ).

Typen

Welche Möglichkeiten es gibt hängt vom Automaten also von seiner Programmierung ab.

Eine einfachere Variante die man auch als endlicher Akzeptor bezeichnet produziert dagegen keine Ausgabe sondern nach dem vollständigen Lesen der Eingabe entweder einem akzeptierenden oder einem nichtakzeptierenden Zustand. Man also die Gültigkeit eines Eingabe wortes überprüfen d.h. überprüfen ob ein gegebenes Wort in einer Sprache ist oder nicht. wird dies durch den Automaten indem er Startzustand beginnt die einzelnen Buchstaben des Wortes einzulesen und bei jedem den Zustand wechselt (er kann auch im verbleiben). Ist das Ende des Wortes erreicht die Gültigkeit des Wortes am letzten Zustand. der Zustand in der Menge <math>Z_E</math> ( s.u. ) wird das Wort akzeptiert und gehört zur entsprechenden Sprache andernfalls ist das Wort ungültig.

Eine weitere Variante sind die sogenannten ω-Automaten bei denen die Eingabe eine unendliche von Symbolen ist. Bei diesem Automatenmodell wird Akzeptanz üblicherweise durch die Menge der Zustände die unendlich oft angenommen werden. Der griechische ω ( omega ) steht hier für die kleinste unendliche Ordinalzahl .

Weiterhin lassen sich die endlichen Automaten zwei Gruppen aufteilen:

1. Mealy-Automat
2. Moore-Automat

Werkzeuge

• AT&T FSM Library™
• AutoFSM
• Covered
• Exorciser
• Finite State Kernel Creator
• Finite State Machine Editor
• Finite State Machine Explorer
• FSMGenerator
• jrexx-Lab
• Kara
• Nunni FSM Generator
• Qfsm
• Ragel
• WhatOS

Siehe auch

• Kellerautomat
• Turing-Maschine
• Petri-Netz
• Simulation
• Zustandsdiagramm
• Marvin Minsky
• John E. Hopcroft
• Jeffrey D. Ullman
• Raymond J. Carroll
• Anthony D. Long
• Noam Chomsky
• Automatenanalyse
• Abedeckungsanalyse
• Protokollentwicklung
• Markow-Kette

Weblinks

• Skript " Datenverarbeitende Systeme - Allgemeine Informationen" von Helmut Knebl
• Vorlesungsskript " Automaten und Formale Sprachen " von Siegmar Gerber
• Diplomarbeit " Visualisierung endlicher Automaten " von Jürgen Hemminger
• Beschreibung aus der Wissensdatenbank eines Kompetenzzentrums
• Informatikmaterialien " Formale Sprachen und Abstrakte Automaten " von Tino Hempel

Bücher zum Thema Endlicher Automat

Dieser Artikel von Wikipedia unterliegt der GNU FDL.