Maszyna skończona: teoria i implementacja. Rodzaje maszyn skończonych. Praktyczne zastosowanie maszyn stanowych

Teoria automatów jest gałęzią matematyki dyskretnej badającą modele dyskretnych konwerterów informacji. Przetwornikami takimi są zarówno urządzenia rzeczywiste (komputery, organizmy żywe), jak i urządzenia urojone (teorie aksjomatyczne, maszyny matematyczne). Zasadniczo maszynę o skończonych stanach można scharakteryzować jako urządzenie M , posiadający kanały wejściowe i wyjściowe, i w każdym z dyskretnych momentów czasu, zwanych momentami zegarowymi, znajduje się w jednym ze stanów końcowych.

Według kanału wejściowego w każdym momencie T =1, 2, ... do urządzenia M docierają sygnały wejściowe (z pewnego skończonego zestawu sygnałów). Prawo zmiany stanu w następnym momencie ustala się w zależności od sygnału wejściowego i stanu urządzenia w danym momencie. Sygnał wyjściowy zależy od stanu i sygnału wejściowego w danej chwili (rys. 1).

Maszyna o skończonych stanach to model matematyczny rzeczywistych urządzeń przetwarzających informację dyskretną.

Maszyna stanu zwany systemem A= (X , Q , Y ,  ,  ), Gdzie X , Q , Y są dowolnymi niepustymi zbiorami skończonymi i  I  - funkcje, w tym:

pęczek X ={A 1 , ..., A M ) jest nazywany alfabet wejściowy , a jego elementy są sygnały wejściowe , ich sekwencje są w w powszechnych słowach ;

pęczek Q ={Q 1 , ..., Q N ) jest nazywany wiele stanów automat i jego elementy - stwierdza ;

pęczek Y ={B 1 , ..., B P ) jest nazywany alfabet wyjściowy , jego elementy są sygnały wyjściowe , ich sekwencje są słowa wyjściowe ;

funkcjonować  : X  Q Q zwany funkcja przejścia ;

funkcjonować  :X  Q Y zwany funkcja wyjściowa .

Zatem,  (X , Q )Q ,  (X , Q )Y dla  X X , Q Q .

Maszyna o skończonych stanach jest powiązana z wyimaginowanym urządzeniem, które działa w następujący sposób. Może znajdować się w jednym z wielu stanów Q , odbierają sygnały z różnych X i wysyłają sygnały z różnych źródeł Y .

2. Metody wyznaczania maszyny skończonej

Istnieje kilka równoważnych sposobów definiowania automatów abstrakcyjnych, spośród których można wymienić trzy: tabelaryczny , geometryczny I funkcjonalny .

2.1. Tabelaryczne zadanie maszyny

Z definicji automatu wynika, że ​​zawsze można go określić za pomocą tablicy zawierającej dwa wejścia T linie i P kolumny, gdzie na przecięciu kolumny Q i sznurki A są wartościami funkcji  (A I , Q J ),  (A I , Q J ).

2.2. Określenie automatu za pomocą diagramu Moore'a

Innym sposobem zdefiniowania skończonej maszyny stanów jest graficzna, to znaczy użycie wykresu. Automat jest przedstawiony jako oznaczony graf skierowany G(Q , D ) z wieloma wierzchołkami Q i wiele łuków D ={(Q J ,  (A I , Q J ))| Q J Q , A I X ), natomiast łuk ( Q J ,  (A I , Q J )) jest oznaczony parą ( A I ,  (A I , Q J )). Zatem w tej metodzie stany maszyny są przedstawiane za pomocą okręgów, w których zapisane są symbole stanów Q J (J = 1, …, N ). Z każdego koła jest to przeprowadzane T strzałki (zorientowane krawędzie) jeden do jednego odpowiadające znakom alfabetu wejściowego X ={A 1 , ..., A M ). Strzałka odpowiadająca literze A I X i opuszczenie kręgu Q J Q , przypisuje się parze ( A I ,  (A I , Q J )), a ta strzałka prowadzi do odpowiedniego okręgu  (A I , Q J ).

Powstały rysunek nazywa się wykres automatu Lub, Schemat Moore'a . W przypadku niezbyt skomplikowanych maszyn ta metoda jest bardziej wizualna niż tabelaryczny.

