Den Muller-Automat bezeichnet in der Automatentheorie ein 1963 von David E. Muller vorgestelltes Konzept eines ω-Automaten. Dieser Typ – deterministisch wie nichtdeterministisch – hat die gleiche Ausdrucksstärke wie nichtdeterministische Büchi-Automaten. Im Gegensatz dazu wird die Menge der unendlich oft besuchten Zustände genau festgelegt, was präzisere Aussagen zum Akzeptanzverhalten zulässt.

Muller-Automat zur Worterkennung

Bearbeiten

Ein nicht-deterministischer Muller-Automat hat die Form  . Hierbei gilt:

  •   ist die Menge der Zustände,   ist der Startzustand
  •   ist die Transitionsrelation
  •   ist die Tafel, d. h.   für bestimmte Mengen  

Für deterministische Automaten ist die Transitionsrelation eine Funktion  , hat also eindeutige Bilder und der Automat damit eindeutige Läufe.

Die Muller-akzeptierbaren ω-Sprachen sind die booleschen Kombinationen der deterministisch-Büchi-erkennbaren ω-Sprachen. Jeder deterministische Büchi-Automat kann als Muller-Automat ausgedrückt werden. Die Klasse der Muller-erkennbaren ω-Sprachen ist also unter booleschen Operationen abgeschlossen. Um zu einem Muller-Automaten einen (nichtdeterministischen) Büchi-Automaten zu konstruieren, lässt man den Büchi-Automaten raten, welches   die richtige Menge ist, die unendlich oft durchlaufen werden muss, und von wann an die Durchläufe beginnen müssen.

Akzeptanzverhalten

Bearbeiten

Ein Lauf   ist erfolgreich, wenn  , wobei  . Dies nennt man die Muller-Akzeptierung.

  akzeptiert ein Wort  , wenn ein Lauf von   auf   erfolgreich ist.

Die Muller-Bedingung lautet:   für ein  

Es muss zur Akzeptierung also eine bestimmte Menge   aus der Tafel   unendlich oft komplett durchlaufen werden.

Muller-Automat zur Baumerkennung

Bearbeiten

Ein Muller-Baumautomat hat das Format  , wobei   und   eine Menge von Teilmengen von   ist.

Ein Muller-Baumautomat akzeptiert einen Baum  , wenn es einen Lauf   von   auf   gibt, so dass auf jedem Pfad von   die Menge   der unendlich oft vorkommenden Zustände ein Element von   ist.

Literatur

Bearbeiten
  • Wolfgang Thomas: Automata on Infinite Objects. In: Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science. Band B: Formal Models and Semantics. Elsevier Science Publishers u. a., Amsterdam u. a. 1990, ISBN 0-444-88074-7, S. 133–164.