Büchiho automat

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.^[1] Automat je pojmenován po švýcarském matematikovi Juliovi Richardu Büchim, který ho vynalezl v roce 1962.

Deterministický Büchiho 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
• q₀ 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 q₀ 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.

• Co-Büchiho automat
• Omega-regulární jazyk

• Obrázky, zvuky či videa k tématu Büchiho automat na Wikimedia Commons

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