Algoritmul este o contracepție fundamentală a informaticii, iar problema construirii dispozitivelor automate realizate pentru algoritmii date este una din întrebările de pin de proiectare a dispozitivelor microprocesoare pentru prelucrarea informațiilor. Toate dispozitivele existente de procesare a informațiilor sunt împărțite în două clase majore:
1) Traductoare funcționale
2) Automatele, în care rezultatul transformării informațiilor care intră în intrare, depinde nu numai de informațiile pe care le-a apărut la intrare, ci și de informațiile pe care le-au primit înainte de aceste automate. Astfel de dispozitive se numesc automate finite sau automate cu memorie (exemple de astfel de dispozitive sunt sisteme biologice). Pe același semnal de intrare, mașina de stare finită (SC) poate reacționa diferit, în funcție de starea în care se află în acest moment.
Când semnalul de intrare este recepționat, mașina de stat nu numai că transmite informații către ieșire, în funcție de această stare, ci și își schimbă starea, deoarece semnalul de intrare își schimbă istoricul.
Numărul de istorii de intrare ale oricărui automat finit este infinit, dar poate fi numărat. Dacă aparatul se comportă diferit pentru orice fundal posibil, atunci trebuie să aibă o resursă nesfârșită (memorie), astfel încât toate aceste preistorii să se fixeze într-un fel. Dacă introducem pe setul de preistorie ----, atunci două istorii pot fi considerate echivalente dacă au același efect asupra comportamentului suplimentar al automatului. Este evident că, pentru funcționarea sa, automatele trebuie să țină cont doar de clasa de echivalență de care aparține preistoria. În cazul în care există foarte multe astfel de clase de echivalență, aceasta este cea mai simplă, dar acest model matematic este de mare valoare practică și este folosit pe scară largă. Modelul formal corespunzător se numește automat automat.
Un model matematic al unui automat finit, starea internă a automatului este o clasă de echivalență a preistoriei. Se poate simplifica presupunerea că starea internă a automatului este tocmai caracteristica sa, care determină în mod unic toate reacțiile ulterioare ale automatului la un eveniment extern.
O mașină de stat finită este un dispozitiv care funcționează la momente discrete ale timpului (așa-numitele cicluri). În fiecare astfel de ciclu de tact, semnalele de intrare sunt aplicate la intrarea automatului și un semnal de ieșire apare pe ieșire, iar starea internă se modifică. Momentele de declanșare (ciclurile) sunt determinate fie de semnale speciale de sincronizare, fie de apariția unui eveniment extern, care constă în faptul că un nou semnal de intrare ajunge la intrarea automatului. În acest caz, se consideră că mașina este controlată de evenimente, iar ciclurile de funcționare ale mașinii au o durată diferită în funcție de sosirea semnalelor externe.
Concepte și definiții de bază ale automatelor finite
Un automat finit (Millie automaton) este un model matematic compus din 5 elemente: (S, X, Y, # 948; # 955;), unde:
S este un set finit de stări k>;
X este alfabetul final de intrare;
Y este alfabetul final de ieșire;
Dacă o stare inițială specială S0 este alocată în automatul finit. atunci acest automat este numit automat automat.
Două automate finite A1 și A2 sunt echivalente. Dacă hărțile de intrare / ieșire pe care le implementează sunt echivalente. Cele două funcții logice f1 și f2 sunt echivalente dacă au aceleași valori pe toate seturile de argumente, deoarece numărul de argumente ale funcției logice este finit, atunci este suficient să se compare valoarea acestor funcții cu toate seturile de argumente. Mașina de stat implementează un număr infinit de secvențe de intrare într-un set finit de semnale de ieșire, astfel încât mapările de intrare automatului> ieșire nu poate fi determinată prin simpla enumerare a hărților lor și să le compare cu valorile tuturor seturilor infinite. Pentru a determina echivalența automatelor, este necesară extinderea funcțiilor astfel încât funcțiile de tranziție și ieșire să fie definite pe seturile de secvențe de semnale ale alfabetului de intrare (lanțuri succesive) ale elementelor x.
Definiția 2.3 Fie A =
(e este un șir gol, alfa este lanțul propriu-zis
astfel Funcțiile extinse de tranziție și de ieșire sunt definite pe setul de secvențe de intrare (intrări de caractere), spre deosebire de funcțiile obișnuite de tranziție și de ieșire care sunt definite pe setul de semnale de intrare.
Cu alte cuvinte, pentru un automat dat A și funcțiile sale, dA și lA pot fi definite nu numai pe setul X al tuturor literelor de intrare, ci și pe setul X * al tuturor cuvintelor de intrare. Pentru orice cuvânt de intrare
Această definiție tradițională cu elipse este mult mai precisă și mai bine citită decât o definiție inductivă.
Funcția de tranziție este specificată:
a) d (Si, aj) este dată de tabelul automat;
b) pentru orice cuvânt aÎX * și orice scrisoare aj
Utilizarea funcției avansate # 948; este definit (și inductiv) funcția extinsă # 955; :
Fixăm în automatul A starea inițială S și fiecare cuvânt # 945; = aj aj. o asociază cuvântul # 969; alfabetul de ieșire Y:
unde Ùoperație de concatenare.
Această corespondență, care hărtește cuvintele de intrare în cuvintele de ieșire, se numește o mapare automată, precum și un operator automat (sau determinist limitat). Dacă rezultatul aplicării operatorului automat la cuvântul de intrare # 945; este cuvântul de ieșire , Atunci aceasta va fi notată cu A (S, # 945;) = # 969; sau A (# 945;) = # 969; cu | # 945; | = | # 969 ;. sau l (# 945;) = l (# 969;), adică cuvintele # 945; și # 969; au aceeași lungime.
cartografiere automaton are două proprietăți, care urmează în mod direct de la (2-5): un cuvânt și W au aceeași lungime (lungime de conservare de proprietate) și, în plus, mașini-operatori - o operatori Nonanticipatory, adică Operatorii care, atunci când procesează cuvântul de la stânga la dreapta, nu privesc înainte. Această proprietate reflectă faptul că litera i a cuvântului de ieșire depinde numai de primele litere i ale cuvântului de intrare.
Definiția 2.4
Definiția 2.5 Se spune că un automat A este puternic conectat. dacă orice alt stat poate fi atins de oricare dintre statele sale.
Definiția 2.6 Un automat este numit autonom. dacă alfabetul său de intrare este compus dintr-o literă X =.
Definiția 2.7 Se spune că un automat este definit parțial sau nu este complet definit. dacă cel puțin una dintre cele două funcții nu este complet definită. Într-o astfel de mașină automată pentru unele perechi (stare - intrare, stare - ieșire), valorile funcțiilor # 948; sau # 955; nu este definit. În tabelul automat, caracterul incomplet al automatului este exprimat în faptul că unele celule nu sunt umplute.
Definiție 2.8 Mașini cu stare finală A = și B = se spune că sunt echivalente. dacă sunt îndeplinite două condiții:
a) alfabetele de intrare coincide cu X = X = X;
b) mapările realizate de ele coincid: ( # 945;ÎX) # 955; (S. # 945;) = # 955; (S, # 945;).
Cu toate acestea, pentru a răspunde la întrebarea dacă automatele sunt echivalente, este imposibil să le rezolvăm reacțiile la toate lanțurile de intrare, deoarece există infinit multe dintre ele, astfel încât problema echivalenței navelor spațiale nu este banală. Metoda de rezolvare a acestei probleme se bazează pe conceptul de produs direct al automatelor.
Definiție 2.9 Un produs direct al automatelor finite A = și B = cu aceeași alfabet de intrare X (desemnată de AxB) este un automat:
AxB =, unde
a) (S. Î S) (S. Î S) (x ÎX) # 948; ((S, S), x) = (# 948; (S, x), # 948; (S, x));
b) (S. Î S) (S. ÎS) (x ÎX) # 955; ((S, S), x) = (# 955; (S, x), # 955; (S, x)).
componentwise multiplicatori, și funcțiile de tranziție și de ieșire sunt definite - Cu alte cuvinte, o mașină de stat, care este un produs direct a două nave spațiale ca și statele lor are o pereche de stări, mașini de pornire, starea sa inițială este o pereche de stări inițiale, alfabetul de ieșire - un set de perechi de mașini simboluri de ieșire . astfel produsul direct al unui vehicul spațial este pur și simplu două centrale neinteraționale din apropiere care operează sincron la o singură intrare comună
14. Metode de specificare a automatelor finite.
Aparatele care funcționează cu semnale logice, primind doar 2 valori - 0 și 1 și având o pluralitate de stări echivalente S interne, o pluralitate de semnal de intrare x și o multitudine de semnale de ieșire y - numit aparat digital.
Cel mai simplu automat automat este orice dispozitiv combinat care are o singură stare internă. În acest dispozitiv, fiecare set de variabile logice de intrare corespunde unui anumit semnal de ieșire. Dacă mașina poate fi în mai multe stări interne echivalente, răspunsul său la semnalele de intrare este determinat nu numai de setul curent de semnale de intrare, ci și de starea internă a automatului.
Se presupune că modificările semnalelor de intrare și ale stărilor interne apar instantaneu, astfel încât automatul funcționează în timp discret Ti, unde lungimea fiecărei măsuri (interval) poate fi arbitrar de mare.
Dacă în timp nu există nici o schimbare în semnalele de intrare x și, în consecință, stările interne ale lui S.
Sunt puști de mașină Moore și mitraliere Millie.
Automatul Moore este un caz special al unei noțiuni mai ample a automatului Mili.
Automatele Moore sunt descrise prin următoarele funcții de tranziție și ieșire:
Fiecare stare nouă a automatului Moore este condiționată de starea precedentă și de semnalul de intrare, iar funcția de ieșire - la fiecare moment dat de timp este determinată în mod unic de starea automatului.
Mașinile automate Miley diferă de mașinile Moore prin faptul că semnalul de ieșire din această mașină depinde nu numai de stare, ci și de semnalul de intrare.
Si + 1 = f (Si, xi + 1) yi + 1 = y (si, xi + 1)
Conceptul de stare internă a automatului presupune că automatul are memorie internă. Numărul de stări echivalente diferite depinde de adâncimea memoriei.
Ca elemente de memorie, pot fi utilizate module standard ROM sau bucle de feedback, în special diferite tipuri de declanșatoare.
În principiu, orice automotor Moore poate fi redus la o mașină Mili și invers.
Miley Automatic este un dispozitiv mai versatil
Masina Mile nu are astfel de restricții pe care le are Moore
Având în vedere setul (x s y), este destul de dificil să se determine modul în care funcționează mașina finită. Ecuațiile de mai sus care descriu funcționarea automatelor Moore și Mile stabilesc o conexiune între seturile x s y, dar sunt incomode pentru a descrie funcționarea automatelor specifice, astfel încât alte metode de descriere a funcționării automatelor finite au fost utilizate pe scară largă în practică.
Cea mai folosită masă în tabel, unde sunt date tabelele de tranziții și ieșiri ale automatului finit. Clădirea este finită sub forma unei scheme grafice, precum și alocarea automatelor finite sub formă de LHSA (schema logică a algoritmilor).
Luați în considerare atribuirea navei spațiale, care calculează și afișează suma pentru orice pereche de numere scrise în sistemul binar, iar datele încep cu biți care au cele mai mici cifre, iar numerele sunt citite de la dreapta la stânga.
(Biletele vor fi un exemplu cu declanșatoare, RS și altele)
În Tabelul 2.1, stările posibile sub forma unei secvențe ordonate sunt scrise în primul rând.
Semnalele de intrare sunt aranjate într-o formă comandată în prima coloană.
La intersecția rândurilor și coloanelor se obține o celulă în care este scris un nou stat.
Tabelul de tranziție (2.1) poate fi determinat incomplet. În acest caz, tabelul conține liniuțe în celule individuale.
Unele semnale nu produc schimbări de stare. Astfel, sub acțiunea semnalelor de intrare 0 și 1avtomat salvează starea S0, dacă era în ea, și starea S1, în cazul în care se aplică o astfel de combinație de semnale de intrare a fost în stare S1.
Setul de semnale de ieșire este definit în mod similar pentru fiecare pereche de Si, Lj și la intersecția rândului și coloanei corespunzătoare obținem semnalul de ieșire al automatului.
Valorile semnalului de ieșire al automatului sunt prezentate în Tabelul 2.2
Uneori, dacă există o astfel de oportunitate - ambele mese sunt combinate.
Pentru automatul Moore, tabela de ieșire degenerează într-o singură linie, care poate fi scrisă în prima linie a tabelului de tranziție.
Tabulare formalizate descriere oferă o limbă convenabilă în care să ceară orice mașină de stare finită, care asigură comunicarea între client și dezvoltator.
Un mijloc comun de a descrie un automat este o diagramă grafică logică a descrierii algoritmului.
15. Mașina de stat finit ca model al unui "sistem reactiv".
Ultima dată pentru programatorii care lucrează în domeniul informaticii, a devenit clar necesitatea alocării unei clase speciale de sisteme, numite sisteme reactive. Aceste sisteme sunt capabile să răspundă fluxului evenimentelor externe. Sa dovedit că modelul matematic al unui automat finit este un mijloc convenabil de a descrie astfel de sisteme. Ușor de utilizare a mașinii de stare finită a modelului matematic este că acest model are o claritate semantică, claritate și expresivitate și, în același timp, este destul de stricte și formale.
Totuși, sa dovedit că modelul matematic clasic al unui automat finit are o serie de deficiențe. Principalul dezavantaj al acestui model îl constituie lipsa mijloacelor pentru exprimarea ierarhiei statului, precum și aparatul matematic pentru afișarea întreruperilor și continuarea funcționării normale a sistemului după procesarea întreruperii.
O extensie simplă și destul de eficientă a modelului unui automat clasic finit este introducerea conceptului de "eveniment extern", a cărui ofensivă poate fi considerată o condiție pentru trecerea automatului într-o stare nouă. Astfel de evenimente pot fi considerate a fi recepționate un semnal la intrarea mașinii, întrerupând și declanșând cronometrul. Prin funcționarea temporizatorului, conceptul de timp din automat este asociat în mod natural. Într-adevăr, introducerea conceptului de timp într-un automat finit poate fi legată de restrângerea staționării unui automat într-o stare predefinită, concretă. O astfel de restricție, dacă este necesară, este cel mai bine stabilită de temporizatorul modelului matematic al automatului finit, funcționarea timerului ar trebui să determine automatul să treacă la o altă stare. Luați în considerare, de exemplu, specificarea unui proces care definește un singur clic sau un dublu clic pe un mouse. Amintiți-vă că un dublu clic este o secvență de două apăsări de taste, separate de un interval de timp t = 250ms. Reprezentăm graficul de tranziție al unui automat finit care rezolvă această problemă.
La primul clic al mouse-ului (faceți clic pe), mașina trece de la starea S0 la starea S1 și dacă înainte de următorul t = 250ms expiră un alt semnal (eveniment clic), atunci faceți clic pe \ . În oricare dintre aceste variante, automatul revine la poziția S0, iar operarea automatului se repetă.
16. Mașina de stat finit ca model al protocolului de transmitere a mesajelor în rețele.
Articole similare
Trimiteți-le prietenilor: