Automat sygnałowy

W teorii automatów , dziedzinie informatyki , automat sygnałowy jest automatem skończonym rozszerzonym o skończony zestaw zegarów o wartościach rzeczywistych. Podczas działania automatu sygnałowego wszystkie wartości zegara rosną z tą samą prędkością. Wzdłuż przejść automatu wartości zegara można porównać do liczb całkowitych. Te porównania tworzą strażników, które mogą włączać lub wyłączać przejścia, a przez to ograniczać możliwe zachowania automatu. Ponadto zegary można zresetować.

Przykład

Przed formalnym zdefiniowaniem, czym jest automat sygnałowy, zostanie podany przykład. Rozważmy język $}}}$ nad alfabetem binarnym, który zawiera sygnały. $L$$\ mathcal$ takie, że:

• $czasu$ . $_$ czasów _
• $.$ się co najmniej raz podczas każdego interwału o długości jeden

Ten język może zaakceptować automat przedstawiony obok.

Automat sygnałowy zapewniający dyskretne trzymanie A i co najmniej raz na jednostkę czasu

Jeśli chodzi o automat skończony, nadchodzące strzałki reprezentują początkowe lokalizacje, a podwójne kółko oznacza akceptujące lokalizacje. Jednak w przeciwieństwie do automatów skończonych litery występują w miejscach, a nie w przejściach. Dzieje się tak, ponieważ litery są emitowane w sposób ciągły, a przejścia są wykonywane dyskretnie. Symbol $zegar$ . _ _ Zegar ten $emisji$ mierzyć czas od ostatniej . Zatem ${\ displaystyle x = 0}$ zapewnia, że ${\ displaystyle A}$ emitowany jest dyskretnie. A ${\ displaystyle 1> x} zapewnia$$,$ że ​​nie więcej niż jednostka czasu może minąć bez .

Definicja formalna

Automat sygnałowy

Formalnie automat sygnałowy jest krotką ${\ Displaystyle {\ mathcal {A}} = \ langle \ Sigma, L, L_ {0}, C,F,\alpha ,\beta ,E\rangle }$ , który składa się z następujących elementów:

• $Sigma}$${\ displaystyle {\ mathcal {A}}}$ to skończony zbiór zwany alfabetem lub działaniami ZA .
• ${\ displaystyle L}$ jest skończonym zbiorem . Elementy $nazywane$ lokalizacjami lub stanami . _ $_$ _
• ${\ displaystyle C}$ to skończony zbiór zwany zegarami ZA {\ ${\ mathcal {A}}}$ .
• ${\ Displaystyle L_ {0} \ subseteq L}$ to zbiór lokalizacji początkowych.
• ${\ displaystyle F \ subseteq L}$ to zbiór akceptujących lokalizacji.
• ${\ Displaystyle \ alfa: L \ do \ Sigma}$ , który kojarzy literę z każdą lokalizacją.
• ${\ Displaystyle \ beta: L \ do {\ mathcal {B}} (C)},$ które wiążą ograniczenia zegara z każdą lokalizacją i
• $Displaystyle E \ subseteq L \ razy {\ mathcal {P}} (C) \ razy L}$${\ Displaystyle {\ mathcal { A}}}$ to zbiór krawędzi, zwanych przejściami ZA
  • , jest mocą ${\ mathcal {P}} (C)$$\ Displaystyle$ .
  gdzie

Krawędź ${\ Displaystyle (\ ell, r, \ ell ')}$$ell '}$ { $Displaystyle E}$ jest przejściem z lokalizacji do $\ ell}$$\ Displaystyle$ , które resetują zegary ${\ displaystyle r}$ .

Stan rozszerzony

Para z $rozszerzonym$ i wyceną $jest$ nazywana stanem lub stanem .

$jest$ więc niejednoznaczne, ponieważ w zależności od autora może oznaczać parę lub element . Dla jasności w tym artykule będzie używany termin $dla$ elementu i termin rozszerzona lokalizacja dla par.

Tutaj leży jedna z największych różnic między automatami sygnałowymi a automatami skończonymi . W automacie skończonym w pewnym momencie wykonania stan jest w całości opisany liczbą odczytanych liter i skończoną liczbą możliwych wartości, które w rzeczywistości nazywane są „stanami”. Oznacza to, że mając stan i sufiks słowa do odczytania, pozostała część przebiegu jest całkowicie określona. Stąd słowo „skończony” w nazwie „automaty skończone”. Jednak, jak wyjaśniono w sekcji „uruchom” poniżej, w celu wznowienia używane są zegary, które określają, które przejścia można wykonać. Tak więc, aby poznać stan automatu, musisz zarówno teraz, w którym miejscu się znajdujesz, jak i wycenę zegara.

Uruchomić

Jeśli chodzi o automaty skończone, przebieg jest zasadniczo sekwencją lokalizacji, tak że istnieje przejście między dwoma lokalizacjami. Należy jednak podkreślić dwie różnice. Litera nie jest określona przez przejście, ale przez lokalizacje; wynika to z faktu, że litery są emitowane w sposób ciągły, podczas gdy przejścia są wykonywane dyskretnie. W lokacji upływa trochę czasu; ograniczenia zegara oznaczające lokalizację lub jej następcę mogą ograniczać czas spędzony w jednym miejscu.

Przebieg jest sekwencją postaci $}] {C}} ( \ell _{0},I_{0}){\xrightarrow[{\nu _{1}}]{r_{1}}}(\ell _{1},I_{1})\dots } spełnia$ , niektóre ograniczenia. Przed określeniem tych ograniczeń wprowadzono pewne oznaczenia. Sekwencje są dyskretne, ale reprezentują zdarzenia ciągłe. Ciągła wersja sekwencji $)}$${\ Displaystyle (\ sigma _ {i})}$ , ) $\ nu _ {i$ } teraz wprowadzony. Niech ${\ Displaystyle i \ geq 0}$ całka i t ∈ ja ja $\ in I_ {i}}$ , to

• niech ${\ Displaystyle \ sigma '_ {t}}$ będzie równy ${\ Displaystyle \ sigma _ {i}}$ ,
• niech ${\ Displaystyle \ nu '_ {t}}$ będzie $\ Displaystyle \ nu _ {i} + t- \ lceil I_ {i} \ rceil}$ z $lceil I_ {i} \ rceil}$ \ będąc dolną granicą przedziału, ${\ Displaystyle I_ {i}}$
• niech ${\ Displaystyle \ ell '_ {t} = \ ell _ {i}}$ .

Ograniczenia spełnione przez uruchomienie są dla każdej $:$ i rzeczywistej $\ displaystyle i \ geq 0}$

• ${\ Displaystyle \ ell _ {0} \ w L_ {0}}$ ,
• ${\ Displaystyle (\ ell _ {i}, r_ {i}, \ ell _ {i + 1}) \ w mi$ ,
• ${\ Displaystyle \ nu _ {i + 1} = (\ nu _ {i} + \ mid I_ {i} \ mid) [r_ {i}\strzałka w prawo 0]}$ ,
• ${\ Displaystyle \ nu '_ {t} \ modele \ beta (\ ell '_ {t})}$ .

Sygnał zdefiniowany przez $przebieg$ jest funkcją powyżej . Mówi się, że bieg zdefiniowany powyżej to bieg na sygnał ${\ displaystyle \ sigma '}$ .

Pojęcie akceptowania przebiegu jest zdefiniowane jak w automatach skończonych dla słów skończonych i jak w automatach Büchi dla słów nieskończonych. $\$ to, że jeśli $,$ jest skończona to przebieg jest akceptowany, jeśli $Displaystyle \ ell _ {n} \ in F}$ . Jeśli słowo jest nieskończone, to przebieg akceptuje wtedy i tylko wtedy, gdy istnieje nieskończona liczba pozycji takich, że ja $\ displaystyle i}$${\ Displaystyle \ ell _ {i} \ w F}$ .

Akceptowane sygnały i język

$się, że$$jest$ akceptowany przez automat sygnałowy, $.$ przebieg na ${\ displaystyle \ gamma}$ akceptując to. Zbiór sygnałów akceptowanych przez jest nazywany językiem akceptowanym przez ${A}}}$$\ Displaystyle {\ mathcal$ i jest oznaczony przez $\ mathcal {S(A)}}}$ .

Deterministyczny automat sygnałowy

Podobnie jak w przypadku automatu skończonego i automatu Büchiego, automat sygnałowy może być deterministyczny lub niedeterministyczny. Intuicyjnie bycie deterministycznym oznacza to samo znaczenie w każdym z tych przypadków. ${\ displaystyle s$ jest singletonem i że biorąc pod uwagę stan rozszerzony $literę$ , istnieje tylko jeden możliwy stan rozszerzony, do którego można dotrzeć z $} \ displaystyle s}$ czytając za $\ displaystyle a}$ . Mówiąc dokładniej, albo możliwe jest pozostanie w danej lokalizacji dłużej, albo istnieje co najwyżej jedna następna lokalizacja.

Formalnie można to zdefiniować w następujący sposób:

• ${\ displaystyle L_ {0}}$ jest singletonem
• dla każdej lokalizacji ${\ Displaystyle \ ell \ in L}$ , dla każdego przejścia ${\ Displaystyle (\ ell, r, \ ell ') \ in mi$ } strefy są rozłączne:
  • strefa zdefiniowana przez ograniczenie zegara , ${\ Displaystyle \ beta (\ ell)$ }
  • $}$ przez ograniczenie zegara, ograniczenia dotyczące zegarów $displaystyle$ \
• dla każdej zmiany lokalizacji ${\ Displaystyle (\ ell, r ', \ ell ') \ in E}$ i ${\ Displaystyle (\ ell ,r'',\ell '')\in E}$ , dwie następujące strefy są rozłączne:
  • strefa zdefiniowana przez ograniczenie zegara, $}$ której usunięto zegarów $\ displaystyle r$
  • strefa zdefiniowana przez ograniczenie zegara, $}$ dotyczące zegarów $displaystyle r'$ '

Uproszczone automaty sygnałowe

W zależności od autorów dokładna definicja automatów sygnałowych może być nieco inna. Obecnie podano dwie takie definicje.

Interwały półotwarte

Aby uprościć definicję przebiegu, niektórzy autorzy wymagają, aby każdy przedział przebiegu był zamknięty w prawo i otwarty w lewo. Ogranicza to automaty do akceptowania tylko sygnałów, których podstawowa partycja spełnia tę samą właściwość. Zapewnia jednak, że za każdym razem ${\ Displaystyle t \ geq 0}$ , ${\ Displaystyle \ lim _ {t \ leftarrow x ^ {+}} f (x) = f (t)}$ dla ${\ displaystyle f}$ reprezentujący dowolną z funkcji wprowadzonych powyżej ${\ displaystyle \ sigma '}$ , ${\ displaystyle \ nu '}$ lub ${\ displaystyle \ ell '} .$

Dwudzielny automat sygnałowy

Dwudzielny automat sygnałowy to automat sygnałowy, w którym przebieg zmienia się pomiędzy przedziałami otwartymi i przedziałami osobliwymi (tj. przedziałami, które są singletonami). Zapewnia to, że wykres leżący u podstaw automatu jest grafem dwudzielnym , a zatem zbiór lokalizacji można podzielić na ${\ Displaystyle \ {L ^ {o}, L ^ {s} \}}$ , zbiór otwartych lokalizacji i pojedynczych lokalizacji. Ponieważ pierwszy przedział zawiera 0, nie może to być miejsce otwarte, stąd wynika, że ${\ Displaystyle L_ {0} \ subseteq L ^ {s}}$ . Aby upewnić się, że każda pojedyncza lokalizacja jest rzeczywiście pojedyncza, dla każdej lokalizacji $}$$}$ zegar , który jest resetowany podczas wchodzenia. $}$$\ displaystyle \ ell$ i takie, że ograniczenie zegara $\$ x $displaystyle x = 0}$ .

Każdy automat sygnałowy można przekształcić w równoważny dwudzielny automat sygnałowy. Wystarczy zastąpić każdą lokalizację parą lokalizacji ${\ Displaystyle (\ ell ^ {o}, \ ell ^ {s})}$$s$ nowy zegar ${\ Displaystyle x}$ tak, że dla każdego ${\ Displaystyle \ ell}$ , ${\ Displaystyle x _ {\ ell ^ {s}} = x}$ .

