Definirea și metodele de specificare a mașinilor cu stări finite. Definiţia finite state machines

Este evident că k,r,s respectiv egal cu numărul de cifre din reprezentarea binară a numerelor t, p, r. De exemplu, dacă T - 5, n= 17, p = 3, apoi k= 3, r= 5, s = 2.

2. Codificarea stărilor simbolurilor de intrare și de ieșire ale sursei
maşină.

Fiecare q j Q punem în corespondență unu-la-unu o secvență binară de lungime r- cod binar = z 1 z 2 z r . În mod similar, pentru fiecare a i X și b k Y punem în corespondență unu-la-unu secvențele binare =x 1 x 2 x k ; =y 1 y 2 y s .

Rețineți că codificarea stărilor, a simbolurilor de intrare și de ieșire se poate face în mai multe moduri. În acest caz, unele secvențe (coduri) pot fi neutilizate.

3. Compilați următorul tabel:

Acest tabel contine k + r + r + s coloane şi 2 k + r linii. În primul rând k+r toate seturile de lungimi sunt listate în coloane k+r. Fiecare astfel de set corespunde unei perechi (), unde este un posibil cod al unei stări, codul simbolului de intrare.

4.Completarea ultimelor coloane din tabel (pasul anterior).

Pentru fiecare pereche (a i ,q j), unde a i X; q j Q , găsim codul și . Folosind tabelul automat (sau diagrama Moore) determinăm \|/(a; q) = Y. Apoi găsim codul = "1" 2...",. și codul .

La rândul tabelului corespunzător setului

adaugand setul

5. Definirea unui sistem de funcţii booleene.

După finalizarea pasului anterior, este posibil să descoperiți că toate rândurile din tabel sunt completate. Acest lucru se va întâmpla dacă cel puțin unul dintre numerele m, n nu este o putere de 2. Astfel, funcțiile nu vor fi complet definite - pe unele seturi valorile lor nu sunt definite. Apoi le definim în continuare într-un mod arbitrar. De regulă, funcțiile sunt definite în continuare în așa fel încât funcțiile complet definite rezultate să satisfacă anumite condiții de optimitate, de exemplu, acestea sunt reprezentate de DNF-uri minime.

După finalizarea acestui pas, automatul original va fi specificat de un sistem de funcții booleene complet definite

3.2 Limbi de început.

Ei descriu automatul la nivel comportamental. Limbile primare includ:

1) limbaje ale circuitelor logice și diagrame grafice ale algoritmilor;

2) limbajul expresiilor regulate ale algebrei evenimentelor;

3) gramatici formale și automate.

Dacă descrierea (4) a unui automat definit complet este dată în formă standard, atunci pentru orice stare inițială a automatului s(0) și secvențe de caractere introduse v(0)v(1)v(2)…v(t) puteți calcula răspunsul mașinii sub forma unei secvențe de simboluri de ieșire w(0)w(1)…w(t).

Exemple.

Exemplul 1. Ziarul VÂNZĂTOR primește monede în valori nominale de 1 rublă și 2 ruble. Dacă cantitatea de monede este egală cu 3 ruble, atunci mașina distribuie un ziar. Dacă suma este mai mare de 3 ruble, atunci mașina returnează toți banii. Să introducem denumirea simbolurilor de intrare și de ieșire și a stărilor mașinii.

Caractere introduse:

v 1 - se aruncă o monedă de 1 rublă;

v 2 - se aruncă o monedă în valoare de 2 ruble.

Caractere de ieșire:

w 1 - mesaj „A fost acceptată suma de 1 rublă.”;

w 2 - mesajul „Suma de 2 ruble acceptată.”;

w 3 - livrarea ziarelor;

w 4 - banii înapoi.

Mașina afirmă:

s 0 - suma acceptată este 0 rub. (starea inițială);

s 1 - suma acceptată este de 1 rub.;

s 2 - suma acceptată este de 2 ruble.

Prezentăm funcția de tranziție în tabelul 2 și funcția de ieșire în tabelul 3.

Același automat poate fi specificat sub forma unui digraf marcat, ale cărui vârfuri corespund stărilor automatului, iar arcele tranzițiilor (Fig. 3).

Mai jos este un exemplu de răspuns al mașinii VÂNZĂTOR la ​​secvența de intrare v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:

Exemplul 2. Pentru mașina VÂNZĂTOR considerată mai sus, este posibilă construirea unei mașini Moore echivalente, caracterizată printr-un tabel de tranziții/ieșiri (Tabelul 4).

Tabelul 4

Figura 4 prezintă graficul de tranziție/ieșire al mașinii VÂNZĂTOR, corespunzător Tabelului 4. Starea inițială a mașinii Moore echivalente include simbolul de intrare v(0). Prin urmare, este necesar să se schimbe fluxul de simboluri de intrare: .

Să descriem comportamentul unui părinte care și-a trimis fiul la școală. Fiul aduce în doi și cinci. Tatăl nu vrea să apuce cureaua de fiecare dată când fiul său primește o altă notă proastă și alege tactici parentale mai subtile. Este convenabil să se definească un automat printr-un grafic în care vârfurile corespund stărilor, iar o muchie de la starea s la starea q, etichetată x/y, este trasată atunci când automatul din starea s, sub influența unui semnal de intrare x , trece la starea q cu o reacție de ieșire y. Graficul unui automat care modelează comportamentul inteligent al unui părinte este prezentat în Fig. 5.

Orez. 5. Automat care descrie comportamentul unui tată „înțelept”.

Acest automat are patru stări (s0, s1, s2, s3) și două semnale de intrare - notele pe care le-a primit fiul meu la școală: (2,5). Pornind de la starea inițială s0 (este marcată de săgeata de intrare), mașina, sub influența semnalelor de intrare, trece de la o stare la alta și produce semnale de ieșire - reacții la intrări. Vom interpreta ieșirile mașinii (y0,..., y5) ca acțiuni ale părintelui, după cum urmează:

y0: - ia cureaua;

yl: - certa-ti fiul;

y2: - liniștește-ți fiul;

UZ: - speranta;.

y4: - bucură-te;

y5: - bucură-te.

Un fiu care primește aceeași notă - un D - va avea o reacție complet diferită față de tatăl său acasă, în funcție de mediul de studii. Tatăl își amintește cum a studiat fiul său înainte și își construiește educația ținând cont de succesele și eșecurile sale anterioare. De exemplu, după al treilea zeu din povestea 2,2, 2 fii vor fi întâmpinați cu brâu, iar în povestea 2, 2, 5, 2 se vor liniști. Fiecare istoric determină starea curentă a automatului, în timp ce unele istorice de intrare sunt echivalente (și anume cele care conduc automatul în aceeași stare): istoricul 2, 2, 5 este echivalent cu istoricul gol, care corespunde stării inițiale.

Starea actuală a automatului reprezintă tot ceea ce automatul știe despre trecut în ceea ce privește comportamentul său viitor - reacții la intrările ulterioare. Această istorie într-o formă concentrată este determinată de starea curentă, iar întregul comportament viitor al mașinii, ca reacție la semnalele de intrare ulterioare, este determinat exact starea actuală, dar nu cum a ajuns mașina la ea.

Deci, o mașină cu stări finite este un dispozitiv care funcționează la timpi (cicluri) discreti. La fiecare ciclu de ceas, unul dintre semnalele de intrare posibile este primit la intrarea mașinii cu stări finite, iar la ieșire apare un semnal de ieșire, care este o funcție de starea sa curentă și de semnalul de intrare primit. Se modifică și starea internă a mașinii. Momentele de funcționare (ciclurile) sunt determinate fie de semnale de tact forțat, fie asincron, de apariția unui eveniment extern - sosirea unui semnal.

Să definim formal un automat finit.

Pe lângă reprezentarea grafică pentru mașină, puteți utiliza și una tabelară, specificând funcțiile tranzițiilor și ieșirilor sub formă de tabele. Mașina exemplu va fi reprezentată de următoarele tabele.

Tabelul 5 O definește funcția de tranziție după cum urmează:

si masa 5, b definește funcția ieșirilor : .(s0, 2) = y2; (s2, 5) = y3; ....

Reprezentarea unui automat finit se reduce de fapt la descrierea funcțiilor automatului care îl definesc.

Există trei moduri de a defini mașinile cu stări finite:

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

· Grafic (folosind grafice);

· Analitice (folosind formule).

Metoda analitica– automatul este specificat printr-un sistem de ecuații. Dintr-un astfel de sistem rezultă că, cu un număr finit de stări interne posibile, numărul de valori posibile ale funcțiilor automate se dovedește, de asemenea, a fi finit. Un exemplu de astfel de sarcină este sistemul de ecuații care definesc automatele Mealy și automatele Moore

Metoda tabelară. Un tabel de stare al mașinii este compilat pentru funcția de tranziție – δ și funcția de ieșire. În acest caz:

· coloanele de tabel corespund elementelor alfabetului de intrare X,

· rândurile de tabel corespund stărilor (elementele unei mulțimi finite Q).

Intersecția i-lea rând și j-a coloană corespunde celulei (i, j), care este argumentul funcțiilor 8 și λ ale automatului în momentul în care acesta se află în stare qi la intrarea sa este un cuvânt xj, iar în celula cea mai potrivită scriem valorile funcțiilor 8 și λ. Astfel, întregul tabel corespunde setului Q X X.

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

În practică, funcțiile automate sunt specificate de două tabele finite, numite respectiv matricea de tranzițieŞi matricea de ieșire. În acest caz, rândurile sunt desemnate de literele alfabetului de intrare, iar coloanele de literele alfabetului intern (simboluri care codifică starea internă a mașinii).

În matricea de tranziție, la intersecția rândului x k și coloanei q r, valoarea funcției de tranziție δ(q i, X)și funcțiile de ieșire λ(q, X). În unele cazuri, ambele tabele sunt combinate într-un singur tabel.

Metoda grafică.

Automatul este specificat folosind un grafic, diagramă, grafic etc. Specificarea folosind un grafic direcționat este o formă mai convenabilă și mai compactă de descriere a automatului.

Graficul automat conţine

· vârfuri, corespunzătoare condiției qiÎQ,

· arcuri, vârfurile de legătură sunt tranziții ale automatului de la o stare la alta. Se obișnuiește să se indice pe arce perechi de semnale de intrare și de ieșire – semnale de tranziție.

Dacă mașina trece de la stat q 1într-o stare q 2 sub influența mai multor semnale de intrare, apoi pe arcul corespunzător al graficului această opțiune va fi reprezentată printr-o disjuncție. Pentru a reprezenta un automat, sunt utilizate grafice bipolare cu stări inițiale și finale distincte.

Dezvoltarea unei scale pentru un „dispozitiv de măsurare a capacității”

Fig.2.5. Graficul la scară al unui dispozitiv de măsurare a capacității

Concluzie

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

În partea teoretică a acestui curs au fost luate în considerare elemente ale generatoarelor de tip LC. De asemenea, au fost luate în considerare clasificarea generatoarelor de tip LC, scopul lor, precum și diferite circuite generatoare. Precum și caracteristicile tehnice ale elementelor generatoarelor.

În partea practică s-a abordat subiectul privind codificatoarele, decodoarele, scopul acestora și s-au conceput scheme electrice funcționale și circuite electrice ale encoderelor și decodoarelor. S-a dezvăluit subiectul hărților Carnot. A fost dezvoltat și segmentul „b” al indicatorului cu șapte segmente. A fost dezvoltată o mașină cu stări finite pentru scara unui dispozitiv de măsurare a capacității, precum și un grafic pentru aceasta.

Definiții de bază n Un automat finit este un sistem M =(A, B, S, y), în care n n n A = (a 1, . . . , am) este alfabetul de intrare finit, B =(b 1, . . . , bk ) - alfabetul final de ieșire, S =(s 1, . . . , sn) - alfabetul final al stărilor, : A S S - funcție de tranziție, y: A S B - funcție de ieșire. n Dacă într-un automat M este selectată o stare, numită inițială (de obicei se va presupune că acesta este s 1), atunci automatul rezultat se numește inițial și se notează (M, s 1). n Există două moduri de a defini un automat: Tabel de automate, diagramă de tranziție

Tabel automat n 1) 2) 3) 4) Exemplu: setați un automat să citească cuvântul „001” dacă caracterele introduse sunt „0” și „1”. Alfabetul de intrare A=(0, 1) Alfabetul de ieșire A=(Y, N) Alfabetul de stare S=(s 0 "", s 1 "0", s 2 "00" s 3 "001") Tabel automat în două moduri . este specificat de 1) Linii – stări ale mașinii. Coloanele sunt simboluri de intrare. La intersecția rândurilor și coloanelor sunt indicate funcțiile y. 2) S, A, y sunt specificate prin coloane. Exercițiul 25 Construiește un automat pentru a căuta cuvântul KAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 " 0" S 2, N S 0, N S 2 " 00" S 2, N S 3, Y S 3 " 001 " S 1 , N S 0, N S In 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 N S 1 S 2 S 3

Diagrama de tranziție n O diagramă de tranziție orientată numită grafic este un multigraf, tranzițiile sau graficul corespund stărilor. Dacă (Si, aj)=Sk, y(Si, aj)=bl, atunci se trasează un arc de la vârful Si la vârful Sk pe care se scrie (aj, bl) n La fiecare vârf si condiţiile de corectitudine sunt: ​​0 1 S 0 "" S 1, N S 0, N S 1 « 0» n Noduri, y S 2, N S 0, N S 2 « 00» S 2, N S 3, Y S 3 « 001» S 1, N S 0, N 1, N sunt îndeplinite 1) pentru orice litera de intrare aj are un arc emanat din si, pe care se scrie aj (condiția de completitudine); 2) orice litera aj apare doar pe o margine care iese 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

Automate și cuvinte de intrare n Pentru un automat M dat, funcțiile sale sunt 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 introduse. n Pentru orice cuvânt de intrare = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2... ajk) = y((... (si, aj 1), aj 2),... , ajk-1), ajk).

Exemplu: Automate și cuvinte de intrare Exemplu: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 "0" S 2, N S 0, N S 2 " 00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2) , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) = N, y S 2, N S 3, Y S 3 „001” S 1, N S 0, N

Maparea automată n Să fixăm starea inițială S 0 în M ​​și fiecare cuvânt de intrare = a 1 a 2. . . ak potrivim cuvântul din alfabetul de ieșire: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1... ak). (3 a) n Această corespondență, maparea cuvintelor de intrare cu cuvintele de ieșire, se numește mapare automată n Dacă rezultatul aplicării unui operator unui cuvânt este un cuvânt de ieșire, atunci vom desemna acest lucru în mod corespunzător M() = .

Exemplu: Mapare automată Potrivim cuvântul de intrare = 0101 cu un cuvânt din alfabetul de ieșire: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N , y 0 S 0 "" S 1, N S 0, N S 1 " 0" S 2, N S 0, N S 2 " 00" S 2, N S 3, Y 1 S 3 " 001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S) 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

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

Tipuri de automate Modelul general al unui automat finit (S-finit), despre care a fost discutat mai devreme, se numește automat Mealy. n Un automat se numește autonom dacă alfabetul său de intrare este format dintr-o literă: A = (a). Toate cuvintele de intrare ale automatului autonom sunt de forma aa. . . O. n Un automat finit se numește automat Moore dacă funcția sa de ieșire depinde numai de stări, adică pentru orice s, ai, aj y(s, ai) = y(s, aj). Funcția de ieșire a mașinii Moore este în mod natural cu un singur argument; este de obicei notat printr-o literă și numit funcția de marcare. În graficul unui automat Moore, rezultatul este scris nu pe muchii, ci la vârf.

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

Exemplu de automat 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 S S S S S A=(a) , B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S 9)

Stări care nu se pot distinge n Fie M și T două automate cu alfabete de intrare și ieșire identice. Starea s a automatului M și starea r a automatului T se spune că nu se pot distinge dacă pentru orice cuvânt de intrare M(s,) = T(r,). n Automatele M și T se numesc indistinguibile dacă pentru orice stare s a automatului M există o stare indistincbilă r a automatului T și, invers, pentru orice r din T există un s indistinguibil de M. n Stările care nu se pot distinge sunt numite echivalente

Automat minim n Trecerea de la un automat M la un automat echivalent se numește transformare echivalentă a unui automat M. n Puteți pune diverse probleme legate de găsirea de automate echivalente cu unul dat și având 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 - un automat minim.

Aspecte ale „lucrării” automatelor n Se pot distinge două aspecte principale ale „lucrării” automatelor: 1) automatele recunosc cuvintele de intrare, adică răspund la întrebarea dacă cuvântul dat ca intrare aparține unui anumit set (aceste sunt recunoscători de automate); 2) automatele convertesc cuvintele de intrare în cuvinte de ieșire, adică implementează mapări automate (convertoare automate).

