Büchi automat - Büchi automaton - Wikipedia

Büchi automat se dvěma státy,

{ displaystyle q_ {0}}

a

{ displaystyle q_ {1}}

, z nichž první je počáteční stav a druhý přijímá. Jeho vstupy jsou nekonečná slova nad symboly

{ displaystyle {a, b }}

. Jako příklad přijímá nekonečné slovo

{ displaystyle (ab) ^ { omega}}

, kde

{ displaystyle x ^ { omega}}

označuje nekonečné opakování řetězce. Odmítá nekonečné slovo

{ displaystyle aaab ^ { omega}}

.

v počítačová věda a teorie automatů, a deterministický Büchi automat je teoretický stroj, který přijímá nebo odmítá nekonečné vstupy. Takový stroj má sadu stavů a přechodovou funkci, která určuje, do kterého stavu by se měl stroj při čtení dalšího vstupního znaku přesunout ze současného stavu. Některé státy přijímají stavy a jeden je počáteční stav. Zařízení přijímá vstup právě tehdy, pokud při načítání vstupu projde nekonečně mnohokrát přijímacím stavem.

A nedeterministický Büchi automat, dále jen a Büchi automat, má přechodovou funkci, která může mít více výstupů, což vede k mnoha možným cestám pro stejný vstup; přijímá nekonečný vstup právě tehdy, když přijímá nějakou možnou cestu. Deterministické a nedeterministické Buči automaty zobecňují deterministické konečné automaty a nedeterministický konečný automat na nekonečné vstupy. Každý z nich je typu ω-automaty. Büchi automaty rozpoznávají ω-běžné jazyky, nekonečná slovní verze běžné jazyky. Jsou pojmenovány podle švýcarského matematika Julius Richard Büchi, který je vynalezl v roce 1962.^[1]

Büchi automaty jsou často používány v kontrola modelu jako automatická teoretická verze vzorce v lineární časová logika.

Formální definice

Formálně, a deterministický Büchi automat je n-tice A = (Q, Σ, δ,q₀,F), který se skládá z následujících komponent:

Q je konečná množina. Prvky Q se nazývají státy z A.
Σ je konečná množina zvaná abeceda z A.
δ:Q × Σ →Q je funkce zvaná přechodová funkce z A.
q₀ je prvek Q, volal počáteční stav z A.
F⊆Q je podmínka přijetí. A přijímá přesně ty běhy, ve kterých je alespoň jeden z nekonečně často se vyskytujících stavůF.

V (nedeterministický) Büchi automat, přechodová funkce δ je nahrazena přechodovým vztahem Δ, který vrací sadu stavů, a jediný počáteční stav q₀ je nahrazen sadou Já počátečních stavů. Obecně se termín Büchi automat bez kvalifikace vztahuje k nedeterministickým Büchi automatům.

Podrobnější formalismus viz také ω-automat.

Vlastnosti uzavření

Sada automatů Büchi je uzavřeno pod následující operace.

Nechť A = (Q_A, Σ, Δ_A,Já_A,F_A) a B = (Q_B, Σ, Δ_B,Já_B,F_B) být Büchi automaty a C = (Q_C, Σ, Δ_C,Já_C,F_C) být a konečný automat.

svaz: Existuje automat Büchi, který rozpoznává jazyk L (A) ∪L (B).

Důkaz: Pokud předpokládáme, w.l.o.g., Q_A∩Q_B je prázdné, pak L (A) ∪L (B) je rozpoznáno automatem Büchi (Q_A∪Q_B, Σ, Δ_A∪Δ_B, Já_A∪Já_B, F_A∪F_B).

Průsečík: Existuje automat Büchi, který rozpoznává jazyk L (A) ∩L (B).

Důkaz: Büchi automat A '= (Q', Σ, Δ ', I', F ') rozpozná L (A) ∩L (B), kde

Q '=Q_A × Q_B × {1,2}
Δ '= Δ₁ ∪ Δ₂
- Δ₁ = {((q_A, q_B, 1), a, (q '_A, q '_Bi)) | (q_A, a, q '_A) ∈Δ_A a (q_B, a, q '_B) ∈Δ_B a pokud q_A∈F_A pak i = 2 else i = 1}
- Δ₂ = {((q_A, q_B, 2), a, (q '_A, q '_Bi)) | (q_A, a, q '_A) ∈Δ_A a (q_B, a, q '_B) ∈Δ_B a pokud q_B∈F_B pak i = 1 else i = 2}
Já = já_A × I_B × {1}
F '= {(q_A, q_B, 2) | q_B∈F_B }

Podle konstrukce, r '= (q_A⁰, q_B⁰, i⁰), (q_A¹, q_B¹, i¹), ... je běh automatu A 'na vstupním slově w pokud r_A= q_A⁰, q_A¹, ... běží A na w a r_B= q_B⁰, q_B¹, ... běží B na w. r_A přijímá a r_B přijímá, pokud r 'je zřetězení nekonečné řady konečných segmentů 1-stavů (stavů s třetí složkou 1) a 2-stavů (stavů s třetí složkou 2) alternativně. Existuje taková řada segmentů r 'pokud r' je přijato A '.

Zřetězení: Existuje automat Büchi, který rozpoznává jazyk L (C) ⋅L (A).

Důkaz: Pokud předpokládáme, w.l.o.g., Q_C∩Q_A je prázdný, pak Büchi automat A '= (Q_C∪Q_A, Σ, Δ ', I', F_A) rozpoznává L (C) ⋅L (A), kde

Δ '= Δ_A ∪ Δ_C ∪ {(q, a, q ') | q'∈I_A a ∃f∈F_C. (q, a, f) ∈Δ_C }
kdybych_C∩F_C je prázdný, pak I '= I_C jinak já '= já_C ∪ já_A

ω-uzávěr: Pokud L (C) neobsahuje prázdné slovo, pak existuje automat Büchi, který rozpoznává jazyk L (C)^ω.

Důkaz: Büchi automat, který rozpoznává L (C)^ω je postavena ve dvou fázích. Nejprve zkonstruujeme konečný automat A 'tak, že A' také rozpozná L (C), ale neexistují žádné příchozí přechody do počátečních stavů A '. Takže A '= (Q_C Q {q_Nový}, Σ, Δ ', {q_Nový},F_C), kde Δ '= Δ_C ∪ {(q_Nový, a, q ') | ∃q∈I_C. (q, a, q ') ∈Δ_C}. Všimněte si, že L (C) = L (A '), protože L (C) neobsahuje prázdný řetězec. Zadruhé postavíme Büchiho automat A ", který rozpozná L (C)^ω přidáním smyčky zpět do počátečního stavu A '. Takže A "= (Q_C Q {q_Nový}, Σ, Δ ", {q_Nový}, {q_Nový}), kde Δ "= Δ '∪ {(q, a, q_Nový) | ∃q'∈F_C. (q, a, q ') ∈Δ'}.

Doplnění:Existuje automat Büchi, který rozpoznává jazyk Σ^ω/LOS ANGELES).

Důkaz: Důkaz je předložen tady.

Rozpoznatelné jazyky

Büchi automaty rozpoznávají ω-běžné jazyky. Pomocí definice ω-regulárního jazyka a výše uvedených uzavíracích vlastností Büchiho automatů lze snadno ukázat, že Büchi automat může být sestaven tak, že rozpozná jakýkoli daný ω-regulární jazyk. Pro konverzaci viz konstrukce ω-regulárního jazyka pro automat Büchi.

Deterministické versus nedeterministické Buči automaty

Nedeterministický automat Büchi, který rozpoznává (0∪1) * 0^ω

Třída deterministických automatů Büchi nestačí k zahrnutí všech regulárních jazyků omega. Zejména neexistuje žádný deterministický Büchi automat, který rozpozná jazyk (0∪1) * 0^ω, který obsahuje přesně slova, ve kterých se 1 vyskytuje jen konečně mnohokrát. Můžeme to prokázat rozporem, že žádný takový deterministický Büchi automat neexistuje. Předpokládejme A je deterministický Büchi automat, který rozpoznává (0∪1) * 0^ω s nastaveným konečným stavem F. A přijímá 0^ω. Tak, A navštíví nějaký stát v F po přečtení nějaké konečné předpony 0^ω, řekněme po i₀th dopis. A také přijímá ω-slovo 0^i₀10^ω. Proto pro některé i₁, za předponou 0^i₀10^i₁ automat navštíví nějaký stát v F. Pokračováním v této konstrukci ω-slovo 0^i₀10^i₁10^i₂... je generováno, což způsobí, že A navštíví nějaký stát v F nekonečně často a slovo není v (0∪1) * 0^ω. Rozpor.

