Co-Büchi automat - Co-Büchi automaton
![]() | tento článek ne uvést žádný Zdroje.Červenec 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v teorie automatů, a co-Büchi automat je varianta Büchi automat. Jediným rozdílem je podmínka přijetí: automat Co-Büchi přijímá nekonečné slovo pokud existuje běh, takže všechny stavy vyskytující se v běhu nekonečně často jsou v konečném stavu . Naproti tomu a Büchi automat přijímá slovo pokud existuje běh, tak, že alespoň jeden stav se v sadě konečných stavů vyskytuje nekonečně často .
(Deterministické) Co-Büchi automaty jsou přísně slabší než (nedeterministické) Büchi automaty.
Formální definice
Formálně, a deterministický co-Büchi automat je n-tice který se skládá z následujících komponent:
- je konečná množina. Prvky se nazývají státy z .
- je konečná množina zvaná abeceda z .
- je přechodová funkce z .
- je prvek , nazvaný počáteční stav.
- je konečný stav nastaven. přijímá přesně ta slova s během , ve kterém jsou všechny nekonečně často se vyskytující stavy v jsou v .
V nedeterministický co-Büchi automat, přechodová funkce je nahrazen přechodovým vztahem . Počáteční stav je nahrazen počátečním stavem . Obecně se termín co-Büchi automat vztahuje k nedeterministickému co-Büchi automatu.
Podrobnější formalismus viz také ω-automat.
Podmínka přijetí
Podmínka přijetí automatu co-Büchi je formálně
Podmínka přijetí Büchi je doplňkem podmínky přijetí Büchi:
Vlastnosti
Co-Büchi automaty jsou uzavřeny spojením, průnikem, projekcí a determinizací.