Teoria mașinilor cu stări finite

Teoria automatelor stă la baza teoriei construcției compilatorului. O mașină cu stări finite este unul dintre conceptele de bază. Prin automat nu înțelegem un dispozitiv tehnic cu adevărat existent, deși se poate construi un astfel de dispozitiv, ci un anumit model matematic, ale cărui proprietăți și comportament pot fi imitate cu ajutorul unui program pe calculator. Un automat finit este cel mai simplu model al teoriei automatelor și, de regulă, servește ca dispozitiv de control pentru toate celelalte tipuri de automate. Mașina cu stări finite are o serie de proprietăți:

· O mașină de stare poate rezolva o serie de probleme ușoare de compilare. Blocul lexical este aproape întotdeauna construit pe baza unei mașini cu stări finite.

· Funcționarea mașinii cu stări finite se caracterizează prin performanță ridicată.

· Modelarea mașinii de stat necesită o cantitate fixă ​​de memorie, ceea ce simplifică gestionarea memoriei.

· există o serie de teoreme și algoritmi care vă permit să construiți și să simplificați mașini cu stări finite.

Există mai multe definiții diferite ale unei mașini cu stări finite în literatură. Cu toate acestea, ceea ce au în comun este că o mașină cu stări finite modelează un dispozitiv de calcul cu o cantitate fixă ​​de memorie care citește secvențe de simboluri de intrare aparținând unui set de intrare. Diferențele fundamentale în definiții sunt legate de ceea ce face mașina la ieșire. Ieșirea mașinii poate fi un indiciu dacă un anumit lanț de intrare este „acceptabil” sau nu. „Acceptabil” este un lanț corect construit sau corect din punct de vedere sintactic. De exemplu, un lanț care se presupune că reprezintă o constantă numerică este considerat construit incorect dacă conține două zecimale.

Definiţie: O mașină cu stări finite este un sistem formal care este definit folosind următoarele obiecte:

· set finit de simboluri de intrare;

· set finit de stări;

· o funcție de tranziție care atribuie fiecărei perechi (stare curentă, simbol de intrare) o nouă stare;

· starea initiala;

· un subset de stări identificate ca permisive sau finale.

Exemplu. Să analizăm funcționarea unui controler care verifică dacă numărul de unități este par sau impar într-un lanț arbitrar format din zerouri și unu. Să presupunem că automatul finit corespunzător trebuie să „accepte” toate lanțurile care conțin un număr impar de unități și să „respinge” lanțurile cu un număr par. Să numim această mașină „controler de paritate”. Credem că alte simboluri decât 0 și 1 nu pot fi trimise la intrarea mașinii. Deci, alfabetul de intrare al controlerului este setul (0, 1). Credem că la un anumit moment de timp automatul finit se ocupă de un singur simbol de intrare și stochează informații despre simbolurile anterioare ale lanțului de intrare folosind un set finit de stări. Vom considera multimea (par, impar) ca un set de stari una dintre aceste stari trebuie sa fie aleasa ca fiind cea initiala. Fie starea (par), deoarece la primul pas numărul celor citite este zero, iar zero este un număr par. La citirea următorului simbol de intrare, starea mașinii fie se schimbă, fie rămâne aceeași, iar noua sa stare depinde de simbolul de intrare și de starea curentă. Această schimbare de stare se numește tranziție.

Funcționarea mașinii poate fi descrisă matematic printr-o funcție de tranziție de forma d(Scurrent, x) = Snew. Altfel se poate scrie astfel:

d(par, 0) = par. d(par, 1) = impar.

d(impar, 0) = impar. d(impar, 1) = par.

Controlerul are o singură stare de acceptare, ODD, iar EVEN este o stare de „respingere”. Să reflectăm secvența de tranziții ale mașinii atunci când lanțul 1101 este furnizat la intrarea sa.

EVEN ® ODD ® EVEN ® EVEN ® ODD

Tabelul de tranziție al unui astfel de automat are forma:

Definiţie. O mașină cu stări finite este un sistem formal

S = (A, Q, d, l, V),

ale căror obiecte sunt următoarele:

* A este un set finit de simboluri de intrare (set

terminale);