AT în cadrul metamatematicii n Subiectul teoriei algoritmilor și sistemelor formale în cadrul metamatematicii - care obiecte și acțiuni asupra lor ar trebui considerate definite cu precizie, ce proprietăți și capacități au combinațiile de acțiuni elementare, ce pot și ce nu pot fi făcut cu ajutorul lor. n Aplicația principală a teoriei algoritmilor este demonstrarea imposibilității unei soluții algoritmice (adică, exactă și lipsită de ambiguitate) la anumite probleme matematice.

Algoritm n Un algoritm este o prescripție care specifică în mod unic procesul de conversie a datelor sursă la rezultatul necesar n Procesul de conversie în sine constă din pași elementari discreti, a căror aplicare de un număr finit de ori duce la rezultat

Principalele tipuri de algoritmi n Teoria algoritmilor este o metateorie care studiază diverse proprietăți (calitative și cantitative) ale algoritmilor. n Pentru studiul proprietăților calitative, sunt definite 3 tipuri principale de algoritmi: 1) Funcții recursive 2) Mașină Turing 3) Sisteme Canonical Post și algoritmi normali Markov.

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

Recursie primitivă n Funcția f(x 1…xn+1) este obținută prin algoritmul de recursie primitivă din funcțiile g(x 1…xn) și h(x 1…xn+2), dacă f(x 1, …xn , 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), unde z=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 suprapunere și recursivitate primitivă.

Exemplul n Pentru a demonstra că o funcție este recursivă primitiv, este necesar: 1) Conform ecuațiilor (1) și (2), definiți în mod explicit funcțiile g() și h(). 2) Să se arate că g() și h() sunt cele mai simple funcții S 1, On, Imn sau funcții recursive primitive dovedite anterior. Exercițiul 26: Demonstrați că funcția f(x, y) = x+y este recursivă primitivă Teza lui Church: Clasa funcțiilor numerice calculabile algoritmic coincide cu clasa tuturor funcțiilor recursive.

Mașina Turing n Mașina Turing conține: n 1) Memorie externă – o bandă de n celule. Fiecare i-a celulă este în starea ai. Este specificat alfabetul stărilor. Banda poate fi nesfârșită în ambele direcții. Stările goale sunt omise. n 2) Memoria internă a mașinii - dispozitivul este în prezent în starea qi. Este specificat alfabetul stării interne. Starea inițială q 1, starea finală q 0 sau qz. n 3) Pointer – indică către celula curentă și se deplasează de-a lungul benzii. n 4) Dispozitiv de control – citește simbolul celulei către care indică indicatorul. În conformitate cu programul, schimbă starea celulei și mută indicatorul.

Starea și programul MT n Starea unei mașini Turing se numește cuvântul n ​​n n n a 1…ak-1 qi ak…ar , format prin inserarea unui simbol de stare intern înaintea celulei care este observată. Un program de mașină Turing este un set de comenzi pe care o mașină qi aj qi' aj' D le poate executa, 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 pe celula monitorizată D = ( L, R, E) – simboluri care simbolizează deplasarea indicatorului cu o celulă la stânga, la dreapta și, respectiv, fără deplasare.

