Języki, automaty i obliczenia/Wykład 3: Automat skończenie stanowy: Różnice pomiędzy wersjami
m (→Automaty) |
|||
Linia 528: | Linia 528: | ||
\hline \tau _{\mathcal{A}}(b) & s_0 & s_0 & s_0\\ | \hline \tau _{\mathcal{A}}(b) & s_0 & s_0 & s_0\\ | ||
\hline \tau _{\mathcal{A}}(a^{2}) & s_2 & s_2 & s_2\\ | \hline \tau _{\mathcal{A}}(a^{2}) & s_2 & s_2 & s_2\\ | ||
− | \hline \tau _{\mathcal{A}}(ab) & s_0 & s_0 & | + | \hline \tau _{\mathcal{A}}(ab) & s_0 & s_0 & s_0\\ |
\hline \tau _{\mathcal{A}}(ba) & s_1 & s_1 & s_1\\ | \hline \tau _{\mathcal{A}}(ba) & s_1 & s_1 & s_1\\ | ||
\hline \tau _{\mathcal{A}}(b^{2}) & s_0 & s_0 & s_0\\ | \hline \tau _{\mathcal{A}}(b^{2}) & s_0 & s_0 & s_0\\ |
Wersja z 07:30, 15 kwi 2008
W rozdziale tym zdefiniujemy automat - drugi, obok gramatyki, model obliczeń. Określimy język rozpoznawany przez automat i podamy warunki równoważne na to, by język był rozpoznawany.
Automaty
Wprowadzimy teraz pojęcie automatu. Jak już wspomnieliśmy w wykładzie drugim automat to drugi, obok gramatyki, model obliczeń będący przedmiotem badań teorii języków i automatów. Model realizujący warunek efektywności analitycznej, czyli taki na podstawie którego możliwe jest sformułowanie algorytmu rozstrzygającego w skończonej liczbie kroków, czy dowolne słowo należy, czy też nie należy do języka rozpoznawanego przez ten automat. Lub inaczej możemy powiedzieć, że taki automat daje algorytm efektywnie rozstrzygający, czy dowolne obliczenie sformułowane nad alfabetem automatu jest poprawne.
Wprowadzony w tym wykładzie automat, zwany automatem skończenie stanowym, jest jednym z najprostszych modeli obliczeń. Jest to model z bardzo istotnie ograniczoną pamięcią. Działanie takiego automatu sprowadza się do zmiany stanu pod wpływem określonego zewnętrznego sygnału czy impulsu.
Pomimo tych ograniczeń urządzenia techniczne oparte o modele takich automatów spotkać możemy dość często. Jako przykład służyć mogą automatyczne drzwi, automaty sprzedające napoje, winda, czy też urządzenia sterujące taśmą produkcyjną.
Przykład 1.1.
Drzwi automatycznie otwierane są sterowane automatem, którego działanie opisać można, przyjmując następujące oznaczenia. Fakt, że osoba chce wejść do pomieszczenia zamykanego przez takie drzwi, identyfikowany przez odpowiedni czujnik, opiszemy symbolem
. Zamiar wyjścia symbolem . Symbol będzie związany z równoczesnym zamiarem wejścia jakiejś osoby i wyjścia innej. Wreszcie symbol oznaczał będzie brak osób, które chcą wejść lub wyjść. Zatem zbiór , to alfabet nad którym określimy automat o stanach: Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle OTWARTE, ZAMKNIĘTE} poniższym grafem.<flash>file=ja-lekcja03-w-rys6.swf|width=270|height=270</flash> <div.thumbcaption>Rysunek 1 |
<flashwrap>file=ja-lekcja03-w-rys7.swf|size=small</flashwrap> <div.thumbcaption>Animacja 1 |
Automaty reagują więc na określone sygnały zewnętrzne reprezentowane przez litery alfabetu
, zmieniając swój stan. Jeśli ustalimy stan początkowy automatu oraz dopuszczalne stany końcowe, to automat będzie testował dowolne słowo z , startując ze stanu początkowego. Jeśli rezultatem finalnym działania automatu (obliczenia) będzie stan końcowy, to słowo będzie rozpoznawane przez automat, a obliczenie określone takim słowem poprawne. Automaty można graficznie reprezentować jako etykietowane grafy skierowane. W takim grafie każdy wierzchołek odpowiada stanowi automatu, a każda strzałka pomiędzy wierzchołkami i , etykietowana symbolem , oznacza przejście automatu ze stanu do stanu pod wpływem litery . Podamy teraz definicję automatu. Niech oznacza dowolny alfabet. Od tego momentu wykładu zakładamy, że alfabet jest zbiorem skończonym.Definicja 1.1
Automatem nad alfabetem
nazywamy system , w którym- jest dowolnym skończonym zbiorem zwanym zbiorem stanów,
- jest funkcją przejść.
Automat będąc w stanie
po przeczytaniu litery zmienia stan na zgodnie z funkcją przejścia .Funkcję przejść rozszerzamy na cały wolny monoid
do postaciprzyjmując:
dla każdego
orazdla każdego
i dla dowolnegoDziałanie automatu pokazane jest na poniższej animacji 2.
<flashwrap>file=ja-lekcja03-w-rys1.swf|size=small</flashwrap>
<div.thumbcaption>Animacja 2Zdefiniowany powyżej automat
Przykład 1.2.
Niech
będzie alfabetem, a automatem takim, że, a funkcja przejść zadana jest przy pomocy tabelki
Automat możemy również jednoznacznie określić przy pomocy grafu.
<flash>file=ja-lekcja03-w-rys2.swf|width=350|height=150</flash>
<div.thumbcaption>Rysunek 2
Podamy teraz bardzo interesujący przykład zastosowania automatów skończonych.
Przedstawimy mianowicie wykorzystanie tak zwanych
automatów synchronizujących w przemyśle. Automat synchronizujący nad alfabetem to
automat o
następującej własności: istnieje stan oraz słowo takie, że dla każdego stanu tego automatu . Istnieje więc pewne uniwersalne
słowo , pod wpływem którego wszystkie stany przechodzą w jeden,
ustalony stan automatu . Mówimy, że następuje wtedy synchronizacja
wszystkich stanów automatu.
Poniżej prezentujemy przykład zaczerpnięty z pracy Ananicheva i Volkova (D. S. Ananichev, M. V. Volkov, Synchronizing Monotonic Automata, Lecture Notes in Computer Science, 2710(2003), 111-121.), ukazujący ideę użycia automatów synchronizujących w tej dziedzinie.
<flash>file=ja-lekcja03-w-rys-s1.swf|width=250|height=100</flash>
<div.thumbcaption>Rysunek 3<flash>file=ja-lekcja03-w-rys-s2.swf|width=250|height=100</flash>
<div.thumbcaption>Rysunek 4<flash>file=ja-lekcja03-w-rys-s3.swf|width=250|height=250</flash>
<div.thumbcaption>Rysunek 5Przykład 1.3.
Załóżmy, że pewna fabryka produkuje detale w kształcie kwadratu z "wypustką" na jednym boku (patrz rys. 3). Po wyprodukowaniu detale należy umieścić w opakowaniach w ten sposób, by wszystkie były w tej samej orientacji - mianowicie "wypustką" w lewo.
Załóżmy ponadto dla uproszczenia, że detale mogą przyjmować jedną z czterech orientacji (rys. 4): "wypustką" w górę, w dół, w lewo lub w prawo.
Należy zatem skonstruować takie urządzenie (orienter), które będzie ustawiało wszystkie detale w żądanej orientacji. Oczywiście istnieje wiele metod rozwiązania tego problemu, ale z praktycznego punktu widzenia potrzebne jest rozwiązanie najprostsze i najtańsze. Jednym z takich sposobów jest umieszczanie detali na pasie transmisyjnym z zamontowaną wzdłuż niego pewną ilością przeszkód dwojakiego rodzaju: niskich (low) oraz wysokich (HIGH). Wysoka przeszkoda ma tę własność, że każdy detal, który ją napotka, zostanie obrócony o 90 stopni w prawo (zakładamy, że elementy jadą od lewej do prawej strony). Przeszkoda niska obróci o 90 stopni w prawo tylko te detale, które są ułożone "wypustką" w dół. Na rys. 5 przedstawione zostały przejścia pomiędzy orientacjami detali w zależności od napotkania odpowiedniej przeszkody.
Można zauważyć, że automat z rysunku 5 jest automatem synchronizującym. Słowem, które go synchronizuje, jest następująca sekwencja przeszkód:
low-HIGH-HIGH-HIGH-low-HIGH-HIGH-HIGH-low.
Niezależnie od tego, w jakiej orientacji początkowej znajduje się detal, po przejściu przez powyższą sekwencję przeszkód zawsze będzie ułożony "wypustką" w lewo. Sytuację przedstawia poniższa animacja 3:
<flashwrap>file=ja-lekcja03-w-anim-s4.swf|size=small</flashwrap>
<div.thumbcaption>Animacja 3Rozszerzymy teraz wprowadzone pojęcie automatu w ten sposób, by uzyskać możliwość efektywnego rozstrzygania, czy dowolne słowo utworzone nad alfabetem
reprezentuje poprawne obliczenie, czyli spełnia kryteria określone przez rozszerzony automat.Definicja 1.2.
Język
jest rozpoznawany (akceptowany) wtedy i tylko wtedy, gdy istnieje automat skończony stan oraz zbiór takie, żeStan
nazywamy stanem początkowym, a zbiorem stanów końcowych automatu .Rozszerzony w powyższy sposób automat, poprzez dodanie stanu początkowgo i zbioru stanów końcowych, w dalszym ciągu nazywamy automatem i oznaczamy jako piątkę
lub czwórkę , jeśli wiadomo, nad jakim alfabetem rozważamy działanie automatu.Fakt, że język
jest rozpoznawany przez automat zapisujemy jakoRodzinę wszystkich języków rozpoznawalnych nad alfabetem
oznaczamy przez .Podobnie jak w przypadku gramatyk nie ma jednoznacznej odpowiedniości pomiędzy językami rozpoznawalnymi a automatami. Wprowadza się więc relację, która identyfikuje automaty rozpoznające ten sam język.
Definicja 1.3.
Automaty
i są równoważne, jeśli rozpoznają ten sam język, czyliW dalszych rozważaniach języków rozpoznawanych ograniczymy się do automatów
, które spełniają warunek Nie zawęża to naszych rozważań. Jeśli bowiem język jest rozpoznawany przez pewien automat , to jest również rozpoznawany przez automatktóry spełnia powyższy warunek. Zauważmy, że przyjmując to założenie, upraszczamy strukturę automatu. Z punktu widzenia grafu automatu można powiedzieć, że nie występują w nim wierzchołki (stany) nieosiagalne z
. Poniżej przedstawiamy algorytm usuwający z automatu stany nieosiągalne ze stanu początkowego.Algorytm UsuńStanyNieosiągalne - usuwa z automatu
stany nieosiągalne
1 Wejście:- automat. 2 Wyjście: - automat równoważny automatowi bez
stanów nieosiągalnych. 3 for each do 4 zaznaczone ; 5 end for 6 zaznaczone ; 7 OZNACZ ; 8 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle S' \leftarrow \{s \in S:\} zaznaczone ; 9 ; 10 flag false jeśli nie dodamy stanu to na końcu pętli nadal flag=false 11 ; 12 for each do 13 for each do 14 if NULL then 15 ; była nieokreślona 16 flag true; 17 end if 18 end for 19 end for 20 if flag=true then 21 ; 22 end if 23 return ;
Algorytm Procedure Oznacz
1 procedure OZNACZ2 for each 3 flag false 4 for each do 5 if then 6 flag true 7 end if 8 end for 9 if flag=true and zaznaczone then 10 zaznaczone ; 11 OZNACZ ; 12 end if 13 end for 14 end procedure
Powyższy algorytm, dla ustalonego
alfabetu , posiada złożoność , czyli liniową
względem liczby stanów.
Przedstawiając automat przy pomocy grafu przyjmujemy następującą konwencję. Jeśli w automacie występuje stan początkowy, oznaczać go będziemy zieloną strzałką wchodzącą do tego stanu. Jeśli w automacie występują stany końcowe, oznaczać je będziemy niebieską obwódką.
Przykład 1.4.
Jeśli w przykładzie 1.2 (patrz przykład 1.2.) przyjmiemy stan jako stan początkowy, jako zbiór stanów końcowych, to automat rozpoznaje język
złożony ze słów, kończących się na
<flash>file=ja-lekcja03-w-rys3.swf|width=350|height=350</flash>
<div.thumbcaption>Animacja 4Słowo
jest akceptowane.<flash>file=ja-lekcja03-w-rys4.swf|width=350|height=350</flash>
<div.thumbcaption>Animacja 5
Każdy automat wyznacza w wolnym monoidzie
prawą kongruencję, nazywaną prawą kongruencją automatową, określoną w następujący
sposób:
Dla automatu skończonego (o skończonym zbiorze stanów), a takie rozważamy, relacja
ma skończony indeks, czyli skończoną liczbę klas równoważności.Przykład 1.5.
Automat z przykładu 1.2 (patrz przykład 1.2.) ze stanem jako początkowym wyznacza relację równoważności o trzech klasach:
,<br\> ,<br\>
Na odwrót, każda prawa kongruencja
wyznacza automat, zwany ilorazowym, w następujący sposób:
Z definicji prawej kongruencji wynika, że funkcja przejść jest określona poprawnie.
Definicja 1.4.
Niech
wtedy, jeśli i będą dowolnymi automatami. Odwzorowanie nazywamy homomorfizmem automatów wtedy i tylkoHomomorfizm automatów oznaczamy
.Twierdzenie 1.1.
Prawdziwe są następujące fakty:
(1) Dla dowolnej prawej kongruencji
(2) Dowolny automat
jest izomorficzny z automatem ,(3) Dla dowolnych automatów
i prawdziwa jest równoważnośćParser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2}\: \: \Longleftrightarrow \: } istnieje epimorfizm
taki, że .Dowód
(1) Identyczność relacji wynika wprost z definicji automatu ilorazowego
oraz prawej kongruencji .(2) Rozważmy automat
i odwzorowaniegdzie
Istnienie słowa
Odwzorowanie ma być homomorfizmem, czyli dla każdego stanu i dowolnego
słowa spełniać warunek
Warunek ten wynika z następujących równości
gdzie
.Z prostych obserwacji wynika, że
jest suriekcją i iniekcją.(3) Dowód implikacji "
Załóżmy, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2 } }
. Niech
będzie odwzorowaniem takim, że
Stąd, że
Z założenia Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \: \sim _{\mathcal{A}_1}\: \subseteq \: \sim _{\mathcal{A}_2} }
wynika, że jest poprawnie zdefiniowaną funkcją.
Uzasadnienie faktu, że jest
homomorfizmem, jest analogiczne jak w punkcie (2) dla .
jest suriekcją, gdyż
jest stanem początkowym automatu .
ponieważ .
Dowód implikacji " "
Niech będzie epimorfizmem
takim, że .
Wówczas prawdziwy jest następujący ciąg wnioskowań.
To oznacza, że
.
Symbolem
oznaczamy rodzinę wszystkich funkcji określonych na zbiorze i przyjmujących wartości w . Łatwo zauważyć, iż rodzina ta wraz ze składaniem odwzorowań jest monoidem .Definicja 1.5.
Niech
będzie dowolnym automatem. Reprezentacją automatu nazywamy funkcję , określoną dla dowolnych i równościąReprezentacja automatu jest homomorfizmem monoidu
w monoid , bowiem dla dowolnych spełnione są warunkiDefinicja 1.6.
Niech
będzie dowolnym automatem. Monoidem przejść automatu nazywamy monoidNastępujące wnioski są konsekwencjami rozważań przeprowadzonych powyżej.
Wniosek 1.1.
(1) Monoid przejść automatu
generatorów tego monoidu. jest podmonoidem monoidu i zbiór jest zbioremWynika to z faktu, że twierdzenie 2.1. wykład 1)
jest epimorfizmem i z twierdzenia 2.1 z wykładu 1. (patrz(2) Monoid przejść automatu skończonego jest skończony.
(3) Monoid przejść automatu
Jest to wniosek z twierdzenia o rozkładzie epimorfizmu, które w tym przypadku ilustruje poniższy diagram. jest izomorficzny z monoidem ilorazowym .<flash>file=ja-lekcja03-w-rys5.swf|width=350|height=200</flash>
<div.thumbcaption>Rysunek 6Przykład 1.6.
Określimy monoid przejść dla automatu z przykładu 1.2 (patrz przykład 1.2.). Wypisujemy kolejne funkcje dla . Zauważmy, że ze względu na występujące w tabelce powtórzenia, będące wynikiem równości, np. nie ma potrzeby określać funkcji dla . Podobna obserwacja ma miejsce w innych przypadkach, co sprawia, że tabelka zawiera skończoną liczbę różnych funkcji.
Poniżej zamieszczamy algorytm obliczający monoid przejść dla automatu skończenie stanowego.
Algorytm WyznaczMonoidPrzejść - wyznacza monoid przejść dla automatu
1 Wejście:- automat 2 Wyjście: - monoid przejść dla 3 ; jest listą 4 ; 5 for each do 6 insert ; gdzie dla każdego 7 end for 8 while ; do 9 first ; 10 ; 11 for each do 12 for each do 13 ; 14 end for 15 if 16 insert ; 17 end if 18 end for 19 end while 20 return ;
Procedura insert wkłada na koniec listy element
. Funkcja first wyjmuje pierwszy element znajdujący
się na liście i zwraca go. Algorytm działa w następujący sposób:
najpierw na listę wkładane są elementy monoidu przejść
dla każdej litery . Te
funkcje można obliczyć bezpośrednio z tabelki reprezentującej
funkcję przejścia automatu . Następnie z listy po kolei
ściągane są poszczególne funkcje . Każda z
nich dodawana jest do zbioru , a następnie algorytm sprawdza dla
każdej litery , czy funkcja
istnieje już na liście lub w zbiorze . Jeśli nie, to funkcja
ta dodawana jest do listy. Procedura powyższa trwa do czasu, gdy
lista zostanie pusta. Wtedy wszystkie elementy monoidu przejść
znajdą się w zbiorze .
Przeanalizujmy działanie algorytmu dla automatu z przykładu 1.2 (patrz przykład 1.2.).
Na początku na listę
włożone zostaną funkcje , oraz . Z listy zdejmujemy funkcję i dodajemy ją do zbioru . Ponieważ , a funkcje oraz znajdują się już na liście, zatem nie dodajemy ich do . Bierzemy kolejny element listy, , dodajemy go do i obliczamy funkcje oraz . Ponieważ nie jest tożsama z żadną funkcją ze zbioru , dodajemy ją do listy. Funkcja również nie jest równa żadnej z funkcji należących do zbioru , zatem wstawiamy ją na koniec listy. Na liście mamy zatem teraz następujące elementy: , oraz . Zdejmujemy z listy funkcję , dodajemy ją do i obliczamy oraz . Pierwsza z tych funkcji jest nowa, tzn. nie jest tożsama z żadną funkcją ze zbioru więc dodajemy ją na koniec listy. Druga z nich równa jest funkcji , więc nie dodajemy jej do listy. W tym momencie zbiór zawiera następujące elementy: , , , natomiast lista zawiera elementy , , . Zdejmujemy z funkcję , dodajemy ja do i ponieważ i , nic nie dodajemy do . Zdejmujemy teraz z listy funkcję , dodajemy ją do i ponieważ nie należy do dodajemy ją do listy. , więc tej funkcji nie dodajemy do . Z ściągamy , dodajemy ją do i widzimy, że oraz , więc nic nie dodajemy do . Na liście pozostała funkcja . Ściągamy ją z listy i dodajemy do . Widzimy, że i , zatem nic nie dodajemy do listy . Lista jest w tym momencie pusta i działanie algorytmu zakończyło się. Ostatecznie mamyco zgadza się z wynikiem otrzymanym w przykładzie.
Twierdzenie poniższe zbiera dotychczas uzyskane charakteryzacje języków rozpoznawanych.
Twierdzenie 1.2.
Niech
będzie dowolnym językiem. Równoważne są następujące warunki:- (1) Język jest rozpoznawalny,
- (2) Język
- (3) Język
- (4) Istnieje skończony monoid
Dowód
Dowód równoważności czterech powyższych warunków przeprowadzimy zgodnie z następującym schematem:
Dany jest homomorfizm
gdzie
Określamy relację na , przyjmując dla dowolnych
Tak określona relacja jest kongruencją. Natomiast jej skończony indeks wynika z faktu, że monoid
jest skończony. Pokażemy teraz, że:Inkluzja
Inkluzja w przeciwną stronę ( ) oznacza, że każda klasa równoważności relacji
albo cała zawiera się w języku , albo cała zawiera się w uzupełnieniu języka .
Załóżmy, że dla pewnego
Oznacza to, że
Implikuje to ostatecznie, że
.
Każda kongruencja jest prawą kongruencją.
Niech
będzie prawą kongruencją o skończonym indeksie na taką, żeAutomat
dla któregoakceptuje język
.
Niech język
Określamy odwzorowanie
przyjmując dla każdego
Jest to odwzorowanie kanoniczne monoidu
jest monoidem skończonym, ponieważ jest zbiorem skończonym.
Dla dowodu równości
Niech Oznacz to, że
czyli Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle u \in L. }}}