Třídu jazyků rozpoznatelných deterministickými Büchi automaty charakterizuje následující lemma.

Lemma: Jazyk ω je rozpoznatelný podle deterministického Büchiho automatu, pokud se jedná o omezit jazyk některých běžný jazyk.

Důkaz: Na jakýkoli deterministický Büchi automat A lze nahlížet jako na deterministický konečný automat A 'a naopak, protože oba typy automatu jsou definovány jako 5-tice stejných komponent, pouze interpretace podmínky přijetí je odlišná. Ukážeme, že L (A) je mezní jazyk L (A '). Ω-slovo je přijato A, pokud donutí A navštěvovat konečné stavy nekonečně často. pokud A 'přijme nekonečně mnoho konečných předpon tohoto slova ω. Proto je L (A) mezním jazykem L (A ').

Algoritmy

Kontrola modelu konečných stavových systémů lze často převést na různé operace na automatech Büchi. Kromě uzavíracích operací uvedených výše jsou následující užitečné operace pro aplikace automatů Büchi.

Stanovení

Vzhledem k tomu, že deterministické automaty Büchi jsou striktně méně expresivní než nedeterministické automaty, nemůže existovat algoritmus pro určování automatů Büchi. McNaughtonova věta a Stavba Safry poskytnout algoritmy, které mohou převést Büchiho automat na deterministický Mullerův automat nebo deterministické Rabinov automat.^[2]

Kontrola prázdnoty

Jazyk rozpoznávaný automatem Büchi je neprázdný právě tehdy, když existuje konečný stav, který je dosažitelný z počátečního stavu, a leží na cyklu.

Efektivní algoritmus, který dokáže zkontrolovat prázdnotu Büchiho automatu:

Zvažte automat jako a řízený graf a rozložit to na silně připojené komponenty (SCC).
Spusťte vyhledávání (např hloubkové vyhledávání ) zjistit, které SCC jsou dosažitelné z počátečního stavu.
Zkontrolujte, zda existuje netriviální SCC, který je dosažitelný a obsahuje konečný stav.

Každý z kroků tohoto algoritmu lze provádět časově lineárně ve velikosti automatu, proto je algoritmus jasně optimální.

Minimalizace

Algoritmus pro minimalizace nedeterministického konečného automatu také správně minimalizuje Bučiho automat. Algoritmus nezaručuje minimální Bučiho automat^{[je zapotřebí objasnění ]}Algoritmy pro minimalizace deterministického konečného automatu nefunguje pro deterministický Büchi automat.

Varianty

Transformace z jiných modelů popisu na nedeterministické automaty Büchi

Z zobecněné Büchi automaty (GBA)

Více sad stavů v podmínce přijetí lze převést do jedné sady stavů pomocí konstrukce automatů, který je známý jako „počítající konstrukce“. Řekněme A = (Q, Σ, ∆, q₀,{F₁,...,F_n}) je GBA, kde F₁,...,F_n jsou sady přijímajících stavů, pak je ekvivalentní Büchi automat A' = (Q ', Σ, ∆', q '₀, F '), kde

Q '= Q × {1, ..., n}
q '₀ = (q₀,1 )
∆ '= {((q, i), a, (q', j)) | (q, a, q ') ∈ ∆ a pokud q ∈ F_i pak j = ((i + 1) mod n) else j = i}
F '= F₁× {1}

Z Lineární časová logika vzorec: Je uveden překlad z lineárního temporálního logického vzorce do zobecněného Büchiho automatu tady. A výše je uveden překlad z generalizovaného automatu Büchi do automatu Büchi.

Z Mullerovy automaty

Daný Mullerův automat lze transformovat na ekvivalentní Büchiho automat následujícím způsobem konstrukce automatů. Předpokládejme A = (Q, Σ, ∆, Q₀,{F₀,...,F_n}) je Mullerův automat, kde F₀,...,F_n jsou sady přijímajících států. Ekvivalentní Büchi automat je A' = (Q ', Σ, ∆', Q₀, F '), kde