* Q - set finit de stări interne ale automatului

(set de non-terminale);

* V - set finit de simboluri de ieșire (alfabet de ieșire);

* d - funcţie de tranziţie, care se caracterizează prin A ´ Q ® Q;

* l - funcție de ieșire care determină afișarea vizualizării.

Articolul discută mașini simple cu stări finite și implementarea lor în C++ folosind constructe de comutare, tabele de rulare și biblioteca Boost Statechart.

Introducere

În linii mari, o mașină cu stări finite, prin ochii utilizatorului, este o cutie neagră în care ceva poate fi transferat și ceva poate fi primit de acolo. Aceasta este o abstractizare foarte convenabilă, care vă permite să ascundeți un algoritm complex, iar mașinile cu stări finite sunt, de asemenea, foarte eficiente.

Mașinile cu stări finite sunt descrise sub formă de diagrame constând din stări și tranziții. Permiteți-mi să vă explic cu un exemplu simplu:

După cum probabil ați ghicit, aceasta este o diagramă de stare a unui bec. Starea inițială este indicată printr-un cerc negru, tranzițiile prin săgeți, unele săgeți sunt etichetate - acestea sunt evenimente după care mașina trece într-o altă stare. Deci, imediat din starea inițială, ne regăsim în stare Lumina stinsă- lampa nu se aprinde. Dacă apăsați butonul, aparatul își va schimba starea și va urma săgeata marcată Buton de apăsare, într-o stare Lumina aprinsă- becul este aprins. Puteți trece din această stare, din nou urmând săgeata, după apăsarea butonului, la starea Lumina stinsă.

Tabelele de tranziție sunt, de asemenea, utilizate pe scară largă:

Aplicarea practică a mașinilor automate

Mașinile cu stări finite sunt utilizate pe scară largă în programare. De exemplu, este foarte convenabil să ne imaginăm funcționarea unui dispozitiv sub forma unei mașini automate. Acest lucru va face codul mai simplu și mai ușor de experimentat și întreținut.

De asemenea, mașinile cu stări finite sunt folosite pentru a scrie toate tipurile de analizoare și analizoare de text, cu ajutorul lor, puteți căuta în mod eficient expresiile regulate, de asemenea, în mașina cu stări finite;

De exemplu, vom implementa un automat pentru numărarea numerelor și a cuvintelor din text. Pentru început, să fim de acord că un număr va fi considerat o secvență de numere de la 0 la 9 de lungime arbitrară, înconjurate de caractere cu spații albe (spațiu, tabulație, avans de linie). Un cuvânt va fi considerat o secvență de lungime arbitrară constând din litere și, de asemenea, înconjurat de caractere cu spații albe.

Să ne uităm la diagramă:

Din starea inițială ajungem la stare Început. Verificăm caracterul curent, iar dacă este o literă, atunci mergem la stat Cuvânt de-a lungul săgeții marcate ca Scrisoare. Această stare presupune că în prezent luăm în considerare un cuvânt, analiza altor simboluri fie va confirma această presupunere, fie o va infirma. Deci, luați în considerare următorul caracter, dacă este o literă, atunci starea nu se schimbă (rețineți săgeata circulară marcată ca Scrisoare). Dacă caracterul nu este o literă, ci corespunde unui caracter alb, atunci aceasta înseamnă că presupunerea a fost corectă și am găsit cuvântul (urmăm săgeata Spaţiuîntr-o stare Început). Dacă caracterul nu este nici o literă, nici un spațiu, atunci am făcut o greșeală în presupunere și succesiunea pe care o luăm în considerare nu este un cuvânt (urmați săgeata Necunoscutîntr-o stare Sari peste).

În stare să Sari peste suntem acolo până când este întâlnit un caracter alb. După ce a fost detectat un gol, urmăm săgeata Spaţiuîntr-o stare Început. Acest lucru este necesar pentru a sări peste o linie care nu se potrivește cu modelul nostru de căutare.

După intrarea în stat Început, ciclul de căutare se repetă de la început. Ramura de recunoaștere a numerelor este similară cu ramura de recunoaștere a cuvântului.

Automatizează folosind instrucțiunile comutatorului

