Automat Büchi

$Automat$ Büchi z dwoma stanami, z których , a drugi $.$ Jego dane wejściowe to nieskończone słowa nad symbolami. ${\ Displaystyle \ {a, b \}}$ . $przykład$ przyjmuje $oznacza$ , gdzie Odrzuca nieskończone słowo $\ Displaystyle aaab ^ {\ omega}}$ .

W informatyce i teorii automatów deterministyczny automat Büchiego jest teoretyczną maszyną, która przyjmuje lub odrzuca nieskończone dane wejściowe. Taka maszyna ma zestaw stanów i funkcję przejścia, która określa, do jakiego stanu maszyna powinna przejść ze swojego obecnego stanu, gdy odczytuje następny znak wejściowy. Niektóre stany akceptują stany, a jeden stan jest stanem początkowym. Maszyna akceptuje dane wejściowe wtedy i tylko wtedy, gdy podczas odczytywania danych wejściowych przejdzie przez stan akceptacji nieskończenie wiele razy.

Niedeterministyczny automat Büchiego , później nazywany po prostu automatem Büchiego , ma funkcję przejścia, która może mieć wiele wyjść, prowadząc do wielu możliwych ścieżek dla tego samego wejścia; akceptuje nieskończone dane wejściowe wtedy i tylko wtedy, gdy akceptowana jest jakaś możliwa ścieżka. Deterministyczne i niedeterministyczne automaty Büchiego uogólniają deterministyczne automaty skończone i niedeterministyczne automaty skończone na nieskończone wejścia. Każdy z nich jest rodzajem ω-automatów . Automaty Büchi rozpoznają języki regularne ω , nieskończoną wersję słowną języków regularnych . Zostały nazwane na cześć szwajcarskiego matematyka Juliusa Richarda Büchiego , który wynalazł je w 1962 roku.

Automaty Büchiego są często używane w sprawdzaniu modeli jako teoretyczno-automatyczna wersja formuły w liniowej logice czasowej .

Definicja formalna

₀ Formalnie deterministyczny automat Büchiego jest krotką A = ( Q , Σ, δ, q , F ), która składa się z następujących składowych:

• Q jest skończonym zbiorem . Elementy Q nazywane są stanami A .
• Σ jest skończonym zbiorem zwanym alfabetem A .
• δ: Q × Σ → Q jest funkcją, zwaną funkcją przejścia A .
• ₀ q jest elementem Q , zwanym stanem początkowym A .
• F ⊆ Q jest warunkiem akceptacji . A akceptuje dokładnie te przebiegi, w których przynajmniej jeden z nieskończenie często występujących stanów jest w F .

₀ W ( niedeterministycznym ) automacie Büchiego funkcja przejścia δ jest zastępowana relacją przejścia Δ, która zwraca zbiór stanów, a pojedynczy stan początkowy q jest zastępowany przez zbiór I stanów początkowych. Ogólnie rzecz biorąc, termin automat Büchiego bez kwalifikatora odnosi się do niedeterministycznych automatów Büchiego.

Aby zapoznać się z bardziej wszechstronnym formalizmem, zobacz także ω-automat .

Właściwości zamknięcia

Zbiór automatów Büchiego jest domknięty pod następującymi operacjami.

Niech ${\ Displaystyle \ scriptstyle A = (Q_ {A}, \ Sigma, \ Delta _ {A}, I_ {A}, {F} _ {A})}$ i ${\ Displaystyle \ scriptstyle B = (Q_ {B}, \ Sigma, \ Delta _ {B}, I_ {B} {F} _ {B})}$ być automatami Büchi i ${\ Displaystyle \ scriptstyle C = (Q_ {C}, \ Sigma, \ Delta _ {C},I_{C},{F}_{C})}$ będzie automatem skończonym .

• Unia : Istnieje automat Büchi ${\ Displaystyle \ scriptstyle L (A) \ cup L (B).}$ który rozpoznaje język