Q '= Q ∪ ∪ⁿ_{i = 0} {i} × F_i × 2^F_i
∆'= ∆ ∪ ∆₁ ∪ ∆₂, kde
- ∆₁ = {(q, a, (i, q ', ∅)) | (q, a, q ') ∈ ∆ a q' ∈ F_i }
- ∆₂= {((i, q, R), a, (i, q ', R')) | (q, a, q ') ∈∆ a q, q' ∈ F_i a pokud R = F_i pak R '= ∅ jinak R' = R∪ {q}}
F '=∪ⁿ_{i = 0} {i} × F_i × {F_i}

A' zachová původní sadu stavů z A a přidává k nim další stavy. Büchi automat A' simuluje Mullerův automat A takto: Na začátku vstupního slova je provedení A' sleduje popravu A, protože počáteční stavy jsou stejné a ∆ 'obsahuje ∆. Na nějaké nedeterministicky zvolené pozici ve vstupním slově, A' rozhodne se skočit do nově přidaných států přechodem v ∆₁. Poté přechody v ∆₂ zkuste navštívit všechny státy F_i a stále roste R. Jednou R se rovná F_i pak se resetuje na prázdnou sadu a ∆₂ zkuste navštívit všechny státy F_i státy znovu a znovu. Takže pokud státy R=F_i jsou pak navštěvovány nekonečně často A' přijímá odpovídající vstup, stejně tak A. Tato konstrukce úzce navazuje na první část důkazu McNaughtonova věta.

Ze struktur Kripke: Nechť dané Kripkeho struktura být definován M = <Q, Já, R, L, AP> kde Q je množina států, Já je množina počátečních stavů, R je vztah mezi dvěma stavy interpretovaný také jako hrana, L je označení pro stát a AP jsou množinou atomových tvrzení, která se tvoříL.

Büchi automat bude mít následující vlastnosti:

{ displaystyle Q _ { text {final}} = Q cup {{ text {init}} }}

{ displaystyle Sigma = 2 ^ {AP}}

{ displaystyle I = {{ text {init}} }}

{ displaystyle F = Q pohár {{ text {init}} }}

{ displaystyle delta = q { overrightarrow {a}} p}

pokud (q, p) patří R a L(p) = A

a init

{ displaystyle { overrightarrow {a}}}

q -li q patří Já a L(q) = A.

Všimněte si však, že existuje rozdíl v interpretaci mezi strukturami Kripke a Büchi automaty. Zatímco první explicitně pojmenuje polaritu každé stavové proměnné pro každý stav, druhý pouze deklaruje aktuální sadu proměnných, které drží nebo nedrží true. Neříká absolutně nic o ostatních proměnných, které by mohly být v modelu přítomny.

Reference

^ Büchi, J. R. (1962). Msgstr "O rozhodovací metodě v omezené aritmetice druhého řádu". Proc. Mezinárodní kongres o logice, metodě a filozofii vědy. 1960. Stanford: Stanford University Press: 425–435. doi:10.1007/978-1-4613-8928-6_23. ISBN 978-1-4613-8930-9.
^ Safra, S. (1988), „O složitosti ω-automatů“, Sborník 29. výročního symposia o základech informatiky (FOCS '88), Washington DC, USA: IEEE Computer Society, str. 319–327, doi:10.1109 / SFCS.1988.21948, S2CID 206559211.

Bakhadyr Khoussainov; Anil Nerode (6. prosince 2012). Teorie automatů a její aplikace. Springer Science & Business Media. ISBN 978-1-4612-0171-7.
Thomas, Wolfgang (1990). Msgstr "Automaty na nekonečných objektech". Ve Van Leeuwen (ed.). Příručka teoretické informatiky. Elsevier. 133–164.

externí odkazy

„Automaty konečného stavu na nekonečných vstupech“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
Vardi, Moshe Y. „An automata-theoretic approach to linear temporal logic“. CiteSeerX 10.1.1.125.8126. Citovat deník vyžaduje | deník = (Pomoc)

[1] Büchi, J. R. (1962). Msgstr "O rozhodovací metodě v omezené aritmetice druhého řádu". Proc. Mezinárodní kongres o logice, metodě a filozofii vědy. 1960. Stanford: Stanford University Press: 425–435. doi:10.1007/978-1-4613-8928-6_23. ISBN 978-1-4613-8930-9.

[2] Safra, S. (1988), „O složitosti ω-automatů“, Sborník 29. výročního symposia o základech informatiky (FOCS '88), Washington DC, USA: IEEE Computer Society, str. 319–327, doi:10.1109 / SFCS.1988.21948, S2CID 206559211.

[1]

[2]