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.

Formální definiceEditovat

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
  • FQ 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.

OdkazyEditovat

Související článkyEditovat

ReferenceEditovat

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

  1. Madhavan Mukund. Finite-state Automata on Infinite Inputs [online]. Madras: SPIC Mathematical Institute, 1996-08 [cit. 2017-01-01]. Kapitola Buchi automata, s. 2. Dostupné online. (anglicky)