www.wikidata.de-de.nina.az

Muller Automat Den bezeichnet in der Automatentheorie ein 1963 von David E Muller vorgestelltes Konzept eines ω Automate

Muller-Automat

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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Den Muller Automat bezeichnet in der Automatentheorie ein 1963 von David E Muller vorgestelltes Konzept eines w Automaten Dieser Typ deterministisch wie nichtdeterministisch hat die gleiche Ausdrucksstarke wie nichtdeterministische Buchi Automaten Im Gegensatz dazu wird die Menge der unendlich oft besuchten Zustande genau festgelegt was prazisere Aussagen zum Akzeptanzverhalten zulasst Inhaltsverzeichnis 1 Muller Automat zur Worterkennung 1 1 Akzeptanzverhalten 2 Muller Automat zur Baumerkennung 3 LiteraturMuller Automat zur Worterkennung BearbeitenEin nicht deterministischer Muller Automat hat die Form A Q S q 0 D F displaystyle A Q Sigma q 0 Delta mathcal F nbsp Hierbei gilt Q displaystyle Q nbsp ist die Menge der Zustande q 0 Q displaystyle q 0 in Q nbsp ist der Startzustand D Q S Q displaystyle Delta subseteq Q times Sigma times Q nbsp ist die Transitionsrelation F 2 Q displaystyle mathcal F subseteq 2 Q nbsp ist die Tafel d h F F 1 F k displaystyle mathcal F lbrace F 1 dots F k rbrace nbsp fur bestimmte Mengen F 1 F k Q displaystyle F 1 dots F k subseteq Q nbsp Fur deterministische Automaten ist die Transitionsrelation eine Funktion d Q S Q displaystyle delta colon Q times Sigma to Q nbsp hat also eindeutige Bilder und der Automat damit eindeutige Laufe Die Muller akzeptierbaren w Sprachen sind die booleschen Kombinationen der deterministisch Buchi erkennbaren w Sprachen Jeder deterministische Buchi Automat kann als Muller Automat ausgedruckt werden Die Klasse der Muller erkennbaren w Sprachen ist also unter booleschen Operationen abgeschlossen Um zu einem Muller Automaten einen nichtdeterministischen Buchi Automaten zu konstruieren lasst man den Buchi Automaten raten welches F i F displaystyle F i in mathcal F nbsp die richtige Menge ist die unendlich oft durchlaufen werden muss und von wann an die Durchlaufe beginnen mussen Akzeptanzverhalten Bearbeiten Ein Lauf r displaystyle rho nbsp ist erfolgreich wenn Inf r F displaystyle operatorname Inf rho in F nbsp wobei Inf r q Q q erscheint unendlich oft in r displaystyle operatorname Inf rho lbrace q in Q mid q text erscheint unendlich oft in rho rbrace nbsp Dies nennt man die Muller Akzeptierung A displaystyle A nbsp akzeptiert ein Wort a displaystyle alpha nbsp wenn ein Lauf von A displaystyle A nbsp auf a displaystyle alpha nbsp erfolgreich ist Die Muller Bedingung lautet Inf r F i displaystyle operatorname Inf rho F i nbsp fur ein i 1 k displaystyle i 1 dots k nbsp Es muss zur Akzeptierung also eine bestimmte Menge F i displaystyle F i nbsp aus der Tafel F displaystyle mathcal F nbsp unendlich oft komplett durchlaufen werden Muller Automat zur Baumerkennung BearbeitenEin Muller Baumautomat hat das Format A Q S q 0 D F displaystyle A Q Sigma q 0 Delta mathcal F nbsp wobei D Q S Q Q displaystyle Delta subseteq Q times Sigma times Q times Q nbsp und F displaystyle mathcal F nbsp eine Menge von Teilmengen von Q displaystyle Q nbsp ist Ein Muller Baumautomat akzeptiert einen Baum t displaystyle t nbsp wenn es einen Lauf r displaystyle rho nbsp von A displaystyle A nbsp auf t displaystyle t nbsp gibt so dass auf jedem Pfad von r displaystyle rho nbsp die Menge M displaystyle M nbsp der unendlich oft vorkommenden Zustande ein Element von F displaystyle F nbsp ist Literatur BearbeitenWolfgang 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 Abgerufen von https de wikipedia org w index php title Muller Automat amp oldid 201718631