Baranov Victor Pavlovici. Matematică discretă. Secțiunea 6. Mașini cu stare finită și limbaje formale.

Lectură 31. Definiția și metodele de specificare a unei mașini cu stare finită. Problemă de sinteză. Automate elementare

Lectură 30. DEFINIREA ȘI METODE DE SETARE A AUTOMATORULUI FINITOR.

PROBLEMA DE SINTEZĂ. MAȘINI DE VÂNZARE

Planul de prelegeri:

1. Definiția unei mașini cu stare finită.

2. Metode pentru specificarea unei mașini cu stare finită.

1. Problema sintezei automatelor.
2. Automate elementare.
3. Problema completitudinii unei baze de automat.
4. O metodă canonică pentru sinteza unui automat.

1. Definiția unei mașini de stare

SFE-urile nu iau în considerare faptul că dispozitivele reale funcționează în timp. În comparație cu SFE, o mașină cu stare finită este un model mai precis al unui convertor de informații discrete. Mai mult, conceptul unui automat finit, ca orice model, este asociat cu o serie de presupuneri simplificatoare.

În primul rând, se presupune că intrarea și ieșirea automatului în fiecare moment al timpului poate fi doar într-un număr finit de stări diferite. Dacă un traductor real are un semnal de intrare continuă, atunci pentru a-l descrie folosind un automat finit, este necesar să cuantificăm acest semnal. În definiția formală a unui automat, un set finit de stări de intrare și ieșire a unui automat se numește alfabetul de intrare și ieșire, respectiv stările individuale sunt numite literele acestor alfabeturi.

În al doilea rând, se presupune că timpul se schimbă discret. Stările de intrare și ieșire corespund unei secvențe de timp discrete.Deoarece un moment în timp este determinat în mod unic de indexul său, din simplitate, vom presupune că timpul ia valorile 1, 2, ..., ... Intervalul de timp se numește tact.

Lucrările mașinii sunt următoarele.

Semnalele din alfabetul de intrare ajung la intrarea automatului, ceea ce duce la apariția de semnale la ieșirea din alfabetul de intrare. Dependența secvenței de ieșire de intrare depinde de structura internă a mașinii. Rețineți că, spre deosebire de SF-urile, care nu au memorie, un automat este un dispozitiv cu memorie, adică ieșirea automatului este determinată nu numai de intrarea sa, ci și de istoricul său. Istoricul este luat în considerare de dependența semnalului de ieșire nu numai de intrare, ci și de starea curentă, pe care o denotăm.

Să dăm o definiție formală a unui automat.

Cinci obiecte sunt numite mașină de stat

- un set finit numit alfabet de intrare; - una dintre stările de intrare posibile;

- un set finit, numit alfabet de ieșire; elementele acestui set determină stările posibile de ieșire;

- un set finit, numit alfabetul stărilor interne;

- funcția tranzițiilor mașinii:; această funcție atribuie o stare fiecărei perechi de „input-state”;

- funcția ieșirilor automate:; această funcție atribuie o valoare de ieșire fiecărei perechi input-state.

Legea de funcționare a mașinii: mașina își schimbă stările în funcție de funcție și generează semnale de ieșire în conformitate cu funcția:

1. Metode pentru specificarea unei mașini de stare

1. Modul de repartizare tabular. Deoarece pentru funcții și domenii de definiție și valori aparțin unui set finit, acestea sunt specificate folosind tabele.

Exemplu 1. Să definim automatul astfel:,. Definiți funcția folosind tabelul de tranziție, iar funcția folosind tabelul de ieșire.

Tabelul 1. Tabelul de tranziție Tabelul 2. Tabelul de ieșire

	condiție

	condiție

Dacă secvența de semnale la intrarea mașinii este cunoscută, atunci secvența de ieșire este determinată în mod unic de tabelele de tranziție și de ieșire.

2. Modul grafic de atribuire. Se folosește diagrama de tranziție-ieșire. Este un multigraf orientat în care un vertex corespunde fiecărei stări interne a automatului. Tranzițiile automatului de la stat la stat sunt reprezentate de săgeți, pe fiecare dintre acestea sunt scrise simbolul de intrare care provoacă această tranziție și simbolul de ieșire generat de automat.

Fig. 1 Diagrama de tranziție-ieșire

Exemplul 2. Este necesar să se construiască un automat care să funcționeze astfel: în fiecare ciclu de ceas, următoarele cifre binare ale termenilor ajung la intrarea automatului, automatul generează cifra binară corespunzătoare a sumei lor. Pentru termeni cu două cifre avem:.

Automatul este în starea 1 dacă se produce un transfer la adăugarea cifrelor anterioare, iar în starea 0 în caz contrar. Diagrama de tranziție-ieșire este prezentată în Fig. 2.

1. Problema de sinteză automată

Prin analogie cu problema sintezei SFE, putem pune problema sintezei pentru automate. Există un set nelimitat de automate de bază. Este necesară asamblarea unui automat cu o funcție predeterminată. În acest caz, problema de sinteză se confruntă cu anumite probleme.