$.$ Jeśli , że wlog jest ${\ Displaystyle \ scriptstyle L (A) \ kubek L (B)}$ pusty jest rozpoznawany przez automat Büchi ${\ Displaystyle \ scriptstyle (Q_ {A} \ kubek Q_ {B}, \ Sigma, \ Delta _ {A} \ kubek \ Delta _ {B}, I_ {A} \ kubek I_ {B}, {F} _ {A}\cup {F}_{B}).}$

• Przecięcie : Istnieje automat Büchi, który rozpoznaje język ${\ Displaystyle \ scriptstyle L (A) \ cap L (B).}$

Dowód: automat Büchi rozpoznaje ZA $\ Displaystyle \ scriptstyle A' = (Q', \ Sigma, \ Delta ', I', F')}$${\ Displaystyle \ scriptstyle L (A) \ cap L (B)}$ gdzie

• ${\ Displaystyle \ scriptstyle Q '= Q_ {A} \ razy Q_ {B} \ razy \ {1,2 \}}$
• ${\ Displaystyle \ scriptstyle \ Delta '= \ Delta _ {1} \ kubek \ Delta _ {2}}$
  • $\ Displaystyle \ scriptstyle \ Delta _{1}=\{((q_{A},q_{B},1),a,(q'_{A},q'_{B},i))|(q_{A},a ,q'_{A})\in \Delta _{A}{\text{ i }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ a if }}q_{A}\in F_{A}{\text{ then }}i=2{\text{ else }}i=1\}}$
  • ${\ Displaystyle \ scriptstyle \ Delta _{2}=\{((q_{A},q_{B},2),a,(q'_{A},q'_{B},i))|(q_{A},a ,q'_{A})\in \Delta _{A}{\text{ i }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ a if }}q_{B}\in F_{B}{\text{ then }}i=1{\text{ else }}i=2\}}$
• ${\ Displaystyle \ scriptstyle I' = I_ {A} \ razy I_ {B} \ razy \ {1 \}}$
• ${\ Displaystyle \ scriptstyle F '= \ {(q_ {A}, q_ {B}, 2) | q_ {B} \ w F_ {B} \}}$

Z konstrukcji ${\ Displaystyle \ scriptstyle r' = (q_ {A} ^ {0}, q_ { B}^{0},i^{0}),(q_{A}^{1},q_{B}^{1},i^{1}),\dots } jest przebiegiem automatu$ A' na słowie wejściowym w jeśli jest uruchamiany ${\ Displaystyle \ scriptstyle r_ {A} = q_ {A} ^ {0}, q_ {A} ^ {1}, \ kropki$ } A na w i ${\ Displaystyle \ scriptstyle r_ {B} = q_ {B} ^ {0}, q_ {B} ^ {1}, \ kropki}$ jest uruchamiane z B na w . ${\ displaystyle \ scriptstyle r_ {A}}$$akceptuje$ i akceptuje, jeśli r 'jest konkatenacją nieskończonej serii skończonych segmentów stanów 1 (stany z 1) i 2-stany (stany z trzecią składową 2) alternatywnie. Istnieje taki ciąg odcinków r', jeśli r' jest akceptowane przez A'.

• Konkatenacja : Istnieje automat Büchi, który rozpoznaje język ${\ Displaystyle \ scriptstyle L (C) \ cdot L (A).}$

Dowód: Jeśli założymy, $to$$_$ , jest automat ⋅ ${\ Displaystyle \ scriptstyle L (C) \ cdot L (A)}$ gdzie

• ${\ Displaystyle \ scriptstyle \ Delta '= \ Delta _ {A} \ kubek \ Delta _ {C} \ kubek \ {(q, a, q ') | q '\ w I_{A}{\text{ i }}\istnieje f\w F_{C}.(q,a,f)\in \Delta _{C}\}}$
• ${\ Displaystyle \ scriptstyle {\ tekst {jeśli}} I_ {C} \ czapka F_ {C} {\ tekst {$

• Jeśli $) ^ {\ omega}.}$ zawiera pustego słowa, to istnieje automat Büchi, $który$ zamknięcie :

$Dowód$ : automat Büchi, który rozpoznaje, konstruowany w dwóch $nie$ konstruujemy automat skończony A 'taki, że A' również rozpoznaje, nadchodzących przejść do stanów początkowych A' Więc ${\ Displaystyle \ scriptstyle A' = (Q_ {C} \ puchar \ {q_ {\ text { nowy}}\},\Sigma ,\Delta ',\{q_{\text{nowy}}\},F_{C}),}$ gdzie ${\ Displaystyle \ scriptstyle \ Delta '= \ Delta _ {C} \ puchar \ {(q _ {\ tekst {nowy}}, a, q') | \ istnieje q \ w I_ {C}. (q, a, q ') \ in \ Delta _ {C} \}.}$ Zauważ, że ${\ Displaystyle \ scriptstyle L (C) = L (A')},$ ponieważ ${\ displaystyle \scriptstyle L(C)}$ nie zawiera pustego łańcucha. Po drugie, skonstruujemy automat Büchi A”, który rozpoznaje, dodając pętlę z powrotem do stanu początkowego A'. L ( do $}$${\ Displaystyle \ scriptstyle A'' = (Q_ {C} \ puchar \ {q_ {\ tekst {nowy}} \},\Sigma ,\Delta '',\{q_{\text{nowy}}\},\{q_{\text{nowy}}\})} ,$ gdzie ${\ Displaystyle \ scriptstyle \ Delta '' = \ Delta '\ kubek \ {(q, a, q_ { \text{new}})|\exists q'\in F_{C}.(q,a,q')\in \Delta '\}.} Dopełnienie: Istnieje automat Büchi,$

• który rozpoznaje język $\ Displaystyle \ scriptstyle \ Sigma ^ {\ omega} / L (A).}$

Dowód: Dowód jest przedstawiony tutaj .

Rozpoznawalne języki

Automaty Büchi rozpoznają języki regularne ω . Korzystając z definicji języka ω-regularnego i powyższych właściwości domknięć automatów Büchiego, można łatwo wykazać, że automat Büchi można skonstruować tak, że rozpoznaje dowolny dany język ω-regularny. Odwrotnie, zobacz konstrukcję języka regularnego ω dla automatu Büchi .

Deterministyczne i niedeterministyczne automaty Büchiego

Niedeterministyczny automat Büchiego, który rozpoznaje ${\ Displaystyle (0 \ puchar 1) ^ {*} 0 ^ {\ omega}}$

Klasa deterministycznych automatów Büchi nie wystarcza do objęcia wszystkich języków omega-regularnych. W szczególności nie ma deterministycznego automatu Büchiego, który rozpoznaje język , $skończenie$ 1 występuje wiele razy. Możemy wykazać przez zaprzeczenie, że taki deterministyczny automat Büchiego nie istnieje. Załóżmy, że $stanu$ deterministycznym automatem Büchiego, który ze końcowego akceptuje $\ Displaystyle 0 ^ {\ omega}}$ { . Tak więc A odwiedzi jakiś stan w $F$ po przeczytaniu jakiegoś skończonego przedrostka $,$ po literze. A akceptuje również słowo ω ${\ Displaystyle 0 ^ {i_ {0}} 10 ^ {\ omega}.}$ Dlatego dla niektórych po przedrostku ${\ Displaystyle i_ {1}}$${\ Displaystyle 0 ^ {i_ {0} }}10^{i_{1}}}$ automat odwiedzi jakiś stan w F . $tę$ generowane słowo A odwiedzać jakiś stan w F nieskończenie często i słowo nie jest w ${\ Displaystyle (0 \ puchar 1) ^ {*} 0 ^ {\ omega}.}$ Sprzeczność.

Klasę języków rozpoznawalną przez deterministyczne automaty Büchiego charakteryzuje następujący lemat.

Lemat: Język ω jest rozpoznawalny przez deterministyczny automat Büchiego, jeśli jest językiem granicznym jakiegoś języka regularnego .

Dowód: Każdy deterministyczny automat Büchiego A może być traktowany jako deterministyczny automat skończony A' i odwrotnie, ponieważ oba typy automatów są zdefiniowane jako 5-krotka tych samych składowych, tylko interpretacja warunku akceptacji jest inna. Pokażemy, że $L (A$$Displaystyle$ ZA } Słowo ω jest akceptowane przez A , jeśli zmusi A do odwiedzania stanów końcowych nieskończenie często. Zatem nieskończenie wiele skończonych przedrostków tego słowa ω będzie akceptowanych przez A' . Stąd ${\ Displaystyle L (A)}$ jest językiem granicznym ${\ Displaystyle L (A')}$ .

Algorytmy

Sprawdzanie modeli systemów o skończonych stanach często można przełożyć na różne operacje na automatach Büchiego. Oprócz operacji zamknięcia przedstawionych powyżej, poniżej przedstawiono kilka przydatnych operacji w zastosowaniach automatów Büchi.

Determinacja

Ponieważ deterministyczne automaty Büchiego są ściśle mniej wyraziste niż automaty niedeterministyczne, nie może istnieć algorytm wyznaczania automatów Büchiego. Ale twierdzenie McNaughtona i konstrukcja Safry dostarczają algorytmów, które mogą przetłumaczyć automat Büchi na deterministyczny automat Mullera lub deterministyczny automat Rabina .

Sprawdzanie pustki

Język rozpoznawany przez automat Büchi jest niepusty wtedy i tylko wtedy, gdy istnieje stan końcowy, który jest zarówno osiągalny ze stanu początkowego, jak i leży w cyklu.

Efektywny algorytm sprawdzający pustkę automatu Büchi:

1. Rozważ automat jako graf skierowany i rozłóż go na silnie połączone składowe (SCC).
2. Uruchom wyszukiwanie (np. przeszukiwanie w głąb ), aby znaleźć, które SCC są osiągalne ze stanu początkowego.
3. Sprawdź, czy istnieje nietrywialny SCC, który jest osiągalny i zawiera stan końcowy.

Każdy z kroków tego algorytmu można wykonać w czasie liniowym w rozmiarze automatu, stąd algorytm jest wyraźnie optymalny.

Minimalizacja

Algorytm minimalizacji niedeterministycznego automatu skończonego również poprawnie minimalizuje automat Büchiego. Algorytm nie gwarantuje minimalnego automatu Büchiego . Jednak algorytmy minimalizacji deterministycznego automatu skończonego nie działają dla deterministycznego automatu Büchiego.

Warianty

• Automat Co-Büchi
• Słaby automat Büchi
• Półdeterministyczny automat Büchiego
• Uogólniony automat Büchiego

Przejście od innych modeli opisu do niedeterministycznych automatów Büchiego

Z uogólnionych automatów Büchi (GBA)

₀₀ Wiele zestawów stanów w stanie akceptacji można przetłumaczyć na jeden zestaw stanów za pomocą konstrukcji automatu, znanej jako „konstrukcja licząca”. Powiedzmy, że A = (Q,Σ,∆,q ,{F ₁ ,...,F _n }) jest GBA, gdzie F ₁ ,...,F _n są zbiorami akceptujących stanów, to odpowiednik automatu Büchiego to A' = (Q', Σ, ∆',q' ,F'), gdzie

• Q' = Q × {1,...,n}
• ₀₀ q' = ( q ,1 )
• ∆' = { ( (q,i), za, (q',j) ) | (q,a,q') ∈ ∆ i jeśli q ∈ F _i wtedy j=((i+1) mod n) else j=i }
• F'=F ₁ × {1}

Z formuły logiki liniowej temporalnej

tutaj tłumaczenie formuły liniowej logiki czasowej na uogólniony automat Büchiego . Powyżej przedstawiono tłumaczenie z uogólnionego automatu Büchiego na automat Büchiego.

Z automatów Mullera

₀₀₀₀ Dany automat Mullera można przekształcić w równoważny automat Büchiego za pomocą następującej konstrukcji automatu. Załóżmy, że A = (Q,Σ,∆,Q ,{F ,...,F _n }) jest automatem Mullera, gdzie F ,...,Fn _są zbiorami akceptujących stanów. Równoważnym automatem Büchiego jest A' = (Q', Σ, ∆',Q ,F'), gdzie

• Q' = Q ∪ ∪ ⁿ _{i = 0} {i} × fa _ja × 2 ^{fa _ja}
• ∆'= ∆ ∪ ∆ ₁ ∪ ∆ ₂ , gdzie
  • ∆ ₁ = { ( q, za, (i,q',∅) ) | (q, a, q') ∈ ∆ i q' ∈ F _i }
  • ∆ ₂ = { ( (i,q,R), za, (i,q',R') ) | (q,a,q')∈∆ i q,q' ∈ F _i i jeśli R=F _i to R'= ∅ inaczej R'=R∪{q} }
• fa'= ∪ ⁿ _ja=0 {i} × fa _ja × {fi _ja }

A' zachowuje oryginalny zestaw stanów z A i dodaje do nich dodatkowe stany. Automat Büchiego A' symuluje automat A Mullera w następujący sposób: Na początku słowa wejściowego wykonanie A' następuje po wykonaniu A , ponieważ stany początkowe są takie same, a ∆' zawiera ∆. W jakiejś niedeterministycznie wybranej pozycji w słowie wejściowym A' decyduje o skoku do nowo dodanych stanów poprzez przejście w ∆ ₁ . Fi _Następnie przejścia w ∆ ₂ próbują odwiedzić wszystkie stany i rosną R . Kiedy R staje się równe F _i, Fi . _jest resetowany do zbioru pustego i ∆ _{2 próbuje} raz po raz odwiedzać wszystkie stany stanów Tak więc, jeśli stany R = F _i są odwiedzane nieskończenie często, to A' akceptuje odpowiednie wejście, podobnie jak A . Ta konstrukcja jest ściśle zgodna z pierwszą częścią dowodu twierdzenia McNaughtona .

Ze struktur Kripkego

Niech dana struktura Kripkego będzie zdefiniowana przez M = ⟨ Q , I , R , L , AP ⟩ gdzie Q to zbiór stanów, I to zbiór stanów początkowych, R to relacja między dwoma stanami również interpretowana jako krawędź, L to etykieta stanu, a AP to zbiór zdań atomowych, które tworzą L .

Automat Büchi będzie miał następujące cechy:

${\ Displaystyle Q _ {\ text {final}} = Q \ cup \ {{\ text {init}} \}}$

${ \ Displaystyle \ Sigma = 2 ^ {AP}}$

${\ Displaystyle I = \ {{\ tekst {init}} \}}$

${\ Displaystyle F = Q \ kubek \ { {\ text {init}} \}}$

${\ Displaystyle \ delta = q {\ overrightarrow {a}} p}$ , jeśli ( q , p ) należy do R i L ( p ) = a

i init ${\ Displaystyle {\ overrightarrow {a}}}$ q jeśli q należy do ja i L ( q ) = za .

Należy jednak zauważyć, że istnieje różnica w interpretacji między strukturami Kripkego a automatami Büchiego. Podczas gdy ta pierwsza wyraźnie określa polaryzację każdej zmiennej stanu dla każdego stanu, ta druga po prostu deklaruje bieżący zestaw zmiennych, które są prawdziwe lub nie. Nie mówi absolutnie nic o innych zmiennych, które mogą być obecne w modelu.

•   Bakhadyr Khoussainov; Anil Nerode (6 grudnia 2012). Teoria automatów i jej zastosowania . Springer Science & Business Media. ISBN 978-1-4612-0171-7 .
• Thomas, Wolfgang (1990). „Automaty na nieskończonych obiektach”. W Van Leeuwen (red.). Podręcznik informatyki teoretycznej . Elsevier. s. 133–164.

Linki zewnętrzne

• „Skończone automaty stanów na nieskończonych wejściach” (PDF) .
•   Vardi, Moshe Y. „Teoretyczne podejście do liniowej logiki temporalnej”. CiteSeerX 10.1.1.125.8126 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )