Ministerul Educatiei Federația Rusă Universitatea de Stat din Nijni Novgorod poartă numele. N.I. Lobaciovski

Facultatea de Matematică Computațională și Cibernetică

Dezvoltare educațională și metodologică pentru munca independentă a studenților la cursul „Teoria algoritmilor și logica matematică”

în timp ce studia tema „Conceptele de mașină cu stări finite și limbaj obișnuit. Operațiuni pe limbi obișnuite”

Nijni Novgorod 2000

Dezvoltarea metodologică este destinată lucrului independent al studenților de la specialitatea „Informatică aplicată” pe materialul temei „Concepte de mașini cu stări finite și limbaje obișnuite. Operații pe limbaje obișnuite”, care face parte din cursul de formare „Teoria algoritmilor și logica matematică”. Sunt introduse conceptul de limbaj formal și operațiile pe limbaje formale, inclusiv operațiile de bază teoretice de mulțimi. Este prezentat conceptul de automat finit (în versiuni deterministe și nedeterministe); limbajele obișnuite sunt o clasă de limbaje recunoscute de mașinile cu stări finite. Se arată că operațiile, uniunile, intersecțiile, adunările, concatenările și iterațiile nu părăsesc clasa limbajelor obișnuite. Sunt prezentați algoritmii corespunzători pentru sinteza mașinilor cu stări finite.

Compilat de:

profesori ai Departamentului de Informatică și Automatizare a Cercetării Științifice, Facultatea de Matematică Computațională și Informatică, Conferențiar UNN, Doctor în Științe Tehnice Kogan D.I. și asistentul Babkina T.S.

1. Conceptul de limbaj, exemple de limbi, operatii pe limbi.

Un alfabet este un set finit arbitrar nevid de simboluri; caracterele unui alfabet arbitrar se numesc litere. Ca exemple, vom indica alfabetul rus (cu sau fără includerea semnelor de punctuație), alfabetul latin, o combinație a acestor alfabete și multe cifre ale sistemelor numerice zecimale sau binare. În general, definim alfabetul ca o mulțime A = (a 1, a 2, ..., a n); printre literele alfabetului A poate exista și un caracter spațial special (litera goală este de obicei notat e (abrevierea engleză „empty” - goală).

Un cuvânt din alfabetul A este o secvență finită arbitrară a literelor sale; aceeași literă poate apărea de mai multe ori în această secvență. Lungimea cuvântului α (notația l(α)) este numărul de litere din acest cuvânt. Simbolul special λ va desemna singurul cuvânt care are lungime zero (cuvânt gol); ar trebui să se facă distincția între un cuvânt gol și un cuvânt e, format dintr-o literă goală; lungimea cuvântului e (spațiu) este egală cu unu. În alfabetul A = (a 1, a 2, ..., a n) puteți scrie n l cuvinte diferite de lungime l, unde l = 0, 1, 2, .... Setul tuturor cuvintelor din alfabetul A va fi notat cu A *. Să remarcăm în mod special că colecția A * include și cuvântul gol. Cardinalitatea setului tuturor cuvintelor din alfabetul A este numărabilă.

Dacă α și β sunt două cuvinte arbitrare din alfabetul A, atunci αβ este rezultatul atribuirii cuvântului β cuvântului α din dreapta. Pentru orice cuvinte α și β presupunem că

αλ= λα= α, αλβ= αβ.

O limbă din alfabetul A este un subset arbitrar de cuvinte L din A *. Numim un limbaj L finit dacă conține un set finit de cuvinte; o limbă L este infinită dacă conține un număr infinit de cuvinte. Totalitatea tuturor cuvintelor în rusă și a tuturor cuvintelor în engleză sunt exemple de limbi finite. O mulțime de înregistrări ale tuturor numere primeîn sistemul numeric zecimal sau binar este un limbaj infinit. Setul tuturor limbilor alfabetului A are cardinalitate continuă.

O limbă L din alfabetul A se numește universală dacă L=A *. Limba L

îl numim gol dacă mulţimea L este goală (L =).

Fie L 1 și L 2 limbi în alfabetul A. Prin L 1 L 2 și L 1 ∩ L 2 vom

denotă unirea și, respectiv, intersecția acestor limbi. Cuvântul α aparține unei uniuni a două limbi dacă aparține cel puțin uneia dintre ele; cuvântul α aparține intersecției a două limbi dacă aparține atât uneia, cât și celeilalte limbi. Fie L o limbă în alfabetul A; Fie L c să desemneze complementul acestui limbaj. Limba L c este formată din cuvinte din alfabetul A care nu fac parte din limbajul L: L c = A *\L. Operațiile de unire, intersecție și adunare sunt principalele operații teoretice de mulțimi.

Fie L 1 și L 2 limbi în alfabetul A. Vom nota cu L 1 \L 2

diferența dintre limbile L 1 și L 2. Un cuvânt α din A * este considerat ca aparținând L 1 \L 2 dacă și numai dacă aparține limbajului L 1, dar nu aparține limbajului L 2. Este evident că operația de diferență poate fi reprezentată prin teoreticul de bază

operații multiple: L 1 \L 2 =L 1 ∩ (L 2 )с.

În plus, introducem câteva operațiuni speciale pe limbi. Fie L 1 și L 2 limbi în alfabetul A. Fie L 1 ( L 2 să desemneze limbajul

definit astfel: cuvântul α aparține limbajului L 1 ( L 2 dacă și numai dacă acest cuvânt poate fi împărțit în două părți consecutive

(adică, prezentat sub forma α = α 1 α 2 ) astfel încât prima parte este un cuvânt al limbajului L 1 , iar a doua parte este un cuvânt al limbajului L 2 . Operația ( se numește concatenarea (legarea) limbilor. Semnul ( va fi adesea omis, apoi concatenarea limbilor L 1 și L 2 se scrie L 1 L 2. Limba L 1 L 2 se obține prin adăugarea de cuvinte de limba L 2 la cuvintele de limba L 1 ca terminații Rețineți că, dacă un cuvânt gol este adăugat la un cuvânt γ, atunci rezultatul va fi cuvântul γ Dacă limbile L 1 și L 2 sunt finite. iar prima limbă conține m cuvinte, iar a doua limbă conține n cuvinte, atunci limba L 1 L 2. este formată din cel mult mn cuvinte Dacă una dintre limbile L 1, L 2 este goală, atunci L 1 L 2 este, de asemenea, o limbă goală.

Să introducem operația de ridicare a unei limbi la o putere. Noi credem:

L0 =(λ);

L1 = L;

L2 = LL; Ln +1 = Ln L, n=2, 3, ...;

astfel, conceptul de grad L i al limbajului L este definit pentru orice i =0, 1, 2, 3,

L* =U Li.

i= 0

Operația introdusă se numește iterație. Rețineți că cuvântul gol aparține unei iterații a oricărei limbi. Un cuvânt nevid α aparține unei iterații a limbajului L dacă și numai dacă acest cuvânt poate fi împărțit într-un număr de părți succesive (subcuvinte), astfel încât fiecare parte să aparțină limbajului L. Dacă o limbă L constă din toate cuvintele cu o singură literă ale alfabetului A, atunci o iterație a acestei limbi este limba universală A*. Rețineți că pentru orice limbă L avem (L *)*=L *.

În multe limbi, se consideră uneori următorul operator unar ()+:

(L)+ =U L i .

i= 1

Limbile L * și L + diferă între ele doar într-un cuvânt gol. Cuvântul λ aparține întotdeauna limbajului L *. Aparține limbajului L + dacă și numai dacă aparține limbajului L .

2. Concepte de mașină cu stări finite și limbaj obișnuit.

În cibernetică, automatele sunt module implementate tehnic sau software concepute pentru a procesa informațiile primite. Mașină de stat este un modul care are un număr finit de stări posibile și funcționează în timp discret. În acest tutorial, mașinile cu stări finite sunt studiate ca dispozitive algoritmice abstracte concepute pentru a procesa cuvinte dintr-un alfabet de intrare fix. Presupunem că automatul începe să proceseze un cuvânt arbitrar α în alfabetul de intrare A dintr-o stare inițială special selectată. La fiecare ceas de timp discret, următoarea literă a cuvântului procesat ajunge la intrarea mașinii sub influența sa, mașina își schimbă starea; Starea în care va ajunge mașina este determinată de starea anterioară și de litera citită a cuvântului de intrare. Aparatul lucrează pe un cuvânt de lungime l cicluri. Rezultatul funcționării mașinii este determinat de starea în care se află la finalizare.

Formal, automatul finit K este definit ca o mulțime

К=(Q, A, q0 , g, F),

unde Q =(q 0, q 1, q 2, ..., q m) – set de stări ale automatului; A = (a 1, a 2, ..., a n) – alfabet de intrare; q 0 – o stare special selectată a mașinii, numită stare inițială; g – funcția de tranziție a mașinii finite,

care este o mapare de tip Q xA → Q (dacă g (q i,a j)=q k, atunci automatul din starea q i sub influența literei a j trebuie să treacă în starea q k); F este un subset special selectat de stări ale automatului, pe care îl vom numi în mod convențional „bun”, F Q .

starea în care se află automatul K după t cicluri de lucru pe acest cuvânt (aici t = 0, 1, 2, ..., p):

qα (0) =q0;

q α (1) = g (q α (0), a i 1 )

q α (2) = g (q α (1), a i 2 )

q α (p) = g (q α (p − 1), a i p)

Vom spune că cuvântul α este acceptat de automatul K dacă q α (р) F.

Să introducem limbajul L(K): cuvântul α aparține limbajului L(K) dacă acest cuvânt este acceptat de automatul K. Limbajul L(K) se numește limbajul recunoscut de această mașină cu stări finite. Numim un limbaj L obișnuit dacă este posibil să construim un automat finit de recunoaștere pentru el.

Este convenabil să definiți o mașină cu stări finite prin diagrama de tranziție. Diagrama este un grafic dirijat, ale cărui vârfuri sunt identice cu stările automatului; un arc de la vârful q i la vârful q k cu litera a j scrisă deasupra se trasează dacă și numai dacă g (q i,a j)=q k. În cazul în care trecerea de la q i la q k se realizează sub influența oricăreia dintre literele unui anumit submult S, S A, toate literele acestui subset sunt semnate deasupra arcului corespunzător (în loc de o listă a tuturor literelor, intrarea prescurtată „x S” sau pur și simplu „S” este permisă). Dacă o stare arbitrară q i este inclusă în F, atunci acest fapt este marcat pe diagramă cu un cerc aldin care evidențiază vârful q i.

Evident, orice mașină cu stări finite este complet definită de diagrama sa de tranziție. Mai mult, sarcina de a construi un automat finit cu anumite proprietăți va fi înțeleasă ca sarcina de a construi o diagramă a tranzițiilor sale.

În fig. Figura 2.1 prezintă o diagramă a automatului K 1 care lucrează pe cuvinte din alfabetul A =(a,b,c). Automatul are două stări, q 0 și q 1, și numai starea q 1 este „bună”. După ce a început lucrul în starea q 0, mașina nu părăsește această stare sub influența literelor a, b; sub influența literei c se realizează o trecere la starea q 1; orice altă scrisoare care sosește lasă mașina în aceeași stare. Astfel, automatul K 1 recunoaște limbajul L 1, format din cuvinte care conțin litera c. Acest limbaj este regulat.

q0 q1

Să mai dăm câteva exemple de limbi obișnuite în același alfabet: L 2 - un set de cuvinte în care litera a apare de un număr par de ori; L 3 - un set de cuvinte care încep și se termină cu aceeași literă; L 4

Un set de cuvinte care conțin subcuvântul α =abbc ; L 5 este un set de cuvinte, la citirea de la stânga la dreapta, diferența dintre numărul de litere a și b întâlnite nu depășește niciodată 2. Diagrame ale mașinilor cu stări finite K 2 - K 5 care recunosc limbile L 2 - L 5 , respectiv, sunt prezentate în Figurile 2.2 - 2.5. Mașina „reține” informații despre partea procesată a cuvântului de intrare în funcție de starea sa. Deci, de exemplu, automatul K 5, după ce a procesat o parte din cuvântul de intrare, se găsește în starea q x dacă în partea din cuvântul de intrare pe care o citește, numărul de litere a întâlnit depășește numărul de litere b întâlnit de x; aici x (-2, -1, 0, 1, 2); automatul este în starea q proastă dacă la un moment dat în funcționarea automatului valoarea absolută a diferenței dintre numărul de litere procesate a și numărul de litere prelucrate b depășește 2.

Numim starea unui automat finit absorbant dacă orice literă de intrare nu scoate automatul din această stare. Să numim starea absorbantă absorbant pozitiv, dacă aparține lui F și absorbant negativ altfel. În automatele K 1 și K 4, stările q 1 și q 4 sunt absorbante pozitiv, respectiv în automatul K 5, starea q rău este absorbantă negativ.

Putem presupune că fiecare automat nu are mai mult de o stare de absorbție pozitivă și nu mai mult de o stare de absorbție negativă (dacă există mai multe stări de absorbție pozitivă sau negativă, atunci acestea pot fi ușor înlocuite cu una). De obicei, starea de absorbție negativă nu este reprezentată într-o diagramă de tranziție; dacă nu este indicată o tranziție de la o anumită stare printr-o anumită literă, atunci se presupune că aceasta duce la o stare de absorbție negativă. Mașina finită prezentată în figura 2.6 recunoaște în alfabetul A un limbaj format din cuvinte în care litera c apare exact o dată. Acest automat are 3 stări, starea de absorbție negativă q este proastă (automatul intră în ea din starea q 1 conform litera c) nu este indicată în diagramă.

q0 q1

Să introducem alfabetul B =(0, 1, 2, …, 9), fiecare cuvânt din acest alfabet este tratat ca un întreg nenegativ. Fie L (p) să desemneze mulțimea de cuvinte - înregistrările în sistemul numeric zecimal a tuturor numerelor întregi nenegative care sunt multipli ai constantei naturale p; vom presupune că limbajul L (p)

în plus, mai aparține și cuvântul gol λ. Să arătăm că L (p) este un limbaj obișnuit. Un automat finit K(p) care recunoaște L(p) poate fi construit după cum urmează. Considerăm că stările automatului sunt q 0, q 1, q 2, q p –1; dintr-o stare arbitrară q i prin cifra x, x (0, 1, 2, ... ,9), mașina merge la

Z A 79 Teorie mitraliere: îndrumări de pregătire practică pentru specialitatea 230101 / T.Z. Aralbaev,<...>Orientările abordează următoarele aspecte: metode de prezentare logic funcții ( LF); transformare algebrică LF; metode de minimizare Quineși McClassky, folosind hărți Carnot; forme sarcinile final mitraliere; sinteză combinațională scheme in baza " ȘI-NU” (“SAU-NU"") activat logic elemente seriile K155 și K561.<...>Instrucțiunile metodice sunt destinate organizării orelor practice la curs „ Teorie mitraliere” pentru studenții din anul II la specialitatea 230101 „Calculatoare, complexe, sisteme și rețele.”<...>Minimizarea funcțiilor logice pe hărți Carnot ……………………….. <...>41 3 Introducere Aceste ghiduri conțin materiale pentru desfășurarea orelor practice într-una dintre secțiunile principale ale disciplinei „Teorie” mitraliere” – „Fundamentele logice digital mitraliere”. <...>1.1 Forma tabelară a reprezentării LF Funcția logică este cel mai clar reprezentată de mesele adevăr(TI) și carduri Carnot. <...> Masă adevăr- Asta masă, în care fiecare set binar de valori de argument xi (i = 1, n) este asociat cu valoarea funcției Y = f (x1, x2,..., xi,..., xn) pe acest set. <...>O hartă Carnaugh este un tabel dreptunghiular care conține n 2 celule, fiecare celulă fiind situată la intersecția rândului i și coloanei j, ai și aj sunt elementele constitutive binar recrutare n – LF local.<...>1) orice pereche de celule care sunt adiacente vertical sau orizontal, precum și orice pereche de celule situate simetric pe hartă vertical sau orizontal, corespund binar seturi, care diferă în valoarea unei singure variabile (adică diferă într-o cifră);<...>2) în celule carduri Carnot indică valorile funcției pe setul corespunzător;<...>3) seturi binare de argumente care marchează rânduri, precum și seturi binare de argumente care marchează coloanele<...>

Theory_automata.pdf

UDC 004.3(076.5) BBK 32.97ya73 A 79 Revizor: doctor în științe tehnice, profesor A.M. Pishukhin Aralbaev, T.Z A 79 Teoria automatelor: linii directoare pentru pregătirea practică pentru specialitatea 230101 / T.Z. Aralbaev, I.V. Jukalina. - Orenburg: Instituția de Învățământ de Stat OSU, 2009. – 41 p. Orientările abordează următoarele aspecte: metode de reprezentare a funcțiilor logice (LF); transformarea algebrică a LF; Metode de minimizare Quine și McClassky folosind hărți Karnaugh; formulare pentru specificarea mașinilor cu stări finite; sinteza de circuite combinaționale bazate pe „ȘI-NU” („SAU-NU”) pe elemente logice din seriile K155 și K561. Orientările sunt destinate organizării orelor practice la cursul „Teoria automatelor” pentru studenții din anul II la specialitatea 230101 „Calculatoare, complexe, sisteme și rețele”. BBK 32,97ya73 © Aralbaev T.Z., 2009 © Zhukalina I.V., 2009 © Instituția de Învățământ de Stat OSU, 2009 2

Pagina 2

Cuprins Introducere.............................................................. ................................................... ......... ...................4 1 Lecția practică nr. 1. Metode de prezentare a funcțiilor logice……………………………….… 5 1.1 Forma tabelară de prezentare a LF………………………………….5 1.2 Forma analitică de prezentare a LF ……… …………………………….8 2 Lecția practică nr. 2. Transformarea algebrică a formulelor funcțiilor logice………….…..12 2.1 Legile algebrei booleene……………………………………………………12 2.2 Axiome și teoreme ale algebrei booleene ………… ……………………………..12 3 Lecția practică nr. 3. Metoda de minimizare Quine și McClassky………….……………………….15 3.1 Găsirea tuturor implicanților primi…………………………………..15 3.2 Construcția tabelului de acoperire Quine matrici………………………………16 3.3 Găsirea acoperirii minime a unei funcții……………………………………………….16 3.4 Obținerea formei minime a LF……… …… …………16 4 Lecția practică nr. 4. Minimizarea funcțiilor logice folosind hărți Karnaugh……………..20 4.1 Construcția de DNF-uri minime…………………………………...21 4.2 Construirea de CNF-uri minime… …………………………………………...22 4.3 Minimizarea LF-urilor incomplet definite……………………..23 5 Lecția practică nr. 5 Forme de specificare a finitului mașini de stare……… …………………………….……..25 6 Lecția practică nr. 6 Sinteza circuitelor combinaționale bazate pe „ȘI-NU” (“SAU-NU”)………. ………30 7 Lecția practică nr. 7. Sinteza circuitelor combinaționale bazate pe elemente logice din seriile K155 și K561………………………………………………………………………………………………………. …35 Lista surselor utilizate.... ................................................ ................................40 Anexă…………………………………………………… ……………………………………...41 3

Pagina 3

Introducere Aceste ghiduri conțin material pentru desfășurarea orelor practice într-una dintre secțiunile principale ale disciplinei „Teoria automatelor” - „Fundamentele logice ale automatelor digitale”. Scopul orelor este de a consolida practic cunoștințele despre formele de reprezentare și metodele de conversie a funcțiilor logice, precum și metodologia de sinteză a circuitelor combinaționale. Fiecare lecție practică include o declarație a scopului lecției, un scurt material teoretic pe această temă, exemple tipice, întrebări de testare și exerciții pentru muncă independentă. Înainte de a conduce o lecție, elevul trebuie să înțeleagă scopul acesteia și să răspundă la întrebările de control. Pentru pregătirea independentă pentru cursuri, studenților li se recomandă să citească literatura prezentată în lista surselor utilizate. În timpul lecției, sunt analizate exemple și sunt efectuate exerciții pe baza opțiunilor. Controlul cunoștințelor se realizează pe baza rezultatelor răspunsului la întrebările de testare și a realizării exercițiilor. 4

Pagina 4

1 Lecția practică nr. 1. Forme de reprezentare a funcţiilor logice Există mai multe forme de reprezentare a funcţiilor logice (LF) utilizate în diferite etape de proiectare a circuitelor combinaţionale, în special: verbale, tabulare, analitice, geometrice, cubice. Scopul lecției practice este de a studia formele tabelare și analitice ale reprezentării LF și algoritmii pentru trecerea de la o descriere tabelară a LF la o descriere analitică. 1.1 Forma tabelară a reprezentării LF Funcția logică este cel mai clar reprezentată prin intermediul unui tabel de adevăr (TI) și a unei hărți Karnaugh. Un tabel de adevăr este un tabel în care fiecare set binar de valori de argument xi (i = 1, n) este asociat cu valoarea funcției Y = f (x1, x2,..., xi,..., xn) pe acest set. Tabelul 1.1 prezintă funcția TI pentru trei argumente ca exemplu. Funcția Y ia valoarea 1 sau 0 pe fiecare set. Dacă valoarea funcției nu este definită, atunci o liniuță este plasată în poziția corespunzătoare a TI. Tabelul 1.1 – Tabelul de adevăr al funcției logice N Х1 Х2 Х3 Y 0 0 0 0 1 1 0 0 1 1 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 0 6 1 1 0 1 1 1 1 1 Uneori este folosită o formă de listă de reprezentare a TI, care oferă o listă de seturi de unu și zero. Astfel, funcția considerată în exemplu sub formă de listă poate fi reprezentată ca: Y = F Х Х Х) = ∨ (0, 1, 3, 6, 7) Y = ∧ (2, 4, 5) (0 1, 2, 3 1 5

Note excelente de curs scurte pe tema „teoria automatelor” în fișier Pdf.

Sinteza automatelor digitale pentru implementarea algoritmilor aritmetici binari

• Informații generale despre mașinile digitale. modelul lui Glushkov. Sinteza mașinilor de operare
• Un exemplu de sintetizare a unui automat operațional pentru a efectua multiplicarea indirectă a numerelor fără semn
• Tipuri de mașini de control. Structuri ale automatelor Mealy și Moore.
• Un exemplu de sinteză a unui automat de control cu ​​logică dură (UAL) pentru un algoritm de înmulțire a numerelor fără semn în cod direct

• Descrieți modelul unui convertor discret Glushkov.
• Care este scopul unui automat operațional (OA)?
• Enumerați etapele sintezei unui OA de tip procedural de structură canonică.
• Efectuați sinteza OA pentru a efectua înmulțirea (utilizați simplificat
• algoritm pentru înmulțirea indirectă a numerelor fără semn).
• Dați un exemplu de înmulțire a numerelor folosind algoritmul de înmulțire indirectă.
• Descrieți principalele opțiuni (scheme) pentru înmulțirea indirectă.
• Construiți diagrama de timp a OA pentru înmulțire. Explică-l.
• Sintetizați un algoritm pentru efectuarea unei operații aritmetice pe variante.
• Sintetizați circuitul OA conform algoritmului dvs.
• Care este scopul controlului automat (CA)?
• Rolul semnalelor de informare și de control.
• Tipuri de UA.
• Enumerați etapele sintezei UA cu o logică rigidă.
• Descrieți flip-flops de bază ca mașini de stare elementare.
• Care sunt caracteristicile sintezei UAZL pe diferite tipuri declanșatoare?
• Dați diagrame structurale ale automatelor Mealy și Moore. Care sunt diferențele lor?
• Descrieți modelele automatelor abstracte Mealy și Moore.
• Ce forme de descriere a mașinilor abstracte cu stări finite cunoașteți?
• Construiți tabele de tranziție/ieșire și grafice automate conform schemei
• algoritm.
• Sintetizați UA pentru a implementa algoritmul de multiplicare (utilizați
• algoritm simplificat pentru înmulțirea indirectă a numerelor fără semn) ca
• Mili/Moore automat.
• Construiți o diagramă de timp a OA pentru înmulțire. Explică-l.
• Sintetizați schema UASL pentru algoritmul dvs. în funcție de opțiuni.

Folosind expresii regulate (RE). Implementarea software a automatelor

• Conceptul de expresii regulate și de recunoaștere a automatelor
• O introducere rapidă în expresiile regulate (RE). Dialectele RV.
• Aplicarea RT în programare
• Un exemplu de formare a unei expresii regulate
• Exemplu de lucru cu expresie regulată pentru a controla adresele IP introduse de utilizator.
• Sinteza unui automat determinist pentru recunoașterea limbajului specificat de o expresie regulată și implementarea sa software.
• Conversia RF în NKA cu ε – ​​tranziții
• Conversia NKA cu ε-tranziții în NKA fără ε-tranziții
• Obținerea DKA de la NKA fără tranziții ε
• Minimizarea DFA
• Primirea RF de la navă spațială
• Implementarea software a instrumentului de recunoaștere DFA

• Ce este o expresie regulată?
• Unde se folosesc RV-urile?
• Ce metode cunoașteți pentru alocarea RV?
• Ce automate sunt folosite pentru a recunoaște limbile specificate de RT?
• Ce este NKA? DKA?
• Cum se construiește un detector de navă spațială folosind RV?
• Cum se construiește un detector DKA folosind RV?
• Cum se elimină e-tranzițiile în nave spațiale?
• Cum se reduce la minimum CA - recunoaștere?
• Cum sunt utilizate RT-urile în mediul VS?
• Cum sunt acceptate RT-urile în .NET Framework?
• Descrieți lanțurile date folosind RT.
• Ce lanțuri definește acest RF (exemple, caracteristici).
• Strategii pentru implementarea suportului RT în sistemele software.
• Modalități de utilizare a suportului RT atunci când scrieți programe de procesare a textului.
• Ce probleme de procesare a textului pot fi rezolvate folosind RT?
• Enumeră-i pe cei pe care îi cunoști sisteme software, susținând RV.

Sunt date informații inițiale despre automatele abstracte ale lui Mealy și Moore. Sunt date moduri posibile reprezentări ale automatelor: teoretică multime, grafică, tabelară și matriceală, concepte de răspuns ale unui automat și automate echivalente. Sunt date metode pentru transformarea echivalentă reciprocă a automatelor. Sunt date Informații generale despre controlul microprogramelor, conceptele de microinstrucțiuni, microoperații, microprograme, metode de reprezentare a microprogramelor sub formă de diagrame grafice ale algoritmilor (GDA), formule de translație, diagrame matrice și logice ale algoritmilor. Sunt date metode de marcare a GSA și reguli pentru construirea automatelor Mealy și Moore folosindu-le. Sunt prezentate conceptul de automat combinat și modalitățile de reprezentare a acestuia. Sunt luate în considerare metode pentru sinteza canonică a automatelor structurale. Sunt oferite exemple de sinteză de memorie a unui automat structural bazat pe flip-flops RS-, T- și D.

Concepte de bază și definiții.
Cel mai simplu convertor de informații (Fig. 1.1, a) afișează un anumit set de elemente de informații X care ajung la intrare într-o anumită mulțime la ieșirea Y. Dacă mulțimile X și Y sunt finite și discrete, adică transformarea este efectuată la momente discrete în timp, atunci astfel de informații despre convertoare se numesc transformatoare finale. În acest caz, elementele mulțimilor X și Y sunt pre-codificate cu coduri binare și se construiește o transformare a unei mulțimi în alta.

Rezultatul transformării F: X → Y depinde adesea nu numai de ce informații se află în acest moment apărute la intrare, dar și din cele întâmplate înainte, adică din preistoria transformării. De exemplu, aceeași intrare - scuzele unui vecin după ce te-a călcat pe picior într-un autobuz aglomerat - te va face să ai o reacție prima dată și una complet diferită a cincea oară.

Conţinut
Copertă Amprentă
Curs 1. Concepte de bază ale teoriei automatelor abstracte
Curs 2. Automate echivalente
Curs 3. Metode de descriere a funcționării dispozitivelor discrete
Curs 4. Construirea automatelor abstracte folosind o diagramă grafică de microprogram
Curs 5. Sinteza unui automat structural
Curs 6. Memoria unui automat structural
Curs 7. Un exemplu de sinteză a unui automat structural folosind flip-flops
Cursul 8. Metoda grafica sinteza unui automat structural pe declanșatori.

Descărcare gratuită e-carteîntr-un format convenabil, urmăriți și citiți:
Descarcă cartea Introducere în teoria automatelor, Knyazkov V.S., Volchenskaya T.V., 2016 - fileskachat.com, descărcare rapidă și gratuită.

Descărcați pdf
Puteți cumpăra această carte mai jos cel mai bun pret la reducere cu livrare în toată Rusia.