Să presupunem că doriți să conectați ieșirea mașinii la intrarea aparatului. Acest lucru este posibil, cu condiția ca altfel cel de-al doilea automat să nu înțeleagă semnalele care provin de la primul. Aceasta duce la o situație confuză în care unele conexiuni nu sunt posibile.

Pentru a depăși acest obstacol, este introdus conceptul unui automat structural, în care toate alfabetele (intrare, ieșire și stări interne) sunt codate în cuvinte binare.

Să fie un set fin de elemente și să fie un set de cuvinte binare de lungime, unde. O mapare injectivă arbitrară va fi numită codarea setului prin cuvinte binare.

Să codificăm alfabetele pentru un automat arbitrar:

Să denotăm intrarea, ieșirea și starea automatului codat la momentul respectiv. Atunci legea funcționării va fi reprezentată ca

Automatul obținut după codificare se numește structural. Vom presupune că automatul structural are intrări binare, ieșiri binare, iar starea internă a automatului este dată de un cuvânt binar de lungime. În fig. 3 prezintă un automat abstract și automatul structural corespunzător.

Trecerea la un automat structural oferă două avantaje importante pentru sinteză.

1. Compatibilitatea intrărilor și ieșirilor, deoarece informațiile binare sunt transmise prin intermediul acestora. Nu vom da o definiție generală a unui circuit de automate structurale - este similară cu SFE.

2. Să notăm relațiile (2) în „coordonate”:

Din (3) rezultă că legea funcționării automatului structural este specificată de un sistem de funcții booleane.

1. Automate elementare

Să selectăm cele mai simple automate structurale și să le dăm un nume.

În primul rând, rețineți că un element funcțional cu o singură stare poate fi considerat ca un automat fără memorie.

Haideți să apelăm la automate cu două state. Lăsați automatul să aibă o intrare binară și o ieșire binară, care coincide cu starea internă:

Pentru a seta mașina prezentată în Fig. 4, este suficient să setați doar tabelul de tranziție:

Tabelul 3

	condiție

În loc de asteriscuri, trebuie să puneți 0 și 1. Acest lucru se poate face în 16 moduri, cu toate acestea, nu toate sunt acceptabile. De exemplu, să presupunem că în prima coloană a tabelului 3, ambele elemente sunt zero. Odată ajuns în starea 0, un astfel de automat nu îl va mai părăsi, adică va funcționa ca element funcțional. O analiză a situațiilor similare arată că, pentru a obține un automat care nu se reduce la un automat fără memorie, este necesar să fie necesar ca în fiecare coloană din tabelul 3 să existe atât zero cât și unul. Există doar patru astfel de tabele.

Tabelul 4 Tabelul 5

	condiție
					condiție

Tabelul 6 Tabelul 7

	condiție

	condiție

Avem doar două cele mai simple automate, deoarece 7 este obținut din 4, iar 6 din 5 prin inversarea stărilor interne.

Automatul specificat în tabelul 4 se numește întârziere sau -trigger:

adică acest automat întârzie semnalul cu un ciclu de ceas.

Aparatul specificat în tabelul 5 este denumit declanșator de intrare de numărare sau declanșator. Starea aparatului se schimbă în sens opus dacă intrarea este 1 și rămâne neschimbată dacă intrarea este 0:

Să presupunem că în momentul inițial al timpului declanșatorul este în starea 0. Dacă la un moment dat în timp, declanșatorul este în starea 0, atunci aceasta înseamnă că un număr egal de persoane au ajuns la intrarea automatului. Dacă în starea 1, atunci - ciudat. Astfel, declanșatorul numără numărul de la intrare, dar având în vedere că are doar două stări, el contează până la două.

În implementarea fizică a declanșatoarelor, sunt utilizate două ieșiri: directă și inversă (Fig. 5). Dacă le schimbăm, atunci -trigger va obține automatul specificat de tabelul 7, iar -trigger va produce automatul specificat de tabelul 6.

1. Problema completitudinii unei baze de automat

Un set de automate structurale se numește complet (sau o bază de automat) dacă orice automat structural dat poate fi construit din ele.

Eforturile matematicienilor de a obține un analog al teoremei Post pentru automate nu au fost încununate de succes. În 1964 M.I. S-a dovedit pe scurt inexistența unui algoritm pentru determinarea completitudinii sistemului. În acest caz, sunt interesante variantele teoremei complete cu ipoteze suplimentare despre sistem. Să-l considerăm pe cel mai popular.

Teorema. Un sistem de automate care conține un set complet de FEs și un -trigger (sau -trigger) este complet.

Dovada. Luați în considerare un automat arbitrar dat de relațiile (2) și descrieți circuitul acestor automate, numit structură canonică (Fig. 6).

Diagrama este formată din două părți.

Jumătatea stângă se numește partea de memorie. Se compune din declanșatori, al căror set de stări formează starea automatului: dacă în momentul de timp

atunci aceasta înseamnă că automatul este într-o stare.

Jumătatea dreaptă se numește partea combinată și reprezintă SPE. Intrările acestui circuit sunt:

