Mullerův automat - Muller automaton - Wikipedia

v teorie automatů, a Mullerův automat je typ ω-automat. Podmínka přijetí odděluje Mullerův automat od ostatních ω-automatů. Mullerův automat je definován pomocí Mullera podmínka přijetí, tj. množina všech států navštěvovaných nekonečně často, musí být prvkem akceptační množiny. Deterministické i nedeterministické Mullerovy automaty rozpoznávají ω-běžné jazyky. Jsou pojmenovány po David E. Muller, Američan matematik a počítačový vědec, který je vynalezl v roce 1963.^[1]

Formální definice

Formálně, a deterministický Mullerův automat je n-tice A = (Q, Σ, δ,q₀,F), který se skládá z následujících informací:

• Q je konečná množina. Prvky Q se nazývají státy z A.
• Σ je konečná množina zvaná abeceda z A.
• δ:Q × Σ →Q je funkce zvaná přechodová funkce z A.
• q₀ je prvek Q, nazvaný počáteční stav.
• F je sada množin stavů. Formálně, F ⊆ P(Q) kde P(Q) je výkonová sada z Q. F definuje podmínka přijetí. A přijímá přesně ty běhy, ve kterých je množina nekonečně často se vyskytujících stavů prvkemF

V nedeterministický Mullerův automat, přechodová funkce δ je nahrazena přechodovým vztahem Δ, který vrací sadu stavů a ​​počáteční stav je q₀ je nahrazen sadou počátečních stavů Q₀. Obecně Mullerův automat odkazuje na nedeterministický Mullerův automat.

Pro podrobnější formalismus se podívejte na ω-automat.

Ekvivalence s jinými ω-automaty

Mullerovy automaty jsou stejné expresivní tak jako paritní automaty, Rabin Automata, Streett automaty a nedeterministické Büchi automaty, abych zmínil některé, a přísněji expresivnější než deterministické Büchi automaty. Ekvivalenci výše uvedených automatů a nedeterministických Mullerových automatů lze velmi snadno ukázat, protože podmínky přijetí těchto automatů lze emulovat pomocí podmínky přijetí Mullerových automatů. McNaughtonova věta demonstruje rovnocennost nedeterministického Büchiho automatu a deterministického Mullerova automatu. Deterministický a nedeterministický Mullerův automat jsou tedy ekvivalentní, pokud jde o jazyky, které mohou přijmout.

Transformace na nedeterministický Mullerův automat

Následuje seznam konstrukce automatů který transformuje typ ω-automatů na nedeterministický Mullerův automat.

Z Büchi automat

Li ${ displaystyle B}$ je množina konečných stavů v automatu Büchi se sadou stavů ${ displaystyle Q}$, můžeme sestrojit Mullerovy automaty se stejnou sadou stavů, přechodovou funkcí a počátečním stavem s Mullerovým přijetím podmínky jako F = {X | X ∈ 2^Q ∧ X ∩ B ≠ ${ displaystyle emptyset}$}

Z automatu Rabin / Parity automat

Podobně i rabínské podmínky ${ displaystyle (E_ {j}, F_ {j})}$ lze emulovat vytvořením sady přijetí v automatech Muller jako všechny sady v ${ displaystyle F subseteq 2 ^ {Q}}$ které uspokojí ${ displaystyle F cap E_ {j} = emptyset land F cap F_ {j} neq emptyset}$, pro některé j. Toto zahrnuje i případ Parity automatu, protože podmínku přijetí parity lze snadno vyjádřit jako Rabinovu podmínku přijetí.

Z Streettova automatu

Podmínky Streett ${ displaystyle (E_ {j}, F_ {j})}$ lze emulovat vytvořením sady přijetí v automatech Muller jako všechny sady v ${ displaystyle F subseteq 2 ^ {Q}}$ které uspokojí ${ displaystyle F cap E_ {j} = emptyset rightarrow F cap F_ {j} = emptyset}$, pro všechny j.

Transformace na deterministický Mullerův automat

Spojení dvou deterministických mullerových automatů

Z Büchi automatu

McNaughtonova věta poskytuje postup pro transformaci nedeterministického Büchiho automatu na deterministický Mullerův automat.

Reference

• Automaty na nekonečných slovech Prezentace pro výuku od Paritosh K. Pandya.
• Yde Venema (2008) Přednášky o modálním μ-kalkulu; the Verze 2006 byl představen na 18. evropské letní škole logiky, jazyka a informací