Mullerův automat

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

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,Σ,δ,q0,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 * q0 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 q0 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.

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top