1. cuvânt binar - semnal de intrare al mașinii;
2. cuvânt binar - starea internă actuală a aparatului.

1. cuvânt binar - semnalul de ieșire al mașinii, care este implementat conform formulelor (3);
2. un cuvânt binar care se îndreaptă către intrările de flip-flops în partea de memorie și controlează memoria aparatului.

Să arătăm că semnalele de control ale memoriei sunt funcții booleane ale acelorași variabile ca și ieșirea automatului, ceea ce înseamnă că pot fi implementate de un sistem FE complet.

În fiecare moment al timpului, semnalele de control al memoriei trebuie să transfere automatul de la stat la stat. Pentru a face acest lucru, trebuie să schimbați starea fiecărui declanșator.

-Trigger-urile sau -trigger-urile utilizate în schema canonică au următoarea proprietate: pentru orice pereche de stări există un semnal de intrare care transferă automatul de la stat la stat. Să denotăm acest semnal prin. Pentru un declanșator, întrucât starea de declanșare este setată la egal cu semnalul de intrare. Pentru un declanșator: la intrare, trebuie dat 0 astfel încât starea să nu se schimbe; la - 1 pentru declanșarea „flip-ului”.

Deci, sau sub formă vectorială

Să ne exprimăm din legea de funcționare a automatului (2). Apoi

Teorema este dovedită.

1. Metoda canonică de sinteză a unui automat

Să luăm în considerare această metodă cu un exemplu specific.

Exemplu. Pe transportor, de-a lungul căruia se mișcă părți de două tipuri și, există o mașină automată, a cărei sarcină este de a sorta piesele astfel încât după trecerea pe lângă mașină să formeze grupuri. Mașina împinge partea necorespunzătoare de pe transportor. Este necesar să se construiască un circuit al unui astfel de automat folosind un -trigger și elementele „AND”, „OR”, „NOT”.

Sinteza automatului se împarte în următoarele etape.

1. Construirea unui automat abstract.

Alfabet de intrare -. Alfabet de ieșire - în cazul în care C este ciocnirea piesei, P este săritura acesteia. Stările interne ale automatului reflectă memoria sa despre ce parte a grupului s-a format deja:. Pe măsură ce grupul este format, mașina se deplasează ciclic prin aceste stări, fără a schimba starea la sosirea unei părți improprii. Diagrama de tranziție-ieșire este prezentată în Fig. 7.

2. Codificarea alfabetelor.

Una din opțiunile posibile de codare este prezentată în următoarele tabele.

Stare de intrare

3. Construcția structurii canonice a automatului.

Structura canonică a automatului dezvoltat este prezentată în Fig. 8.

Să găsim dependențele ieșirilor SFE, de variabile, mai întâi într-o formă tabulară (tabelul 8), conform căruia vom construi în continuare formulele

Tabelul 8

Aceste funcții sunt numite parțial definite, deoarece nu sunt definite la. Pentru a reprezenta aceste funcții prin formule, acestea sunt redefinite astfel încât să obțină o formă mai simplă de formule.

4. Reprezentarea funcțiilor de ieșire a automatelor și a funcțiilor de gestionare a memoriei prin formule.

Folosind metodele de minimizare a funcțiilor booleane, construim reprezentarea cea mai economică a funcțiilor prin formule în baza:

5. Implementarea SFE și a circuitului final al mașinii (Fig. 9).

DEFINIREA ȘI METODE DE DEFINIRE A AUTOMATORULUI FINAL. PROBLEMA DE SINTEZĂ. MAȘINI DE VÂNZARE

Definiții de bază ale lui n Un automat finit este un sistem M \u003d (A, B, S, y), în care nnn A \u003d (a 1, ..., Am) este un alfabet de intrare finit, B \u003d (b 1, ..., Bk ) - alfabet de ieșire finală, S \u003d (s 1, ..., sn) - alfabet final de stări,: А SS - funcție de tranziție, y: А SB - funcție de ieșire. n Dacă un automat M conține o stare numită inițială (de obicei se presupune că este s 1), atunci automatul rezultat este numit inițial și notat cu (M, s 1). n Există două modalități de definire a automatului: tabelul Automaton, diagrama de tranziție

Tabel automat (n) 1) 2) 3) 4) Exemplu: setați automatul să citească cuvântul „001” dacă la intrare sunt caracterele „0” și „1”. Alfabet de intrare A \u003d (0, 1) Alfabet de ieșire A \u003d (Y, N) Alfabet de stat S \u003d (s 0 "", s 1 "0", s 2 "00" s 3 "001") Tabel automat pentru două moduri. set 1) Corzi - stări ale mașinii. Coloanele sunt caractere de intrare. Funcțiile, y, sunt indicate la intersecția rândurilor și coloanelor. 2) S, A, y sunt specificate prin coloane. Ex 25 Construiți un automat pentru găsirea cuvântului KAKADU SA 0 1 S 0 "" S 1, NS 0, NS 1 "0" S 2, NS 0, NS 2 "00" S 2, NS 3, YS 3 "001" S 1 , NS 0, NS În y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 NS 1 S 2 S 3

Diagrama de tranziție n Multigraf orientat, numit grafic, diagramă de tranziție, tranziții sau grafice corespund stărilor. Dacă (Si, aj) \u003d Sk, y (Si, aj) \u003d bl, atunci se trage un arc de la vertexul Si la vertexul Sk pe care este scris (aj, bl) n. La fiecare vertex si condițiile de corectitudine sunt: \u200b\u200b0 1 S 0 "" S 1, NS 0, NS 1 "0" n Vârfuri, y S 2, NS 0, NS 2 "00" S 2, NS 3, YS 3 "001" S 1, NS 0, N 1, N sunt executate 1) pentru orice scrisoare de intrare aj are un arc ieșit din si, pe care este scris aj (condiție de completare); 2) orice literă aj apare doar pe o margine ieșită din si (condiție de consistență sau determinism) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Automata și cuvinte de intrare n Pentru un automat M dat, funcțiile sale M și y. M poate fi definit nu numai pe setul A al tuturor literelor de intrare, ci și pe setul A * al tuturor cuvintelor de intrare. n Pentru orice cuvânt de intrare \u003d aj 1 aj 2.. ... ajk (si, aj 1 aj 2 ... ajk) \u003d ((... (si, aj 1), aj 2), ..., ajk-1), ajk). y (si, aj 1 aj 2 ... ajk) \u003d y ((... (si, aj 1), aj 2), ..., ajk-1), ajk).

Exemplu: Automate și cuvinte de introducere Exemplu: \u003d 0101 (S 1, 0101) \u003d ((S 1, 0), 1) (S 1, 0101) \u003d (((S 2, 1), 0), 1) (S 1, 0101) \u003d ((S 3, 0), 1) (S 1, 0101) \u003d (S 1, 1) (S 1, 0101) \u003d S 0 0 1 S 0 "" S 1, NS 0, NS 1 "0" S 2, NS 0, NS 2 "00" y (S 1, 0101) \u003d y ((((S 1, 0), 1) y (S 1, 0101) \u003d y (((S 2 , 1), 0), 1) y (S 1, 0101) \u003d y ((S 3, 0), 1) y (S 1, 0101) \u003d y (S 1, 1) y (S 1, 0101) \u003d N, y S 2, NS 3, YS 3 "001" S 1, NS 0, N

Mapare automată n Fixăm în M starea inițială S 0 și fiecare cuvânt de intrare \u003d a 1 a 2.. ... ak atribuim un cuvânt în alfabetul de ieșire: \u003d y (S 0, a 1) y (S 0, a 1 a 2). ... ... y (S 0, a 1 ... ak). (3 a) n Această corespondență, care mapează cuvintele de intrare în cuvintele de ieșire, se numește mapare automată n Dacă rezultatul aplicării operatorului unui cuvânt este un cuvânt de ieșire, atunci acesta va fi notat, respectiv, de M () \u003d.

Exemplu: mapare automată Cuvântul de intrare \u003d 0101 atribuim un cuvânt în alfabetul de ieșire: \u003d y (S 0, 0) y (S 0, 01) y (S 0, 0101). y (S 0, 0) \u003d N, y 0 S 0 "" S 1, NS 0, NS 1 "0" S 2, NS 0, NS 2 "00" S 2, NS 3, Y 1 S 3 "001 »S 1, NS 0, N y (S 0, 01) \u003d y ((S 0, 0), 1) \u003d y (S 1, 1) \u003d N y (S 0, 010) \u003d y ((S 0, 0), 1), 0) \u003d y ((S 1, 1), 0) \u003d y (S 0, 0) \u003d N y (S 0, 0101) \u003d y (((S 0, 0) , 1) \u003d y (((S 1, 1), 0), 1) \u003d y ((S 0, 0), 1) \u003d y (S 0, 1) \u003d NNNN

Proprietățile mapării automate 1) cuvintele și \u003d M () au aceeași lungime: | | \u003d | | (proprietatea păstrării lungimii); 2) dacă \u003d 1 2 și M (1 2) \u003d 1 2, unde | 1 | \u003d | 1 |, apoi M (1) \u003d 1; cu alte cuvinte, imaginea unui segment de lungime i este egală cu un segment al imaginii de aceeași lungime.

Tipuri de automate n Modelul general al unui automat finit (S-finit), care a fost considerat anterior, se numește automat Mealy. n Un automat se numește autonom dacă alfabetul său de intrare este format dintr-o literă: A \u003d (a). Toate cuvintele de intrare ale unui automat automat au forma aa. ... ... și. n Un automat finit se numește automat Moore dacă funcția sa de ieșire depinde doar de stări, adică pentru orice s, ai, aj, y (s, ai) \u003d y (s, aj). Funcția ieșirilor de automat ale lui Moore este în mod natural un argument; de obicei se notează printr-o literă și se numește funcția de marcare. În graficul automatului Moore, ieșirea este scrisă nu pe margini, ci pe vârf.

