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

Odkazy

Související články

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

Externí odkazy

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

Reference

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