Primul este posibil afirmă:

După care repetăm ​​peste linie, introducând simbolul curent în mașină. Automatul în sine este o instrucțiune de comutare care efectuează mai întâi o tranziție la secțiunea stării curente. În interiorul secțiunii există un construct if-else, care, în funcție de eveniment (un simbol de intrare), schimbă starea curentă:

pentru (size_t i = 0 ; i ! = length; ++ i) ( const char current = text[ i] ; switch (state) (case State_Start: if (std:: isdigit (current) ) ( stare = State_Number; ) else if (std:: isalpha (curent) ) ( stare = State_Word; ) break ; Aici ne uităm la diagramă - starea curentă Număr Spaţiu, eveniment

FoundNumber() ;

stare = State_Start;

) else if (! std::isdigit(current) ) ( stare = State_Skip; ) break ;

case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) else if (! std:: isalpha (current) ) ( stare = State_Skip; ) break ;

caz State_Skip: if (std::isspace (current) ) ( stare = State_Start; ) break ;

) )

Completarea tabelului:

AddTransition(Start_Start, Event_Letter, State_Word) ;

AddTransition(Număr_de stat, Spațiu_Eveniment, Stare_Start) ; AddTransition(Număr_de stat, Literă_Eveniment, Omitere_stare) ; AddTransition(Număr_de stat, Eveniment_Necunoscut, Stat_Omitere) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ;

FoundNumber() ;

AddTransition(State_Skip, Event_Space, State_Start) ;

A ieșit destul de clar. Prețul pentru claritate va fi funcționarea mai lentă a mașinii, care, totuși, adesea nu contează.

Pentru ca mașina, atunci când apar anumite evenimente, să poată notifica un cod, îl puteți adăuga la structură cu informații despre tranziție (

Tranziţie

) indicatorul funcției (

Acţiune

FoundNumber() ;

), care se va numi:

typedef void (DynamicMachine::* Action) () ;

struct Tranziție ( State BaseState_; Events Event_; States TargetState_; Action Action_; ) ;

... void AddTransition(State din stat, eveniment Evenimente, State la stat, acțiune de acțiune) ;

...AddTransition(State_Number, Event_Space, State_Start, & DynamicMachine::FoundNumber) ;

Flexibilitate și vizibilitate

Rezultatul se obține în detrimentul consumului de memorie.

Și statele înseși. În interiorul stărilor, este necesar să se determine tipul care descrie tranzițiile ( reactii), iar dacă există mai multe tranziții, atunci enumerați-le în lista de tip boost::mpl::list. Al doilea parametru de șablon stare_simplu– tip care descrie mașina. Tranzițiile sunt descrise de parametrii șablonului de tranziție, o pereche Eveniment - Următorul stat:

struct Cuvânt: boost::statechart::simple_state

FoundNumber() ;

);

struct Skip: boost::statechart::simple_state

( typedef boost::statechart::transition

reacții;

);

)

Mașina este construită, tot ce rămâne este să o inițializați și o puteți utiliza:

Mașină mașină;

Am publicat deja o serie de articole despre scrierea inteligenței artificiale folosind o mașină cu stări finite. Dacă nu ați citit încă această serie, o puteți face acum:

Ce este o mașină cu stări finite?

O mașină cu stări finite (sau pur și simplu FSM - mașină cu stări finite) este un model de calcul bazat pe o mașină cu stări ipotetice. O singură stare poate fi activă la un moment dat. Prin urmare, pentru a efectua orice acțiune, mașina trebuie să își schimbe starea.

Mașinile de stat sunt de obicei folosite pentru a organiza și reprezenta fluxul de execuție a ceva. Acest lucru este util în special atunci când implementați AI în jocuri. De exemplu, pentru a scrie „creierul” unui inamic: fiecare stare reprezintă un fel de acțiune (atac, eschiv etc.).

O mașină cu stări finite poate fi reprezentată ca un grafic, ale cărui vârfuri sunt stări, iar muchiile sunt tranziții între ele. Fiecare margine are o etichetă care indică când ar trebui să aibă loc tranziția. De exemplu, în imaginea de mai sus puteți vedea că aparatul va schimba starea „rătăcire” în starea „atac”, cu condiția ca jucătorul să fie în apropiere.

Planificarea stărilor și tranzițiile lor

Implementarea unei mașini cu stări finite începe cu identificarea stărilor sale și a tranzițiilor dintre ele. Imaginați-vă o mașină de stat care descrie acțiunile unei furnici care transportă frunze la un furnicar:

Punctul de plecare este starea „găsește frunza”, care rămâne activă până când furnica găsește frunza. Când se întâmplă acest lucru, starea se va schimba în „du-te acasă”. Această stare va rămâne activă până când furnica noastră ajunge la furnicar. După aceasta, starea se schimbă din nou în „găsește frunza”.

Dacă starea „găsește frunza” este activă, dar cursorul mouse-ului este aproape de furnică, atunci starea se schimbă în „fugi”. Odată ce furnica se află la o distanță suficient de sigură de cursorul mouse-ului, starea se va schimba înapoi la „găsi frunza”.

Vă rugăm să rețineți că atunci când mergeți acasă sau departe de casă, furnica nu se va teme de cursorul mouse-ului. De ce? Dar pentru că nu există o tranziție corespunzătoare.

Implementarea unei mașini simple cu stări finite

O mașină cu stări finite poate fi implementată folosind o singură clasă. Să-i spunem FSM. Ideea este de a implementa fiecare stare ca metodă sau funcție. Vom folosi, de asemenea, proprietatea activeState pentru a determina starea activă.