Moore automata n Teorema: Pentru orice automat Mealy există un automat Moore echivalent. n Când explorați capacitățile mașinilor, este suficient să folosiți mașini Moore Acest lucru este convenabil, deoarece un automat Moore poate fi vizualizat ca un automat fără ieșiri, ale căror stări sunt marcate în diferite moduri.

Un exemplu de mașină autonomă SA a S 1 S 3, 0 S 2 S 4, 0 S 3 S 4, 0 S 4 S 7, 0 S 5 S 4, 2 S 6 S 5, 0 S 7 S 6, 1 S 8 S 9, 0 S 9, 1 SSSSSA \u003d (a), B \u003d (0, 1, 2), S \u003d (S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S 9)

Stări nedistinguibile n Fie M și T două automate cu același alfabet de intrare și ieșire. Starea s a automatului M și starea r a automatului T se numesc indistinguibile dacă pentru orice cuvânt de intrare M (s,) \u003d T (r,). n Automatele M și T se numesc indistinguibile dacă pentru orice stare a unui automat M există o stare r a unui automat T nedistinguibilă de ea și, invers, pentru orice r de la T există o indistinguibilă de la ea de la M. n Stările indistinguibile se numesc echivalente

Automat minim n O tranziție de la un automat M la un automat echivalent se numește transformare echivalentă a unui automat M. n Se pot pune diverse probleme cu privire la găsirea de automate care sunt echivalente cu unul dat și au proprietăți date. Cea mai studiată dintre astfel de probleme este problema minimizării numărului de stări ale unui automat: printre automatele echivalente cu M, găsiți un automat cu cel mai mic număr de stări - automatul minim.

Aspectul „lucrării” automatelor n Se pot distinge două aspecte principale ale „lucrării” automate: 1) automat recunoaște cuvinte de intrare, adică răspund la întrebarea dacă cuvântul dat la intrare aparține unui set dat (acestea sunt automate); 2) automat transformă cuvintele de intrare în cuvinte de ieșire, adică implementează mapări automate (convertoare automate).

TA în cadrul metamatematicii n Subiectul teoriei algoritmilor și sistemelor formale în cadrul metamatematicii este ceea ce obiectele și acțiunile asupra lor ar trebui considerate ca fiind definite cu exactitate, ce proprietăți și capabilități au o combinație de acțiuni elementare, ce pot fi și nu pot fi realizate cu ajutorul lor. n Principala aplicare a teoriei algoritmilor este dovada imposibilității unei soluții algoritmice (adică exacte și fără ambiguitate) a unor probleme matematice.

Algoritm n Algoritmul este o prescripție care specifică în mod unic procesul de transformare a datelor inițiale în rezultatul necesar n Procesul de conversie în sine constă din pași discrete elementari, a căror aplicare a unui număr finit de ori conduce la rezultat.

Tipuri de bază de algoritmi n Teoria algoritmului este o metateorie care studiază diversele proprietăți (calitative și cantitative) ale algoritmilor. n Pentru studiul proprietăților calitative, sunt identificate 3 tipuri principale de algoritmi: 1) Funcții recursive 2) Mașină de întărire 3) Sisteme de post Canonical și algoritmi normali Markov.

Cele mai simple funcții recursive n S 1 (x) \u003d x + 1 - funcția depinde de o variabilă x și este egală cu x + 1. n On (x 1 ... xn) \u003d 0 - funcție în funcție de n variabile și întotdeauna egal cu 0. n Imn (x 1 ... xn) \u003d xm - funcție în funcție de n variabile și întotdeauna egal cu valoarea variabilei xm

Recursiune primitivă n Funcția f (x 1 ... xn + 1) este obținută prin algoritmul de recursivitate primitivă din funcțiile g (x 1 ... xn) și h (x 1 ... xn + 2) dacă f (x 1, ... xn, 0) \u003d g (x 1,… xn) (1) f (x 1,… xn, y + 1) \u003d h (z), unde z \u003d f (x 1,… xn, y) (2) Funcția f se numește recursivă primitivă dacă poate fi obținut din cele mai simple funcții S 1, On, Imn printr-un număr finit de operații de superpoziție și recursivitate primitivă.

Exemplul n Pentru a demonstra că funcția este recursivă primitivă, este necesar: 1) Conform ecuațiilor (1) și (2), definiți explicit funcțiile g () și h (). 2) Arătați că g () și h () sunt cele mai simple funcții S 1, On, Imn sau funcții recursive primitive dovedite anterior. Exercițiul 26: Demonstrează că funcția f (x, y) \u003d x + y este teza recurentă primitivă a Bisericii: Clasa funcțiilor numerice calculabile algoritmic este aceeași cu clasa tuturor funcțiilor recursive.

Masina de intrare n Masina de intrare conține: n 1) Memorie externă - o bandă de n celule. Fiecare celulă I este în stare de aer. Alfabetul de state este setat. Banda poate fi interminabilă în ambele direcții. Sunt omise stările goale. n 2) Memoria internă a aparatului - dispozitivul se află în prezent în starea qi. Alfabetul de stat intern este setat. Starea inițială este q 1, starea finală este q 0 sau qz. n 3) Pointer - indică celula curentă și se deplasează de-a lungul benzii. n 4) Dispozitiv de control - citește caracterul celulei indicat de indicatorul. Schimbă starea celulei și mută indicatorul în funcție de program.

Stare și program MT n Starea mașinii Turing se numește cuvântul n n n n a 1 ... ak-1 qi ak ... ar, format prin introducerea unui simbol de stare internă în fața celulei observate. Programul Turing Machine este un set de comenzi care pot fi executate de mașină qi aj qi 'aj' D, unde qi este starea internă a mașinii aj este starea celulei monitorizate qi 'este noua stare a mașinii aj' este noul simbol scris în celula monitorizată D \u003d (L, R, E) - simboluri care simbolizează deplasarea indicelui de către o celulă spre stânga, spre dreapta și, respectiv, absența unei deplasări.

Exemplu MT Control 27: Găsiți starea finală a unei mașini Turing Alfabet inițial: A \u003d (0, 1) Alfabet de stare internă: Q \u003d (q 0, q 1, q 2) Program: (1) q 10 q 20 R, 2) q 20 q 01 E, 3) q 11 R, 4) q 21 R) Cuvânt inițial: q 111

Exemplu MT Control 28 Găsiți starea finală a mașinii Turing Alfabet inițial: А \u003d (0, 1,) Alfabet de stare internă: Q \u003d (q 0, q 1, q 2, q 3) Program: (1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L) A) Cuvânt inițial: q 111 1 B) Cuvânt inițial: q 11111

Teza lui Turing Teza lui Turing: pentru fiecare algoritm A, se poate construi o mașină de Turing, care, având aceleași date inițiale, dă aceleași rezultate ca algoritmul A. n Dacă 1 q 1 2 1 qz 2, atunci spunem că mașina T procesează cuvântul 1 2 în cuvântul 1 2 și notează acest lucru prin T (1 2) \u003d 1 2. n Înregistrarea T () este denumirea mașinii T cu valorile inițiale.

Algoritmi normali Markov n Algoritmi normali Markov (NAM) transformă cuvinte de lungime finită între ele folosind substituția. n Alocarea către US Alfabet Substitution u v Înlocuirea finală u v n Exercițiul 29 Algoritmul normal Markov este dat: Alfabetul - alfabetul limbii ruse. Schema de substituție (Y U, L U, SM, V B, R T, TR, O X, N A) n Cuvânt inițial SLON. n Găsiți cuvântul final.

Estimarea complexității algoritmilor n Să presupunem că funcțiile f (n) și g (n) măsoară eficiența a doi algoritmi, ele sunt de obicei numite funcții de complexitate a timpului. Spunem că ordinea creșterii unei funcții f (n) nu este mai mare decât cea a g (n) dacă există o constantă C pozitivă, astfel încât | f (n) |

Eficiența algoritmilor ABCDE n 3 n 2 2 n 2 + 4 nn 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1.024 s 100 ms 30 s 20.4 ms 0.28 h 4 * 1017 secole 0,56 h 11,6 zile 10 176 secole 1000 ms 0,83 h 1 ms

Teoria algoritmilor n Teoria algoritmilor - clasifică problemele în funcție de complexitate. În acest caz, numai sarcinile de recunoaștere sunt clasificate. n Sarcina de recunoaștere este o sarcină care răspunde la întrebarea: datele de intrare au unele proprietăți. În cazul nostru: date de intrare - grafic, proprietate - este graficul hamiltonian?

Clasele P și NP n Clasa de complexitate P: există un algoritm A care rezolvă problema în timp polinomial. n Clasa de complexitate NP - există un algoritm A care verifică soluția propusă în timp polinomial. n Problema unui ciclu hamiltonian este de a afla dacă un grafic dat G are un ciclu hamiltonian de clasa NP.

Exemple de probleme NP n Problema fiabilității funcțiilor booleane: aflați dintr-o formulă Booleană dată dacă există un set de variabile incluse în ea, care o transformă în 1.n Problemă despre un clic: conform unui grafic dat, aflați dacă conține cliche (subgrafe complete) de o dimensiune dată ... n Problema existenței unui ciclu hamiltonian într-un grafic. n Existența unei soluții întregi la un sistem de inegalități liniare.

Posibilitatea rezolvării problemelor NP prin enumerarea n Inițial, soluția nu este cunoscută. Prin urmare, se dovedește că este important ca orice problemă legată de clasa NP să poată fi rezolvată în timp exponențial prin enumerarea tuturor combinațiilor posibile de n, ceea ce se întâmplă în algoritmul pentru găsirea ciclului Hamilton

Relația dintre P și NP n Orice problemă de la P aparține NP. n Astfel, clasa NP include clasa P. În acest moment, nu se știe dacă clasele P și NP sunt aceleași, dar majoritatea experților cred că nu.

Raportul dintre P și NP n Dacă se dovedește că P \u003d NP 1) Problemele NP vor fi rezolvate într-un timp rezonabil. 2) Există o serie de probleme care folosesc în mod deliberat probleme de complexitate exponențială (adică presupunând că problema nu poate fi rezolvată). De exemplu, în criptografie există o secțiune despre criptarea cheilor publice, care este practic imposibil de decriptat. Dacă dintr-o dată P \u003d NP, atunci multe secrete nu vor mai fi.