W pobliżu przedstawiono automat dwudzielny odpowiadający automatowi sygnałowemu z przykładowej sekcji. Stany prostokąta reprezentują pojedyncze lokalizacje.

Dwudzielny automat sygnałowy zapewniający, że A zachodzi dyskretnie i co najmniej raz na jednostkę czasu

Synchronizacja automatów

Pojęcie iloczynu automatu skończonego zostaje rozszerzone na automat sygnałowy. Jednak taki produkt nazywany jest synchronizacją automatu, aby podkreślić fakt, że czas powinien płynąć podobnie w obu rozpatrywanych automatach. Główna różnica między synchronizacją a iloczynem polega na tym, że kiedy dwa automaty skończone czytają to samo słowo, przechodzą jednocześnie. Nie dotyczy to już automatów sygnałowych, ponieważ mogą one przechodzić w dowolnym czasie. Zatem relacja przejścia automatu sygnałowego może pozwolić na przejście w jednym lub dwóch automatach.

Niech ${\ Displaystyle {\ mathcal {A}} ^ {1} = \ langle \ Sigma, L$ i ${\ Displaystyle {\ mathcal {A}} ^ {2} = \ langle \ Sigma, L ^ {2}, L_ {0} ^ {2}, C$ dwa automaty sygnałowe, ich synchronizacja jest automatem sygnałowym ${\ Displaystyle {\ mathcal {A}} 1 \ otimes {\ mathcal {A}} ^ {2} = \ langle \ Sigma \ {(\ell ^{1},\ell ^{2})\in L^{1}\otimes L^{2}\mid \alpha ^{1}(\ell ^{1})=\alpha ^ {2}(\ell ^{2})\},L_{0}^{1}\czasami L_{0}^{2},C^{1}\cup C^{2},F^{1 }\oraz F^{2},(\ell ^{1},\ell ^{2})\mapsto \alpha ^{1}(\ell ^{1}),(\ell ^{1},\ ell ^ {2}) \ mapsto \ beta ^ {1} (\ ell ^ {1}) \ ziemia \ beta ^ {2} (\ ell ^ {2}), E \ rangle} ,$ gdzie ${\ Displaystyle E }$ zawiera następujące przejścia:

• ${\ Displaystyle ((\ ell ^ {1}, \ ell ^ {2}), r ^ {1}, (\ ell ^ {\ pierwsza 1} \ ell ^ {2})}$ dla ${\ Displaystyle (\ ell ^ {1}, r, \ ell ^ {\ pierwsza 1}) \ w E ^ {1}}$ i podobnie dla ${\ displaystyle E ^ {2}}$ ,
• ${\ Displaystyle ((\ ell ^ {1}, \ ell ^ {2}), r ^ {1} \ kubek r ^ {2}, (\ ell ^ {\ pierwsza 1}, \ ell ^ {\ pierwsza 2})}$ dla ${\ Displaystyle (\ ell ^ {1 },r,\ell ^{\prime 1})\in E^{1}}$ i ${\ Displaystyle (\ ell ^ {2} r, \ ell ^ {\ pierwsza 2}) \ w E ^ {2}}$ .

Różnica w stosunku do automatów czasowych

Automaty czasowe to kolejne rozszerzenie automatów skończonych, które dodaje pojęcie czasu do słów. Przedstawimy teraz niektóre z głównych różnic między automatami czasowymi a automatami sygnałowymi.

W automatach czasowych litery są emitowane na przejściach, a nie w lokalizacjach. Jak wyjaśniono powyżej, porównując automaty sygnałowe z automatami skończonymi, litery są emitowane w przejściach, gdy słowa są emitowane dyskretnie, jak w przypadku słów i słów czasowych, podczas gdy są emitowane w miejscach, w których litery są emitowane w sposób ciągły, jak w przypadku sygnałów.

W automatach czasowych strażnicy są sprawdzani tylko przy przejściach. Upraszcza to definicję automatu deterministycznego, ponieważ oznacza, że ​​ograniczenie musi być spełnione przed ponownym uruchomieniem zegarów.

Zobacz też

• Automat czasowy