Mullerův automat

Mullerův automat je v teorii automatů ω-automat, tedy konečný automat, který rozpoznává slova nekonečné délky. Automat akceptuje nekonečné slovo, pokud všechny jeho stavy, které byly během výpočtu navštíveny nekonečněkrát patří do množiny koncových stavů. Automat je pojmenován po americkém matematikovi a informatikovi Davidu E. Mullerovi, který ho vynalezl v roce 1963.

Formální definice

Deterministický Mullerův automat je pětice A = (Q,Σ,δ,q₀,F) skládající se z těchto komponent:

• Q je konečná množina stavů
• Σ je konečná množina znaků – abeceda automatu A
• δ: Q × Σ → Q je přechodová funkce automatu A
• q₀ je prvek množiny Q – začáteční stav automatu A
• F ⊆ P(Q) je množina koncových stavů – podmnožina potenční množiny množiny Q

Nedeterministický Mullerův automat je podobný deterministickému, ale přechodová funkce Δ odkazuje na množinu stavů (místo jednoho konkrétního stavu) a začáteční stav q₀ je nahrazen množinou začátečních stavů I. Obecně pojem Mullerův automat bez přívlastku označuje právě nedeterministický Büchiho automat.

Reference

V tomto článku byl použit překlad textu z článku Muller automaton na anglické Wikipedii.