Probleme NP complete n Cel mai important motiv de a crede că P ≠ NP este existența unor probleme complete NP. nInformal !!!, Problema Q se reduce la Problema Q dacă Problema Q poate fi rezolvată în timp polinomial pentru orice intrare, presupunând că soluția Problemei Q pentru o altă intrare este cunoscută. De exemplu, problema rezolvării unei ecuații liniare este redusă la problema rezolvării unei ecuații cvadratice.

Probleme NP-complete n O problemă NP-completă este o problemă din clasa NP, la care se poate reduce orice altă problemă din clasa NP. n Problemele complete NP formează un subset al problemelor „cele mai dificile” din clasa NP. Dacă pentru orice problemă completă NP se găsește un algoritm de soluție polinomială, atunci orice altă problemă din clasa NP poate fi rezolvată în timp polinomial. n Toate problemele NP enumerate sunt complete NP. Inclusiv problema ciclului Hamilton.

Reprezentarea unui automat finit se reduce de fapt la o descriere a funcțiilor automatului care îl definește.

Există trei modalități de definire a mașinilor cu stare finită:

· Tabular (matrici de tranziții și ieșiri);

· Grafic (folosind grafice);

· Analitice (folosind formule).

Mod analitic - automatul este dat de un sistem de ecuații. De la un astfel de sistem rezultă că pentru un număr finit de stări interne posibile, numărul de valori posibile ale funcțiilor automatului este, de asemenea, finit. Un exemplu de astfel de sarcină sunt sistemele de ecuații care definesc automatele Mealy și Moore

Mod tabular.Un tabel cu starea mașinii este compilat pentru funcția de tranziție - δ și funcția de ieșire. în care:

Coloanele tabelului corespund elementelor alfabetului de intrare X,

Rândurile tabelului corespund stărilor (elemente ale unui set finit Q).

Intersecția rândului i și coloanei j corespunde celulei (i, j), care este argumentul funcțiilor 8 și λ ale automatului în momentul în care se află în starea q ila intrarea sa - cuvântul x j,iar în celula cea mai potrivită notăm valorile funcțiilor 8 și λ. Astfel, întregul tabel corespunde setului Qx X.

La completarea tabelului de tranziție, fiecare celulă este identificată în mod unic de o pereche de simboluri: simbolul stării următoare și simbolul semnalului de ieșire.

În practică, funcțiile automate sunt definite prin două tabele finite, denumite în consecință matrice de tranziție și matrice de concluzii... În acest caz, liniile sunt notate cu literele alfabetului de intrare, iar coloanele cu literele alfabetului intern (simboluri care codifică starea internă a mașinii).

Matricea de tranziție la intersecția rândului x k și a coloanei q r conține valoarea funcției de tranziție δ (q i, x)și funcția de inferență λ (q, x)... În unele cazuri, ambele tabele sunt combinate într-o singură tabelă.

Mod grafic.

Un automat este specificat folosind un grafic, circuit, grafic etc. O atribuire folosind un grafic direcționat este o formă mai convenabilă și mai compactă de descriere a unui automat.

Grafic automat conține

· nodurile, corespunzător statului q iiQ,

· Arcs, vârfurile de conectare sunt tranziții ale automatului de la o stare la alta. Este obișnuit să se indice perechi de semnale de intrare și ieșire pe arcuri - semnale de tranziție.

Dacă automatul trece de la stare q 1în stare q 2sub influența mai multor semnale de intrare, apoi pe arcul corespunzător al graficului această opțiune va fi prezentată printr-o disjuncție. Pentru a reprezenta automatul, sunt utilizate grafice cu doi poli cu stări inițiale și finale selectate.

Dezvoltarea scării "dispozitivului de măsurare a capacitanței"

№	indicaţie	+	-	suprasarcină.	de pe	┤
0	afara. stat	1	0	0	0	nu
1	0	2	0	13	0	da
2	50	3	1	13	0	da
3	100	4	2	13	0	da
4	150	5	3	13	0	da
5	200	6	4	13	0	da
6	250	7	5	13	0	da
7	300	8	6	13	0	da
8	350	9	7	13	0	da
9	400	10	8	13	0	da
10	450	11	9	13	0	da
11	500	13	10	13	0	da
12	OV	0	0	0	0	nu
13	prăbușire	0	0	0	0	nu

Figura 2.5. Grafic pe scala instrumentului de capacitate

Concluzie

Întrucât utilizarea oscilatoarelor cu circuite oscilatorii (tip RC) pentru generarea oscilațiilor de înaltă frecvență nu este satisfăcătoare, a fost luat un circuit de tip LC pentru generatorul dezvoltat (un circuit în trei puncte cu cuplare autotransformator a fost luat ca un circuit de fază, elementul activ este un tranzistor).