Exemplu MT Exercițiul 27: Găsiți starea finală a unei mașini Turing Alfabetul inițial: A = (0, 1) Alfabetul stării interne: Q = (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 de început: q 111

Exemplu MT Exercițiul 28 Găsiți starea finală a unei mașini Turing Alfabetul inițial: A = (0, 1, ) Alfabetul stării interne: Q = (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) Inițial cuvânt: q 11 111

Teza lui Turing Teza lui Turing: pentru fiecare algoritm A se poate construi o mașină Turing care, având aceleași date inițiale, dă aceleași rezultate ca și algoritmul A. n Dacă 1 q 1 2 1 qz 2, atunci vom spune că mașina T procesează cuvântul 1 2 în cuvântul 1 2 și notați-l T(1 2) = 1 2. n Notația T() este desemnarea mașinii T cu valorile originale.

Algoritmi Markov normali n Algoritmii Markov normali (NAM) transformă cuvinte de lungime finită unele în altele folosind substituție. n Sarcină NAM Substituții alfabetice u v Înlocuire finală u v n Exercițiul 29 Se dă algoritmul Markov normal: Alfabetul - alfabetul limbii ruse. Schema de substituire (Y U, L U, S M, V B, R T, T R, O X, N A) n Cuvânt inițial ELEFANT. n Găsiți ultimul cuvânt.

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

Eficiența algoritmilor A B C D E n 3 n 2 2 n 2+4 n n 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,16 h 164 secole* 10,4 ms 0,28,16 h 164 secole* zile 10176 secole 1000 ms 0,83 ore 1 ms

Teoria algoritmilor n Teoria algoritmilor - clasifică problemele după complexitate. În acest caz, numai sarcinile de recunoaștere sunt clasificate. n O sarcină de recunoaștere este o sarcină care răspunde la întrebarea: datele de intrare au o anumită proprietate. În cazul nostru: date de intrare - grafic, proprietate - graficul este 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 ciclului hamiltonian constă în a afla dacă un graf dat G are un ciclu hamiltonian și aparține clasei NP.

Exemple de probleme NP n Problema de satisfacție pentru funcțiile booleene: folosind o formulă booleană dată, aflați dacă există un set de variabile incluse în ea care o transformă în 1. n Problema clicului: folosind un grafic dat, aflați dacă acesta conține clicuri (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 forță brută n Inițial soluția nu este cunoscută. Prin urmare, se dovedește a fi important ca orice problemă aparținând clasei NP să poată fi rezolvată în timp exponențial prin căutarea prin toate combinațiile posibile n Ce se întâmplă în algoritmul de găsire a unui ciclu Hamilton.

Relația dintre P și NP n Fiecare problemă din P aparține lui 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 consideră că nu.

Relația dintre P și NP n Dacă se dovedește că P = NP 1) NP problemele vor fi rezolvabile î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 cheii publice, care este practic imposibil de decriptat. Dacă brusc P = NP, atunci multe secrete vor înceta să mai fie astfel.

NP–probleme complete n Cel mai serios motiv pentru a crede că P ≠ NP este existența unor NP probleme complete. n În mod informal!!!, 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 se reduce la problema rezolvării unei ecuații pătratice.

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

Baranov Viktor Pavlovici. Matematică discretă. Secțiunea 6. Automate finite și limbaje formale.

Cursul 31. Definirea și metodele de specificare a unei mașini cu stări finite. Sarcina de sinteză. Automate elementare

Curs 30. DEFINIȚIA ȘI METODE DE SPECIFICARE A UNEI MAȘINI FINITE.

PROBLEMA DE SINTEZA. MAȘINI ELEMENTARE

Schema cursului:

1. Definirea unei mașini cu stări finite.

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

1. Problema sintezei automatelor.
2. Automate elementare.
3. Problema completității bazei unui automat.
4. Metodă canonică de sinteză a unui automat.

1. Definiția mașinii de stări

SFE-urile nu țin cont de faptul că dispozitivele reale funcționează în timp. În comparație cu SFE, o mașină cu stări finite este un model mai precis al unui convertor de informații discrete. În același timp, conceptul de automat finit, ca orice model, este asociat cu o serie de ipoteze simplificatoare.

În primul rând, se presupune că intrarea și ieșirea mașinii în fiecare moment de timp pot fi în doar una dintr-un număr finit de stări diferite. Dacă un convertor real are un semnal de intrare continuu, atunci pentru a-l descrie folosind o mașină cu stări finite este necesar să se cuantizeze acest semnal. În definiția formală a unui automat, un set finit de stări de intrare și de ieșire ale automatului este numit alfabet de intrare și, respectiv, de ieșire, iar stările individuale sunt numite literele acestor alfabete.

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

Funcționarea mașinii este prezentată după cum urmează.

Intrarea mașinii primește semnale din alfabetul de intrare, ceea ce duce la apariția semnalelor la ieșire 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 SFE, care nu au memorie, automatul este un dispozitiv cu memorie, adică ieșirea automatului este determinată nu numai de intrare, ci și de istoric. Luând în considerare istoricul se realizează dependența semnalului de ieșire nu numai de intrare, ci și de starea curentă, pe care o notăm.

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

O mașină cu stări finite este un cvintuplu de obiecte.

un set finit numit alfabet de intrare; una dintre posibilele stări de intrare;

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

o mulțime finită numită alfabetul stărilor interne;

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

funcția ieșirilor mașinii: ; această funcție atribuie o valoare de ieșire fiecărei perechi intrare-stare.

Legea de funcționare a automatului: automatul își schimbă stările în funcție de funcție și produce semnale de ieșire în conformitate cu funcția:

1. Metode pentru specificarea unei mașini cu stări finite

1. Metoda tabelară de atribuire. Deoarece pentru funcții atât domeniile de definiție, cât și valorile aparțin unei mulțimi finite, acestea sunt specificate folosind tabele.

Exemplul 1. Definim automatul astfel: , .Definim functia folosind tabelul de tranzitie, iar functia folosind tabelul de iesire.

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

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

2. Metoda grafică de atribuire. Se folosește o diagramă de tranziție-ieșire. Este un multigraf orientat în care fiecărei stări interne a automatului îi corespunde un vârf. Tranzițiile automatului de la stare la stare sunt descrise prin săgeți, pe fiecare dintre care sunt scrise simbolul de intrare care provoacă această tranziție și simbolul de ieșire produs de automat.

Fig.1 Diagrama tranziție-ieșire

Exemplul 2. Este necesar să se construiască un automat care să funcționeze după cum urmează: la fiecare ciclu de ceas, următoarele cifre binare ale termenilor sunt primite la intrarea automatului, automatul produce cifra binară corespunzătoare a sumei lor. Pentru termeni de două cifre avem: , .

Mașina este în starea 1 dacă are loc o transportare la adăugarea biților anteriori și în starea 0 în caz contrar. Diagrama tranziție-ieșire este prezentată în Fig. 2.

1. Problema sintezei automatelor

Prin analogie cu problema sintezei SFE, se poate pune o problemă de sinteză pentru automate. Există un set nelimitat de mașini de bază. Este necesară asamblarea unei mașini automate cu o funcționare predeterminată. În acest caz, sarcina de sinteză se confruntă cu anumite probleme.

Să presupunem că trebuie să conectați ieșirea mașinii la intrarea mașinii. Acest lucru este posibil cu condiția ca, altfel, a doua mașină să nu înțeleagă semnalele care vin de la prima. Acest lucru duce la o situație confuză în care unele conexiuni nu sunt posibile.

Pentru a depăși acest obstacol, este introdus conceptul de automat structural, în care toate alfabetele (input, output și stări interne) sunt codificate în cuvinte binare.

Fie un set finit de elemente și un set de cuvinte binare de lungime, unde. Vom numi o mapare injectivă arbitrară codificarea unui set prin cuvinte binare.

Să codificăm alfabete pentru un automat arbitrar:

Să notăm intrarea, ieșirea și starea mașinii codificate la un moment dat, respectiv. Apoi legea de funcționare va fi prezentată în formular

Automatul rezultat după codificare se numește structural. Vom presupune că un automat structural are intrări binare, ieșiri binare, iar starea internă a automatului este specificată de un cuvânt binar de lungime. În fig. Figura 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 prin acestea se transmit informații binare. Nu vom da o definiție generală a unui circuit de automate structurale, acesta este similar cu SFE.

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

Din (3) rezultă că legea de funcționare a unui automat structural este dată de un sistem de funcții booleene.

1. Automate elementare

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

Să remarcăm mai întâi că un element funcțional care are o singură stare poate fi considerat un automat fără memorie.

Să trecem la automate cu două stări. Fie ca mașina să aibă o intrare binară și o ieșire binară care coincide cu starea internă:

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

Tabelul 3

Î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. Să presupunem, de exemplu, că în prima coloană a tabelului 3 ambele elemente sunt zerouri. Un astfel de automat, odată în starea 0, nu va mai ieși din el, adică va funcționa ca element funcțional. O analiză a situațiilor similare arată că pentru a obține un automat care nu este reductibil la un automat fără memorie, este necesar să se ceară ca fiecare coloană a tabelului 3 să conțină atât un zero, cât și unul. Există doar patru astfel de tabele.

Tabelul 4 Tabelul 5

Tabelul 6 Tabelul 7

Avem doar două automate simple, deoarece 7 se obține din 4 și 6 din 5 prin inversarea stărilor interne.

Mașina specificată în Tabelul 4 se numește întârziere sau declanșare:

adică această mașină întârzie semnalul cu un ciclu de ceas.

Mașina specificată în Tabelul 5 se numește declanșator cu o intrare de numărare sau -trigger. Starea mașinii este inversată dacă se primește un 1 la intrare și rămâne neschimbată dacă se primește un 0 la intrare:

Fie declanșatorul să fie în starea 0 la momentul inițial de timp Dacă la un moment dat declanșatorul este în starea 0, atunci aceasta înseamnă că un număr par de unități a ajuns la intrarea mașinii. Dacă starea este 1, atunci este impar. Astfel, flip-flop-ul numără numărul de unități la intrare, dar, deoarece are doar două stări, numără până la două.

La implementarea fizică a declanșatorilor, sunt utilizate două ieșiri: directe și inverse (Fig. 5). Dacă le schimbăm, atunci -triggerul va produce un automat specificat în tabelul 7, iar -triggerul va produce un automat specificat în tabelul 6.

1. Problema completității bazei unui automat

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

Eforturile matematicienilor de a obține un analog al teoremei lui Post pentru automate au fost fără succes. În 1964 M.I. S-a demonstrat pe scurt inexistența unui algoritm pentru determinarea completității unui sistem. În acest caz, sunt de interes variante ale teoremei de completitudine cu ipoteze suplimentare despre sistem. Să ne uităm la cele mai populare dintre ele.

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

Dovada. Să considerăm un automat arbitrar specificat prin relațiile (2) și să descriem circuitul său din automatele indicate, numită structură canonică (Fig. 6).

Schema constă din două părți.

Jumătatea stângă se numește partea de depozitare. Constă din declanșatoare, al căror set de stări formează starea mașinii: dacă în momentul de față

atunci asta înseamnă că mașina este în stare.

Jumătatea dreaptă se numește partea combinațională și reprezintă SFE. Intrări ale acestui circuit:

1. semnal de intrare a cuvântului binar al mașinii;
2. cuvânt binar starea internă curentă a mașinii.

1. semnal de ieșire a cuvântului binar al mașinii, care este implementat conform formulelor (3);
2. un cuvânt binar care ajunge la intrările flip-flops din partea de stocare și controlează memoria mașinii.

Să arătăm că semnalele de control al memoriei sunt funcții booleene ale acelorași variabile ca și ieșirea mașinii și, prin urmare, pot fi implementate de un sistem FE complet.

În fiecare moment de timp, semnalele de control al memoriei trebuie să transfere mașina de la o stare la alta. Pentru a face acest lucru, trebuie să schimbați starea fiecărui declanșator

-flip-flops-urile sau -flip-flops-urile utilizate în circuitul canonic au următoarea proprietate: pentru orice pereche de stări, există un semnal de intrare care transferă automatul de la o stare la alta. Să notăm acest semnal prin. Pentru un -flip-flop, deoarece starea în care este setat -flip-flop este egală cu semnalul de intrare. Pentru un declanșator: la intrare trebuie aplicat 0 pentru ca starea să nu se schimbe; la 1, astfel încât declanșatorul „se răstoarnă”.

Deci, sau în formă vectorială

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

Teorema este demonstrată.

1. Metodă canonică de sinteză a unui automat

Să ne uităm la această metodă folosind un exemplu specific.

Exemplu. Pe transportor, de-a lungul căruia se deplasează două tipuri de piese, este instalată 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ă construiți un circuit al unui astfel de automat folosind un declanșator și elementele „ȘI”, „SAU”, „NU”.

Sinteza automatului este împărțită în următoarele etape.

1. Construirea unui automat abstract.

Introducerea alfabetului. Alfabetul de ieșire este , unde C este coliziunea piesei, P este omisiunea acesteia. Stările interne ale automatului reflectă memoria acestuia despre care parte a grupului a format deja: . Pe măsură ce grupul se formează, mașina se deplasează ciclic prin aceste stări, fără a schimba starea când sosește o piesă necorespunzătoare. Diagrama tranziție-ieșire este prezentată în Fig. 7.

2. Codificarea alfabetelor.

Una dintre opțiunile posibile de codificare este prezentată în tabelele următoare.

Stare de intrare ieșire

3. Construirea structurii canonice a automatului.

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

Să găsim dependențele rezultatelor SFE de variabile, mai întâi în formă tabelară (Tabelul 8), pe baza cărora vom construi apoi formule

Tabelul 8

Aceste funcții sunt numite parțial definite deoarece nu sunt definite când. Pentru a reprezenta aceste funcții prin formule, ele sunt definite în continuare în așa fel încât să se 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 metode de minimizare a funcțiilor booleene, construim cea mai economică reprezentare a funcțiilor folosind formule pe baza:

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

DEFINIȚIA ȘI METODE DE SPECIFICARE A UNEI MAȘINI FINITE. PROBLEMA DE SINTEZA. MAȘINI ELEMENTARE