Clasa publică FSM ( private var activeState:Function; // pointer către starea activă a mașinii funcția publică FSM() ( ) public function setState(state:Function) :void ( activeState = state; ) public function update() :void (dacă (activeState != null) (activeState(); ) ) )

Fiecare stare este o funcție. Mai mult, astfel încât va fi apelat de fiecare dată când cadrul de joc este actualizat. După cum sa menționat deja, activeState va stoca un pointer către funcția de stare activă.

Metoda update() a clasei FSM trebuie numită fiecare cadru al jocului. Și, la rândul său, va apela funcția statului care este activ în prezent.

Metoda setState() va seta noua stare activă. În plus, fiecare funcție care definește o anumită stare a automatului nu trebuie să aparțină clasei FSM - acest lucru face clasa noastră mai universală.

Folosind o mașină de stat

Să implementăm un AI pentru furnici. Mai sus am arătat deja un set de stări și tranziții dintre ele. Să le ilustrăm din nou, dar de data aceasta ne vom concentra pe cod.

Furnica noastră este reprezentată de clasa Furnicilor, care are un câmp cerebral. Aceasta este doar o instanță a clasei FSM.

Clasa publică Ant ( public var position:Vector3D; public var velocity:Vector3D; public var brain:FSM; public function Ant(posX:Number, posY:Number) (poziție = new Vector3D(posX, posY); viteza = new Vector3D( -1, -1); brain = new FSM(); anthill */ public function goHome() :void ( ) /** * State "runAway / public function runAway() :void ( ) public function update():void ( // Actualizați mașina de stat. Această funcție va apela". // funcția de stare activă: findLeaf(), goHome() sau runAway( );

Clasa Ant conține și proprietăți de viteză și poziție. Aceste variabile vor fi folosite pentru a calcula mișcarea folosind metoda lui Euler. Funcția update() este apelată de fiecare dată când cadrul de joc este actualizat.

Mai jos este o implementare a fiecărei metode, începând cu findLeaf() - starea responsabilă pentru găsirea frunzelor.

Funcția publică findLeaf() :void ( // Mută ​​furnica pe frunză. viteza = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distanță (Jocul .instance.leaf, asta)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

stare goHome() - folosit pentru a face furnica să meargă acasă.

Funcția publică goHome() :void ( // Mută ​​furnica la viteza casei = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distanță( joc.instanță.acasă, asta)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Și, în sfârșit, starea runAway() este folosită atunci când te eschivi de cursorul mouse-ului.

Funcția publică runAway() :void ( // Mută ​​furnica departe de viteza cursorului = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Este cursorul încă în apropiere dacă ( distanță(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Nu, este deja departe. Este timpul să revenim la căutarea frunzei. brain.setState(findLeaf); ) )

Îmbunătățirea FSM: automat bazat pe stivă

Imaginați-vă că și o furnică în drum spre casă trebuie să fugă de cursorul mouse-ului. Iată cum vor arăta statele FSM:

Pare o schimbare banala. Nu, această schimbare ne creează o problemă. Imaginați-vă că starea actuală este „fugă”. Dacă cursorul mouse-ului se îndepărtează de furnică, ce ar trebui să facă: să meargă acasă sau să caute o frunză?

Soluția la această problemă este o mașină de stări bazată pe stivă. Spre deosebire de FSM simplu pe care l-am implementat mai sus, acest tip de FSM folosește o stivă pentru a gestiona stările. În partea de sus a stivei se află starea activă, iar tranzițiile apar atunci când stările sunt adăugate/eliminate din stivă.

Și iată o demonstrație vizuală a funcționării unei mașini de stări bazate pe stivă:

Implementarea unui FSM bazat pe stivă

O astfel de mașină de stare poate fi implementată în același mod ca una simplă. Diferența va fi utilizarea unei matrice de pointeri către stările necesare. Nu mai avem nevoie de proprietatea activeState, deoarece partea de sus a stivei va indica deja starea activă.

Clasa publică StackFSM ( private var stack:Array; public function StackFSM() ( this.stack = new Array(); ) public function update() :void (var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) public function popState() :Function ( return stack.pop(); ) public function pushState(state:Function) :void ( if (getCurrentState() != state) ( stack.push(state) ;) ) funcția publică getCurrentState() :Function ( return stack.length > 0 ? stack : null; ) )

Rețineți că metoda setState() a fost înlocuită cu pushState() (adăugând o stare nouă în partea de sus a stivei) și popState() (eliminând o stare din partea de sus a stivei).

Utilizarea FSM bazată pe stivă

Este important de reținut că atunci când se utilizează o mașină de stări bazată pe stivă, fiecare stare este responsabilă pentru a fi eliminată din stivă atunci când nu mai este necesară. De exemplu, starea atac() ar trebui să se elimine din stivă dacă inamicul a fost deja distrus.

Public class Ant ( (...) public var brain:StackFSM; public function Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Începeți prin a căuta creierul frunzei. pushState( findLeaf); (...) /** * State "findLeaf" * Forțează furnica să caute frunze */ public function findLeaf() :void ( // Mută ​​furnica pe frunză. viteza = new". Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y if (distanță(Game.instance.leaf, this));<= 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) ( // Nu, este deja departe. E timpul să ne întoarcem la căutarea frunzelor. brain.popState(); ) ) (...) )

Concluzie

Mașinile de stat sunt cu siguranță utile pentru implementarea logicii inteligenței artificiale în jocuri. Ele pot fi reprezentate cu ușurință sub formă de grafic, permițând dezvoltatorului să vadă toate opțiunile posibile.

Implementarea unei mașini de stare cu funcții de stare este o tehnică simplă, dar puternică. Pot fi implementate și mai multe împletituri de state folosind FSM.

Teoria automatelor

Definiția unei mașini și varietatea acesteia. Tabele și grafice ale tranzițiilor și ieșirilor. Mașini subautomate. Teorema automată redusă

Operații cu mașini

Transformarea unei mașini Mealy într-o mașină Moore și a unei mașini Moore într-o mașină Mealy. Echivalența automatelor. Distingerea stărilor automatelor. Minimizarea automatelor. Sinteza automatelor. Mașini de recunoaștere

O mașină automată este un sistem de mecanisme și dispozitive în care procesele de recepție, conversie și transfer de energie, materiale și informații sunt complet automatizate Termenul „mașină automată” este utilizat în două aspecte:

1) tehnic,

2) matematică.

În abordarea matematică, un automat este înțeles ca un model matematic al unui dispozitiv tehnic care trebuie să aibă intrări, stări interne și ieșiri. Nu ar trebui să existe informații cu privire la detaliile structurii dispozitivului.

În abordarea tehnică, o mașină este înțeleasă ca fiind un dispozitiv foarte real, de exemplu, o cabină telefonică, un automat de vânzare etc. În acest caz, desigur, sunt cunoscute detaliile structurii interne a dispozitivului.

Un caz special și important al unui automat este un automat digital (DA), în care procesele de primire, conversie, stocare și emitere a informațiilor digitale sunt complet automatizate.

Din punct de vedere al semnalelor DA, este util să se definească un sistem care poate recepționa semnale de intrare, sub influența lor, să treacă de la o stare la alta, să-l mențină până la sosirea următorului semnal de intrare și să producă semnale de ieșire.

Un DA este considerat finit dacă seturile de semnale de intrare X, stări S și semnale de ieșire Y sunt finite O mașină cu stări finite poate fi asociată cu un dispozitiv, cum ar fi un computer. Calculatorul procesează datele de intrare de intrare în date de ieșire (rezultat), dar acest rezultat corespunde nu numai datelor de intrare, ci și stării curente a computerului, adică. datele care sunt stocate în memoria computerului, de exemplu, rezultatele calculelor anterioare, programe de calcul.

Activitatea publicului țintă se desfășoară în timp automat, determinat de numărul de perioade de recepție a semnalelor de intrare.

Un automat abstract este un model matematic al unui dispozitiv discret care are un canal de intrare, care primește secvențe de simboluri ale unei limbi, un canal de ieșire, din care sunt preluate secvențe de simboluri ale unei alte limbi și se află într-o anumită stare în fiecare moment. de timp discret. Grafic, un automat abstract este prezentat în Fig.

Cuvintele limbajului de intrare pot fi reprezentate prin simboluri ale mulțimii X=(x 1 ,x 2 ,...x n ), care se numește alfabet de intrare, iar cuvintele limbajului de ieșire sunt simboluri ale mulțimii Y=(y 1 ,y 2 ,...y p ), care se numește alfabetul de ieșire. Mulțimea stărilor automatului S=(s 1 ,s 2 ,...s m ) se numește alfabetul statelor.

Concept starea mașinii este folosit pentru a descrie sisteme ale căror semnale de ieșire depind nu numai de semnalele de intrare la un moment dat, ci și de o istorie anterioară, adică semnale care au fost primite anterior la intrările sistemului. Prin urmare, automatele digitale se referă la circuite secvențiale, care, după cum sa menționat deja, au memorie. Conceptul de stare a unui automat corespunde unei amintiri a trecutului, deci introducerea acestui concept permite eliminarea timpului ca variabilă explicită, iar ieșirile să fie exprimate în funcție de stări și intrări.

Funcționarea unui automat abstract trebuie luată în considerare în raport cu anumite intervale de timp, deoarece fiecare interval discret t va corespunde semnalului său de ieșire y(t). În consecință, funcționarea mașinii este considerată prin intervale de timp discrete de durată finită. În teoria abstractă a automatelor digitale, se crede că semnalele de intrare acționează asupra unui automat sincron la începutul fiecărui i- acel interval (cuantum) de timp alocat de impulsul (ciclul) de sincronizare corespunzător, iar modificarea stărilor interne ale mașinii are loc în intervalele de timp dintre impulsurile de sincronizare adiacente, când nu există nicio influență a semnalelor de intrare.

Conceptul de „stare” este folosit pentru a stabili dependența funcțională a simbolurilor și/sau cuvintelor limbajului de ieșire generate de mașină de simbolurile și/sau cuvintele limbajului de intrare atunci când mașina implementează un anumit algoritm. Pentru fiecare stare a automatului sОS și pentru fiecare simbol xОX la momentul timpului discret [t], simbolul yОY este generat la ieșirea dispozitivului. Această dependență este determinată de funcția de ieșire a automatului j. Pentru fiecare stare curentă a automatului sОS și pentru fiecare simbol xОX la momentul timpului discret [t], automatul trece la următoarea stare sОS. Această dependență este determinată de funcția de tranziție a automatului y. Funcționarea automatului constă în generarea a două secvențe: o secvență a următoarelor stări ale automatului (s 1[ s 2 s 3 ...) și o secvență de simboluri de ieșire (y 1 y 2 y 3 ...), care pentru succesiunea de simboluri (x 1 x 2 x 3...) se desfășoară la momentele de timp discret t = 1,2,3,.... În paranteze dreptunghiulare indicați momentele de timp discret, care altfel se numesc cicluri de ceas. , în paranteze - secvențe de caractere ale alfabetelor X, Y și S.

Deci, modelul matematic al unui automat finit este o algebră cu trei de bază, ale cărei purtători sunt trei mulțimi X, Y și S, iar operațiile sunt două funcții j și y.

Teoria automatelor este o ramură a matematicii discrete care studiază modele de convertoare de informații discrete. Astfel de convertoare sunt atât dispozitive reale (calculatoare, organisme vii), cât și dispozitive imaginare (teorii axiomatice, mașini matematice). În esență, o mașină cu stări finite poate fi caracterizată ca un dispozitiv M , având canale de intrare și de ieșire, iar la fiecare dintre momentele discrete de timp, numite momente de ceas, se află într-una din stările finale.

Prin canal de intrare în fiecare moment de timp t =1, 2, ... la dispozitiv M sosesc semnale de intrare (de la un set finit de semnale). Legea schimbării stării la data următoare este setată în funcție de semnalul de intrare și de starea dispozitivului la ora curentă. Semnalul de ieșire depinde de starea și semnalul de intrare la ora curentă (Fig. 1).

O mașină cu stări finite este un model matematic de dispozitive reale discrete pentru procesarea informațiilor.

Mașină de stat numit sistem A= (X , Q , Y ,  ,  ), Unde X , Q , Y sunt mulțimi finite nevide arbitrare și  Şi  - functii, dintre care:

multe X ={o 1 , ..., o m ) se numește alfabet de intrare , iar elementele sale sunt semnale de intrare , secvențele lor sunt în în cuvinte comune ;

multe Q ={q 1 , ..., q n ) se numește multe state automatul și elementele sale - state ;

multe Y ={b 1 , ..., b p ) se numește alfabetul de ieșire , elementele sale sunt semnale de ieșire , secvențele lor sunt cuvinte de ieșire ;

funcţie  : X  Q Q numit funcția de tranziție ;

funcţie  :X  Q Y numit funcția de ieșire .

Astfel,  (x , q )Q ,  (x , q )Y pentru  x X , q Q .

O mașină cu stări finite este asociată cu un dispozitiv imaginar care funcționează după cum urmează. Poate fi într-una din multele state Q , percep semnale dintr-o varietate de X și emit semnale de la o varietate de Y .

2. Metode de specificare a unei mașini cu stări finite

Există mai multe moduri echivalente de a defini automatele abstracte, dintre care trei pot fi denumite: tabular , geometric Şi funcţional .

2.1 Sarcina tabulară a mașinii

Din definiția unui automat rezultă că acesta poate fi întotdeauna specificat printr-un tabel cu două intrări care conțin T linii şi n coloane, unde la intersecția stâlpului q și șiruri O sunt valorile funcției  (o i , q j ),  (o i , q j ).

2.2. Specificarea unui automat folosind o diagramă Moore

Un alt mod de a defini o mașină cu stări finite este grafic, adică folosind un grafic. Automatul este reprezentat ca un grafic direcționat etichetat G(Q , D ) cu multe vârfuri Q și multe arcuri D ={(q j ,  (o i , q j ))| q j Q , o i X ), în timp ce arcul ( q j ,  (o i , q j )) este marcat cu perechea ( o i ,  (o i , q j )). Astfel, cu această metodă, stările mașinii sunt descrise prin cercuri în care sunt scrise simboluri de stare q j (j = 1, …, n ). Din fiecare cerc se realizează T săgeți (margini orientate) unu-la-unu corespunzătoare caracterelor alfabetului introdus X ={o 1 , ..., o m ). Săgeată corespunzătoare literei o i X și părăsind cercul q j Q , este atribuită perechii ( o i ,  (o i , q j )), iar această săgeată duce la cercul corespunzător  (o i , q j ).

Desenul rezultat se numește graficul automatului sau, diagrama Moore . Pentru mașinile nu foarte complexe, această metodă este mai vizuală decât tabular.