Maszyna o skończonych stanach to jakiś abstrakcyjny model zawierający skończoną liczbę stanów czegoś. Służy do reprezentowania i kontrolowania przepływu wykonywania dowolnych poleceń. Maszyna stanów jest idealna do wdrażania sztucznej inteligencji w grach, tworząc schludne rozwiązanie bez pisania nieporęcznego i złożonego kodu. W tym artykule przyjrzymy się teorii, a także dowiemy się, jak używać prostej maszyny stanów opartej na stosie.

Opublikowaliśmy już serię artykułów na temat pisania sztucznej inteligencji za pomocą maszyny o skończonych stanach. Jeśli jeszcze nie czytałeś tej serii, możesz to zrobić teraz:

Co to jest maszyna o skończonych stanach?

Maszyna o skończonych stanach (lub po prostu FSM – maszyna o skończonych stanach) to model obliczeniowy oparty na hipotetycznej maszynie stanów. W danym momencie aktywny może być tylko jeden stan. Dlatego, aby wykonać jakiekolwiek czynności, maszyna musi zmienić swój stan.

Maszyny stanowe są zwykle używane do organizowania i reprezentowania przepływu wykonywania czegoś. Jest to szczególnie przydatne przy wdrażaniu sztucznej inteligencji w grach. Na przykład, pisząc „mózg” wroga: każdy stan reprezentuje pewien rodzaj akcji (atak, unik itp.).

Skończoną maszynę stanową można przedstawić jako graf, którego wierzchołki są stanami, a krawędzie przejściami między nimi. Każda krawędź ma etykietę wskazującą, kiedy powinno nastąpić przejście. Przykładowo na powyższym obrazku widać, że maszyna zmieni stan „wędrowania” na stan „ataku”, pod warunkiem, że gracz będzie w pobliżu.

Stany planowania i ich przejścia

Implementacja maszyny o skończonych stanach rozpoczyna się od zidentyfikowania jej stanów i przejść pomiędzy nimi. Wyobraźmy sobie maszynę stanu opisującą działania mrówki przenoszącej liście do mrowiska:

Punktem wyjścia jest stan „znajdź liść”, który pozostaje aktywny do momentu, aż mrówka znajdzie liść. Kiedy to nastąpi, stan zmieni się na „idź do domu”. Ten sam stan pozostanie aktywny, dopóki nasza mrówka nie dotrze do mrowiska. Następnie stan zmienia się ponownie na „znajdź liść”.

Jeżeli stan „znajdź liść” jest aktywny, ale kursor myszy znajduje się w pobliżu mrówki, to stan zmienia się na „uciekaj”. Gdy mrówka znajdzie się w wystarczającej odległości od kursora myszy, stan zmieni się z powrotem na „znajdź liść”.

Pamiętaj, że jadąc do domu lub poza nim, mrówka nie będzie bać się kursora myszy. Dlaczego? Ale ponieważ nie ma odpowiedniego przejścia.

Implementacja prostej maszyny o skończonych stanach

Skończoną maszynę stanów można zaimplementować przy użyciu jednej klasy. Nazwijmy to FSM. Pomysł polega na zaimplementowaniu każdego stanu jako metody lub funkcji. Do określenia stanu aktywnego użyjemy również właściwości activeState.