În partea teoretică a acestei lucrări de curs au fost luate în considerare elementele generatoarelor de tip LC. Au fost, de asemenea, luate în considerare clasificarea generatoarelor de tip LC, scopul acestora, precum și diverse circuite generatoare. La fel ca și caracteristicile tehnice ale elementelor generatoare.

În partea practică, subiectul a fost dezvăluit privind scramblerele, decodificatoarele, scopul lor și s-au proiectat, de asemenea, diagrame electrice funcționale și electrice ale scramblerelor și decoderelor. Subiectul hărților Karnot a fost dezvăluit. Segmentul „b” al afișajului cu șapte segmente a fost, de asemenea, dezvoltat. A fost elaborată o mașină cu stare finită pentru scara unui contometru, precum și un grafic pentru aceasta.

PLANUL DE LECTURA

1. Mod tabular

2. Mod grafic de setare a mașinii

Pentru a defini o mașină S cu stare finită, este necesar să se descrie toate elementele setului S \u003d (A, X, Y, d, l), adică este necesar să se descrie alfabetele de intrare, ieșire și alfabetul de state, precum și funcțiile de tranziție d și iese l... În acest caz, dintre mulțimea A \u003d (a 0, a 1, ..., a n), este necesar să selectați starea inițială a0, în care automatul este la momentul t \u003d 0. Există mai multe modalități de a seta funcționarea mașinii, dar cele mai utilizate sunt tabulare și grafice.

1. Mod tabular

Cu această metodă, mașina Miles este descrisă prin două tabele: tabelul de tranziție și tabelul de ieșire.

Sari de masă

x j\un j
	d(a 0, x 1)		d(a n, x 1)
x m	d(a 0, x m)		d(a n, x m)

Masa de desfacere

x j \\ a j
	l(a 0, x 1)		l(a n, x 1)
x m	l(a 0, x m)		l(a n, x m)

Rândurile acestor tabele corespund semnalelor de intrare x (t), iar coloanele corespund stărilor. La intersecția coloanei a i și a rândului x j din tabelul de tranziție, starea a s \u003d d[a i, x j], în care automatul va trece de la starea a i sub influența semnalului x j; iar în tabelul de ieșire - semnalul de ieșire corespunzător y g \u003d l[a i, x j].

Tabel combinat de transferuri și rezultate ale mașinii Miles:

x j \\ a i
	d(a 0, x 1) / l(a 0, x 1)		d(a n, x 1) / l(a n, x 1)
x m	d(a 0, x m) / l(a 0, x m)		d(a n, x m) /l(a n, x m)

Definiția tabelelor de tranziție și ieșire descrie pe deplin funcționarea mașinii de stare, deoarece nu sunt specificate numai funcțiile de tranziție și ieșire în sine, ci și toate cele trei alfabeturi: intrare, ieșire și alfabetul de stări.

Pentru a defini un automat Moore, este necesară o tabelă, deoarece în acest automat semnalul de ieșire este determinat în mod unic de starea automatului.

Tabelul de tranziție marcat al automatului Moore:

y g	l(a 0)		l(a n)
x j\\ a c
	d(a 0, x 1)		d(a n, x 1)
x m	d(a 0, x m)		d(a n, x m)

Mașină de mile

x j \\ a i
	a 1 / y 1	a 2 / y 3	A 3 / y 2	a 0 / y 1
	a 0 / y 2	a 0 / y 1	A 3 / y 1	a 2 / y 3

Moore Assault Rifle

x j \\ x j

În acest tabel, fiecărei coloane i se atribuie, pe lângă starea a i, și semnalul de ieșire y (t) \u003d l(a (t)) corespunzător acestei stări. Tabelul de tranziție Moore FSM se numește marcat, deoarece fiecare stare este marcată cu un semnal de ieșire.

Iată câteva exemple de alocare tabulară a automatelor Mealy și Moore:

Aceste tabele pot fi utilizate pentru a găsi reacția automatului la orice cuvânt de intrare. De exemplu.

Pentru mașina Miles: Pentru mașina Moore:

x 1 x 2 x 2 x 2 x 1... x 1 x 2 x 2 x 2 x 1 ...

a 0 a 1 a 0 a 0 a 0 a 1 a 0 a 2 a 4 a 1 a 4

y 1 y 1 y 2 y 2 y 1 y 2 y 1 y 2 y 1 y 2

2. Mod grafic de setare a mașinii (setarea mașinii cu ajutorul unui grafic)

Această metodă se bazează pe utilizarea graficelor conectate direcționate. Vârfurile graficelor corespund stărilor automatului, iar arcurile corespund tranzițiilor dintre ele. Două vârfuri ale graficului a i și s sunt conectate printr-un arc direcționat de la i la s, dacă automatul are o tranziție de la i la s, adică. a s \u003d d(a i, x j). În automatul Mealy, arcul este marcat de semnalul de intrare x j, care a provocat tranziția și de semnalul de ieșire y g, care apare în timpul tranziției. Starea este scrisă în cercul care marchează partea de sus a graficului. De exemplu, pentru automatul Mealy dat mai sus, graficul are forma a), iar pentru automatul Moore pare b).