Büchiho automat je v teorii automatů ω-automat, který rozšiřuje koncept konečného automatu pro nekonečné vstupy (slova nekonečné délky). Büchiho automat akceptuje slovo, pokud existuje běh automatu, který navštíví alespoň jeden koncový stav nekonečněkrát. Automat je pojmenován po švýcarském matematikovi Juliovi Richardu Büchim, který ho vynalezl v roce 1962.
Formální definice Deterministický Büchiho 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 q0 je prvek množiny Q – začáteční stav automatu A F ⊆ Q je množina koncových stavů; automat akceptuje slovo, pokud je alespoň jeden z koncových stavů navštíven nekonečněkrát
Nedeterministický Büchiho 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 Büchiho automat bez přívlastku označuje právě nedeterministický Büchiho automat.
Odkazy
Související články Co-Büchiho automat Omega-regulární jazyk
Externí odkazy
Reference
Kategorie:Konečné automaty