Klasa publiczna FSM ( private var activeState:Function; // wskaźnik do aktywnego stanu maszyny funkcja publiczna FSM() ( ) funkcja publiczna setState(state:Function) :void ( activeState = stan; ) funkcja publiczna update() :void ( if ( stan aktywny != null) ( stan aktywny(); ) ) )

Każdy stan jest funkcją. Co więcej, tak, że będzie wywoływany za każdym razem, gdy ramka gry zostanie zaktualizowana. Jak już wspomniano, activeState będzie przechowywać wskaźnik do funkcji stanu aktywnego.

Metoda update() klasy FSM musi być wywoływana w każdej klatce gry. A to z kolei wywoła funkcję stanu, który jest aktualnie aktywny.

Metoda setState() ustawi nowy stan aktywny. Co więcej, każda funkcja określająca jakiś stan automatu nie musi należeć do klasy FSM - czyni to naszą klasę bardziej uniwersalną.

Korzystanie z maszyny stanu

Zaimplementujmy sztuczną inteligencję mrówek. Powyżej pokazaliśmy już zbiór jego stanów i przejść pomiędzy nimi. Zilustrujmy je jeszcze raz, ale tym razem skupimy się na kodzie.

Naszą mrówkę reprezentuje klasa Ant, która posiada pole mózgowe. To jest tylko instancja klasy FSM.

Klasa publiczna Ant (publiczna pozycja var:Vector3D; publiczna prędkość var:Vector3D; publiczna var mózg:FSM; funkcja publiczna Ant(posX:Number, posY:Number) ( pozycja = nowy Vector3D(posX, posY); prędkość = nowy Vector3D( -1, -1); mózg = nowy FSM(); // Zacznij od znalezienia liścia. brain.setState(findLeaf); ):void ( ) /** * Stan „goHome”. mrowisko */ funkcja publiczna goHome() :void ( ) /** * Stan „runAway”. / funkcja publiczna runAway() :void ( ) funkcja publiczna update():void ( // Aktualizacja maszyny stanu. Ta funkcja zostanie wywołana // funkcja stanu aktywnego: findLeaf(), goHome() lub runAway(). brain.update( ); // Stosowanie prędkości do ruchu mrówki moveBasedOnVelocity();

Klasa Ant zawiera również właściwości prędkości i położenia. Zmienne te posłużą do obliczenia ruchu metodą Eulera. Funkcja update() jest wywoływana za każdym razem, gdy ramka gry jest aktualizowana.

Poniżej znajduje się implementacja każdej metody, zaczynając od findLeaf() - stanu odpowiedzialnego za wyszukiwanie liści.

Funkcja publiczna findLeaf() :void ( // Przesuwa mrówkę do liścia. prędkość = new Vector3D(Game.instance.leaf.x - pozycja.x, Game.instance.leaf.y - pozycja.y); if (odległość (Gra .instance.leaf, to)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

stan goHome() - używany, aby mrówka wróciła do domu.

Funkcja publiczna goHome() :void ( // Przenosi mrówkę do domu prędkość = new Vector3D(Game.instance.home.x - pozycja.x, Game.instance.home.y - pozycja.y); if (odległość( Gra.instancja.home, to)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

I na koniec, stan runAway() jest używany podczas oddalania się od kursora myszy.

Funkcja publiczna runAway() :void ( // Odsuwa mrówkę od kursora speed = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Czy kursor jest nadal w pobliżu ? if ( odległość(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Nie, to już daleko. Czas wrócić do szukania liścia. brain.setState(findLeaf); ) )

Ulepszenie FSM: automat oparty na stosie

Wyobraź sobie, że mrówka w drodze do domu również musi uciec przed kursorem myszy. Tak będą wyglądać stany FSM:

Wydaje się, że to banalna zmiana. Nie, ta zmiana stwarza dla nas problem. Wyobraź sobie, że obecny stan jest „uciekany”. Jeśli kursor myszy odsunie się od mrówki, co powinna zrobić: wrócić do domu czy poszukać liścia?

Rozwiązaniem tego problemu jest maszyna stanów oparta na stosie. W przeciwieństwie do prostego FSM, który zaimplementowaliśmy powyżej, ten typ FSM wykorzystuje stos do zarządzania stanami. Na górze stosu znajduje się stan aktywny, a przejścia występują, gdy stany są dodawane/usuwane ze stosu.

A oto wizualna demonstracja działania maszyny stanów opartej na stosie:

Implementacja FSM opartego na stosie

Taką maszynę stanów można zaimplementować w taki sam sposób, jak prostą. Różnica polega na zastosowaniu tablicy wskaźników do wymaganych stanów. Nie potrzebujemy już właściwości activeState, ponieważ wierzchołek stosu będzie już wskazywał stan aktywny.

Klasa publiczna StackFSM ( prywatna var stos:Array; funkcja publiczna StackFSM() ( this.stack = new Array(); ) funkcja publiczna update() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) funkcja publiczna popState() :Function ( return stack.pop(); ) funkcja publiczna pushState(stan:Function) :void ( if (getCurrentState() != stan) ( stack.push(stan) ; ) ) funkcja publiczna getCurrentState() :Function (zwróć długość stosu > 0 ? stos: null; ) )

Należy zauważyć, że metoda setState() została zastąpiona przez pushState() (dodanie nowego stanu na górę stosu) i popState() (usunięcie stanu na górę stosu).

Korzystanie z FSM opartego na stosie

Należy zauważyć, że podczas korzystania z maszyny stanów opartej na stosie każdy stan jest odpowiedzialny za usunięcie ze stosu, gdy nie jest już potrzebny. Na przykład stan ataku() powinien sam usunąć się ze stosu, jeśli wróg został już zniszczony.

Klasa publiczna Ant ( (...) public var mózg:StackFSM; funkcja publiczna Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Zacznij od wyszukania mózgu liścia. pushState( findLeaf); (...) ) /** * Stan „findLeaf”. * Zmusza mrówkę do wyszukiwania liści */ funkcja publiczna findLeaf() :void ( // Przenosi mrówkę do liścia. prędkość = nowy Vector3D(Instancja gry. liść.x - pozycja.x, Instancja gry.liść.y - pozycja.y); if (odległość (instancja gry.liść, to)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // Nie, to już daleko. Czas wrócić do szukania liści. brain.popState(); ) ) (...) )

Wniosek

Maszyny stanowe są z pewnością przydatne do implementowania logiki sztucznej inteligencji w grach. Można je łatwo przedstawić w formie wykresu, co pozwala programiście zobaczyć wszystkie możliwe opcje.

Implementacja maszyny stanowej z funkcjami stanu jest prostą, ale potężną techniką. Jeszcze bardziej złożone sploty stanu można wdrożyć za pomocą FSM.

Jednym z kryteriów złożoności skończonej maszyny stanowej jest liczba jej stanów. Im mniejsza jest ta liczba, tym prostsze jest dyskretne urządzenie, które implementuje tę maszynę. Dlatego jednym z ważnych zadań teorii automatów skończonych jest konstrukcja automatu o jak najmniejszej liczbie stanów.

Ponieważ we współczesnych komputerach wszelkie informacje są reprezentowane w postaci kodów binarnych, do budowy automatu można wykorzystać elementy, które mają tylko dwa różne stany stabilne, z których jeden odpowiada liczbie 0, a drugi cyfrze 1.

Podajmy kilka przykładów maszyn o skończonych stanach.

Przykład 1. Element opóźniający (element pamięci).

Elementy opóźniające to urządzenie posiadające jedno wejście i jedno wyjście. Ponadto wartość sygnału wyjściowego w danym momencie T pokrywa się z wartością sygnału w chwili poprzedzającej. Schematycznie element opóźniający można przedstawić w następujący sposób (ryc. 2).

Załóżmy, że alfabet wejściowy, a co za tym idzie wyjściowy, to X ={0, 1}, Y =(0, 1). Następnie Q =(0, 1). W stanie elementu opóźnienia w danym momencie T Rozumie się zawartość elementu pamięci w danym momencie. Zatem Q (T )= X (T 1), a Y (T )= Q (T )=X (T 1).

Ustawmy element opóźnienia za pomocą tabeli, gdzie A 1 =0, A 2 =1, Q 1 =0, Q 2 =1,

(A 1 , Q 1)= (0, 0)=0,  (A 1 , Q 1)= (0, 0)=0;

(A 1 , Q 2)= (0, 1)=0,  (A 1 , Q 2)= (0, 1)=1;

(A 2 , Q 1)= (1, 0)=1,  (A 2 , Q 1)= (1, 0)=0;

(A 2 , Q 2)= (1, 1)=1,  (A 2 , Q 2)= (1, 1)=1;

Diagram Moore’a pokazany jest na ryc. 3

Aby przedstawić ten automat jako układ funkcji boolowskich, używamy tablicy automatu i powyższego algorytmu. W tym przypadku nie ma potrzeby wykonywania kodowania, ponieważ alfabety i stany wejściowe i wyjściowe są już zakodowane.

Zwróćmy uwagę na fakt t=p=p =2. Następnie k =R =S =1, dlatego element opóźnienia jest określony przez dwie funkcje  I  . Tabela prawdy tych funkcji zawiera 2 k + R =2 2 =4 linie i k +R +R +S =4 kolumny:

Przykład 2. Binarny sumator sekwencyjny.

Ten sumator sekwencyjny to urządzenie, które dodaje dwie liczby w systemie binarnym. Liczby podawane są na wejścia sumatora X 1 i X 2, zaczynając od cyfr najmniej znaczących. Dane wyjściowe generują sekwencję odpowiadającą wpisowi numeru X 1 +X 2 w układzie binarnym (ryc. 4).

Alfabety wejściowe i wyjściowe są jednoznacznie zdefiniowane: X ={00; 01; 10; 11}, Y =(0,1). Zbiór stanów wyznaczany jest na podstawie wartości przeniesienia przy dodawaniu odpowiednich cyfr liczb X 1 i X 2. Jeżeli podczas dodawania bitów nastąpi przeniesienie, to zakładamy, że sumator wszedł w stan Q 1. W przypadku braku przeniesienia założymy, że sumator jest w stanie Q 0 .

Dodatek jest określony w tabeli.

Diagram Moore'a sumatora sekwencyjnego pokazano na ryc. 5.

Należy pamiętać, że symbole wejściowe i wyjściowe są już zakodowane. Kodujemy stany w następujący sposób:  (Q 0)=0,  (Q 1)=1. Dlatego sumator sekwencyjny jest określony przez dwie funkcje logiczne, których tablica prawdy wygląda następująco:

Przykład 3. Schemat porównania równości.

Obwód porównania równości to urządzenie, które porównuje dwie liczby X 1 i X 2, podane w systemie binarnym. To urządzenie działa w następujący sposób. Cyfry liczb podawane są na wejście urządzenia sekwencyjnie, zaczynając od tych najbardziej znaczących. X 1 i X 2. Te cyfry są porównywane. Jeśli bity na wyjściu układu pokrywają się, generowany jest sygnał wyjściowy 0, w przeciwnym razie na wyjściu pojawia się sygnał 1. Oczywiste jest, że pojawienie się 1 w sekwencji wyjściowej oznacza, że ​​porównywane są liczby X 1 i X 2 są różne. Jeżeli sekwencja wyjściowa wynosi zero, a jej długość pokrywa się z liczbą cyfr porównywanych liczb, to X 1 i X 2 .

Dla tej maszyny X ={00, 01, 10, 11}; Y ={0,1}.

O funkcjonowaniu obwodu decydują dwa stany. Państwo Q 0 odpowiada równości aktualnie porównywanych cyfr. W takim przypadku maszyna pozostaje w tym samym stanie. Jeśli w następnej chwili porównywane cyfry będą się różnić, maszyna przejdzie do nowego stanu Q 1 i pozostaje w nim, ponieważ oznacza to, że liczby są różne. Zatem schemat porównania można określić za pomocą tabeli:

Diagram Moore'a schematu porównania równości pokazano na ryc. 6.

Stany będziemy kodować w następujący sposób:  (Q 0)=0,  (Q 1)=1. Maszyna będzie określona przez dwie funkcje.

Przykład 4. Schemat porównania nierówności.

Obwód porównywania nierówności to urządzenie, które pozwala sprawdzić, czy porównywane rzeczy są równe. X 1 i X 2, a jeśli nie są równe, dowiedz się, który z nich jest większy od drugiego. To urządzenie ma dwa wejścia i dwa wyjścia. Sygnały wyjściowe y 1 (T ) I y 2 (T ) ustalane są według następujących zasad:

y 1 (T )=y 2 (T ) = 0, jeśli X 1 (T )=X 2 (T );

y 1 (T )=1, y 2 (T ) = 0, jeśli X 1 (T )>X 2 (T ), to jest X 1 (T )=1, X 2 (T )=0;

y 1 (T )=0, y 2 (T ) = 1, jeśli X 1 (T )<X 2 (T ), to jest X 1 (T )=0, X 2 (T )=1.

Zatem po podaniu na wejście obwodu porównawczego pod kątem nierówności liczb X 1 =X 1(l)… X 1 (T ) I X 2 =X 2(l)… X 2 (T )cyfry tych liczb są porównywane sekwencyjnie, zaczynając od tych najbardziej znaczących. Sygnały wyjściowe formułowane są według powyższych zasad. Co więcej, jeśli sekwencja wyjściowa składa się z par zerowych, to X 1 =X 2. Jeśli pierwsza niezerowa para ma postać , () To X 1 >X 2 (X 1 <X 2).

Z opisu obwodu wynika, że

X ={00, 01, 10, 11}, Y ={00, 01, 10}.

Stan obwodu określa się w następujący sposób. Załóżmy, że w początkowej chwili czasu T =1 maszyna jest w stanie Q 1 . Jeśli porównane cyfry liczb X 1 I X 2 pokrywają się, wówczas maszyna pozostaje w tym stanie. Należy pamiętać, że na wyjściu pojawi się sygnał 00. Jeśli cyfra numeru X 1 będzie mniejsza (większa) niż odpowiadająca jej cyfra liczby X 2, wtedy maszyna przejdzie do stanu Q 2 (Q 3). W takim przypadku na wyjściu pojawi się sygnał 01 (10). Następnie przy składaniu pozostałych cyfr liczb X 1 I X 2 do wejść maszyny, maszyna pozostanie w stanie Q 2 (Q 3) i wygeneruj symbol wyjściowy 10 (01). Z powyższego wynika, że ​​schemat porównania nierówności można określić za pomocą tabeli:

Odpowiedni diagram Moore'a pokazano na ryc. 7.

Alfabety wejściowe i wyjściowe są już tutaj zakodowane. Stany Q 1 , Q 2 i Q Zakodujmy 3:  1 (Q 1)=00,  (Q 2)=01,  (Q 3)=10.

Dlatego obwód ten można określić za pomocą układu składającego się z czterech funkcji boolowskich zależnych od czterech zmiennych. Funkcje te są częściowo zdefiniowane i podane przez tablicę prawdy

W tabeli symbole * oznaczają zbiory zmiennych X 1 , X 2 , z 1 , z 2, na którym znajdują się funkcje  1 ,  2 ,  1 ,  2 nie są określone. Włóżmy wartości funkcji  1 ,  2 ,  1 ,  2 w tych zbiorach jest równe 1.

Teoria maszyn skończonych

Teoria automatów leży u podstaw teorii konstrukcji kompilatora. Maszyna o skończonych stanach jest jednym z podstawowych pojęć. Przez automat nie mamy na myśli rzeczywiście istniejącego urządzenia technicznego, chociaż takie urządzenie można zbudować, ale pewien model matematyczny, którego właściwości i zachowanie można imitować za pomocą programu na komputerze. Automat skończony jest najprostszym modelem teorii automatów i z reguły służy jako urządzenie sterujące dla wszystkich innych typów automatów. Maszyna skończona ma wiele właściwości:

· Maszyna stanów może rozwiązać wiele prostych problemów związanych z kompilacją. Blok leksykalny jest prawie zawsze budowany w oparciu o skończoną maszynę stanów.

· Działanie maszyny skończonej charakteryzuje się dużą wydajnością.

· Modelowanie maszyn stanowych wymaga stałej ilości pamięci, co upraszcza zarządzanie pamięcią.

· istnieje szereg twierdzeń i algorytmów pozwalających konstruować i upraszczać skończone maszyny stanowe.

W literaturze istnieje kilka różnych definicji maszyny o skończonych stanach. Jednak łączy je to, że maszyna o skończonych stanach modeluje urządzenie obliczeniowe ze stałą ilością pamięci, które odczytuje sekwencje symboli wejściowych należących do pewnego zbioru wejściowego. Zasadnicze różnice w definicjach dotyczą tego, co maszyna robi na wyjściu. Wynik maszyny może być wskaźnikiem, czy dany łańcuch wejściowy jest „akceptowalny”, czy nie. „Akceptowalny” to poprawnie skonstruowany lub poprawny pod względem składniowym łańcuch. Na przykład łańcuch, który ma reprezentować stałą liczbową, jest uważany za niepoprawnie skonstruowany, jeśli zawiera dwa miejsca po przecinku.

Definicja: Maszyna o skończonych stanach to system formalny zdefiniowany za pomocą następujących obiektów:

· skończony zbiór symboli wejściowych;

· skończony zbiór stanów;

· funkcja przejścia, która przypisuje każdej parze (stan bieżący, symbol wejściowy) nowy stan;

· stan początkowy;

· podzbiór stanów zidentyfikowanych jako zezwalający lub ostateczny.

Przykład. Przeanalizujmy działanie kontrolera sprawdzającego, czy liczba jedynek jest parzysta czy nieparzysta w dowolnym łańcuchu składającym się z zer i jedynek. Załóżmy, że odpowiedni automat skończony musi „przyjąć” wszystkie łańcuchy zawierające nieparzystą liczbę jedynek i „odrzucić” łańcuchy z liczbą parzystą. Nazwijmy tę maszynę „kontrolerem parzystości”. Uważamy, że na wejście maszyny nie można wprowadzać symboli innych niż 0 i 1. Zatem alfabet wejściowy kontrolera to zbiór (0, 1). Wierzymy, że w danym momencie automat skończony zajmuje się tylko jednym symbolem wejściowym i przechowuje informacje o poprzednich symbolach łańcucha wejściowego za pomocą skończonego zbioru stanów. Zbiór (parzysty, nieparzysty) będziemy rozpatrywać jako zbiór stanów; jeden z tych stanów należy wybrać jako początkowy. Niech to będzie stan (parzysty), gdyż w pierwszym kroku liczba odczytanych jedynek wynosi zero, a zero jest liczbą parzystą. Podczas odczytywania kolejnego symbolu wejściowego stan maszyny albo się zmienia, albo pozostaje taki sam, a jej nowy stan zależy od symbolu wejściowego i stanu bieżącego. Ta zmiana stanu nazywa się przejściem.

Działanie maszyny można opisać matematycznie funkcją przejścia w postaci d(Sprąd, x) = Snew. W przeciwnym razie można to zapisać w następujący sposób:

d(parzysty, 0) = parzysty. d(parzysty, 1) = nieparzysty.

d(nieparzysty, 0) = nieparzysty. d(nieparzysty, 1) = parzysty.

Kontroler ma pojedynczy stan akceptujący, ODD, a EVEN jest stanem „odrzucającym”. Odzwierciedlmy sekwencję przejść maszyny, gdy na jej wejście zostanie dostarczony łańcuch 1101.

PARZYSTY ® NIEPARAWY ® PAWNY ® PAWNY ® NIEPARZYSTY

Tabela przejść takiego automatu ma postać:

Definicja. Maszyna o skończonych stanach jest systemem formalnym

S = ( ZA, Q, re, l, V ),

którego obiekty są następujące:

* A jest skończonym zbiorem symboli wejściowych (zestaw

terminale);

* Q - skończony zbiór stanów wewnętrznych automatu

(zestaw nieterminali);

* V - skończony zbiór symboli wyjściowych (alfabet wyjściowy);

* d - funkcja przejścia, która charakteryzuje się A ` Q ® Q;

* l - funkcja wyjściowa określająca sposób wyświetlania widoku.

Teoria automatów

Definicja maszyny i jej odmiana. Tabele i wykresy przejść i wyjść. Maszyny subautomatyczne. Twierdzenie o automatzie zredukowanym

Operacje na maszynach

Przekształcenie maszyny Mealy'ego w maszynę Moore'a i maszyny Moore'a w maszynę Mealy'ego. Równoważność automatów. Rozróżnialność stanów automatów. Minimalizacja automatów. Synteza automatów. Maszyny rozpoznające

Automat to system mechanizmów i urządzeń, w którym procesy odbioru, przetwarzania i przesyłania energii, materiałów i informacji są w pełni zautomatyzowane. Termin „automat” jest używany w dwóch aspektach:

1) techniczne,

2) matematyczne.

W ujęciu matematycznym automat rozumiany jest jako model matematyczny urządzenia technicznego, które musi posiadać wejścia, stany wewnętrzne i wyjścia. Nie powinno być żadnych informacji dotyczących szczegółów budowy urządzenia.

W ujęciu technicznym przez maszynę rozumie się bardzo realne urządzenie, na przykład budkę telefoniczną, automat itp. W tym przypadku znane są oczywiście szczegóły wewnętrznej budowy urządzenia.

Szczególnym i ważnym przypadkiem automatu jest automat cyfrowy (DA), w którym procesy otrzymywania, przetwarzania, przechowywania i wydawania informacji cyfrowej są w pełni zautomatyzowane.

Z punktu widzenia sygnałów DA celowe jest zdefiniowanie układu, który może pod ich wpływem odbierać sygnały wejściowe, przechodzić z jednego stanu do drugiego, utrzymywać go do czasu nadejścia kolejnego sygnału wejściowego i wytwarzać sygnały wyjściowe.

DA uważa się za skończony, jeśli zbiory sygnałów wejściowych X, stanów S i sygnałów wyjściowych Y są skończone. Maszyna o skończonych stanach może być powiązana z urządzeniem takim jak komputer. Komputer przetwarza przychodzące dane wejściowe na dane wyjściowe (wynik), ale wynik ten odpowiada nie tylko danym wejściowym, ale także aktualnemu stanowi komputera, tj. dane, które są przechowywane w pamięci komputera, na przykład wyniki poprzednich obliczeń, programy obliczeniowe.

Praca grupy docelowej odbywa się w czasie automatycznym, określonym przez liczbę okresów odbioru sygnałów wejściowych.

Automat abstrakcyjny to matematyczny model dyskretnego urządzenia, które ma jeden kanał wejściowy, który odbiera ciągi symboli języka, jeden kanał wyjściowy, z którego pobierane są ciągi symboli innego języka, i które w każdej chwili znajduje się w pewnym stanie dyskretnego czasu. Graficznie abstrakcyjny automat przedstawiono na ryc.

Słowa języka wejściowego można przedstawić za pomocą symboli zbioru X=(x 1 ,x 2 ,...x n ), który nazywa się alfabet wejściowy, a słowa języka wyjściowego są symbolami zbioru Y=(y 1 ,y 2 ,...y p ), który nazywa się alfabet wyjściowy. Zbiór stanów automatu S=(s 1 , s 2 ,...s m ) nazywa się alfabet stanów.

Pojęcie stan maszyny służy do opisu systemów, których sygnały wyjściowe zależą nie tylko od sygnałów wejściowych w danym momencie, ale także od jakiejś wcześniejszej historii, tj. sygnałów, które wcześniej odebrane zostały na wejściach systemu. Dlatego automaty cyfrowe odnoszą się do obwodów sekwencyjnych, które, jak już wspomniano, mają pamięć. Pojęciu stanu automatu odpowiada pewna pamięć o przeszłości, dlatego wprowadzamy to pojęcie pozwala na wyeliminowanie czasu jako zmiennej jawnej i wyrażenie wyników jako funkcji stanów i wejść.

Działanie automatu abstrakcyjnego należy rozpatrywać w odniesieniu do określonych przedziałów czasu, gdyż każdy dyskretny przedział T będzie odpowiadać jego sygnałowi wyjściowemu y(t). W związku z tym działanie maszyny rozpatrywane jest w dyskretnych przedziałach czasu o skończonym czasie trwania. W abstrakcyjnej teorii automatów cyfrowych uważa się, że sygnały wejściowe działają na automat synchroniczny na początku każdego I- ten przedział (kwant) czasu przydzielony przez odpowiedni impuls synchronizacyjny (cykl), a zmiana stanów wewnętrznych maszyny następuje w odstępach czasu pomiędzy sąsiednimi impulsami synchronizacyjnymi, gdy nie ma wpływu sygnałów wejściowych.

Pojęcie „stanu” służy do ustalenia zależności funkcjonalnej symboli i/lub słów języka wyjściowego generowanego przez maszynę od symboli i/lub słów języka wejściowego, gdy maszyna implementuje dany algorytm. Dla każdego stanu automatu sОS i dla każdego symbolu xОX w chwili czasu dyskretnego [t] na wyjściu urządzenia generowany jest symbol yОY. Zależność tę wyznacza funkcja wyjściowa automatu j. Dla każdego aktualnego stanu automatu sОS i dla każdego symbolu xОX w chwili czasu dyskretnego [t] automat przechodzi do kolejnego stanu sОS. Zależność tę wyznacza funkcja przejścia automatu y. Działanie automatu polega na generowaniu dwóch ciągów: ciągu kolejnych stanów automatu (s 1[ s 2 s 3 ...) oraz ciągu symboli wyjściowych (y 1 y 2 y 3 ...), które dla ciągu symboli (x 1 x 2 x 3...) rozwijają się w momentach czasu dyskretnego t = 1,2,3,.... W nawiasach prostokątnych zaznaczamy momenty czasu dyskretnego, które inaczej nazywane są cyklami zegara , w nawiasach - ciągi znaków alfabetu X, Y i S.

Zatem model matematyczny automatu skończonego jest trójpodstawową algebrą, której nośnikami są trzy zbiory X, Y i S, a operacjami są dwie funkcje j i y.