Përkufizimi dhe metodat e specifikimit të automatave të fundme. Përkufizimi i Makinave Shtetërore

Është e qartë se k,r,s përkatësisht e barabartë me numrin e shifrave në paraqitjen binare të numrave t, p, r. Për shembull, nëse t - 5, P= 17, p = 3, pastaj k= 3, r= 5, s = 2.

2. Kodimi i gjendjeve të simboleve hyrëse dhe dalëse të burimit
makinë.

Për çdo q j Q një-për-një shoqërojnë një sekuencë binare gjatësie r- kodi binar = z 1 z 2 z r . Ngjashëm me secilin a i X dhe b k Y caktojmë sekuenca binare një-për-një =x 1 x 2 x k ; =y 1 y 2 y s .

Vini re se kodimi i gjendjeve, simboleve hyrëse dhe dalëse mund të bëhet në shumë mënyra. Megjithatë, disa sekuenca (kode) mund të mos përdoren.

3. Bëjmë tabelën e mëposhtme:

Kjo tabelë përmban k+r+r+s kolonat dhe 2 k + r linjat. Së pari k+r kolonat shkruhen nga të gjitha grupet e gjatësisë k+r.Çdo grup i tillë korrespondon me një çift (), ku është një kod i mundshëm i një shteti, kodi i simbolit të hyrjes.

4. Plotësimi i kolonave të fundit në tabelë (hapi i mëparshëm).

Për çdo çift (a i ,q j), ku a i X; q j Q , gjeni kodin dhe . Nga tabela e automateve (ose diagrami Moore) përcaktojmë dhe \|/(a; q) = Y. Pastaj gjejmë kodin = " 1 " 2 ... ", dhe kodin .

Në rreshtin e tabelës që korrespondon me grupin

shtoni grupin

5. Përkufizimi i një sistemi funksionesh Boolean.

Pas përfundimit të hapit të mëparshëm, mund të rezultojë se të gjitha rreshtat në tabelë janë mbushur. Kjo do të ndodhë nëse të paktën një nga numrat m, n nuk është një fuqi prej 2. Kështu, funksionet nuk do të përcaktohen plotësisht - në disa grupe vlerat e tyre nuk janë të përcaktuara. Pastaj ne i ripërcaktojmë ato në mënyrë arbitrare. Si rregull, shtrirja e funksioneve kryhet në atë mënyrë që funksionet e përcaktuara plotësisht që rezultojnë të plotësojnë disa kushte optimale, për shembull, ato mund të përfaqësohen nga DNF minimale.

Pas përfundimit të këtij hapi, automati origjinal do të përcaktojë sistemin e funksioneve Boolean plotësisht të përcaktuara

3.2 Gjuhët fillestare.

Ata përshkruajnë automatikun në nivelin e sjelljes. Gjuhët kryesore përfshijnë:

1) gjuhët e qarqeve logjike dhe grafiku i diagrameve të algoritmeve;

2) gjuha e shprehjeve të rregullta të algjebrës së ngjarjeve;

3) gramatikat formale dhe automatike.

Nëse jepet përshkrimi (4) i një automati plotësisht të përcaktuar në formë standarde, atëherë për çdo gjendje fillestare të automatit s(0) dhe sekuencat e simboleve hyrëse v(0)v(1)v(2)…v(t) është e mundur të llogaritet përgjigja e automatit në formën e një sekuence simbolesh dalëse w(0)w(1)…w(t).

Shembuj.

Shembulli 1. Makina e gazetave SELLER merr monedha në prerje prej 1 rubla dhe 2 rubla. Nëse shuma e monedhave është e barabartë me 3 rubla, atëherë makina jep një gazetë. Nëse shuma është më shumë se 3 rubla, atëherë makina i kthen të gjitha paratë. Le të prezantojmë shënimin për simbolet hyrëse dhe dalëse dhe gjendjet e automatit.

Karakteret hyrëse:

v 1 - ulet një monedhë me vlerë 1 rubla;

v 2 - një monedhë me vlerë 2 rubla është hequr.

Karakteret e daljes:

w 1 - mesazhi "Shuma prej 1 rubla u pranua.";

w 2 - mesazhi "Shuma prej 2 rubla u pranua.";

w 3 - nxjerrja e gazetës;

w 4 - kthimi i parave.

Makina thotë:

s 0 - pranohet shuma prej 0 rubla. (gjendja fillestare);

s 1 - shuma prej 1 rubla pranohet;

s 2 - shuma prej 2 rubla pranohet.

Ne përfaqësojmë funksionin e tranzicionit në tabelën 2 dhe funksionin e daljes në tabelën 3.

I njëjti automat mund të specifikohet në formën e një digrafi të shënuar, kulmet e të cilit korrespondojnë me gjendjet e automatit, dhe harqet korrespondojnë me tranzicionet (Fig. 3).

Më poshtë është një shembull i reagimit të automatit SELLER ndaj sekuencës hyrëse v 1 v 1 v 2 v 2 v 1 v 2 v 2 v 1 v 1 v 1 …:

Shembulli 2 Për shitësin e automatit të konsideruar më sipër, është e mundur të ndërtohet një automat Moore ekuivalent, i karakterizuar nga një tabelë e tranzicioneve/daljeve (Tabela 4).

Tabela 4

Figura 4 tregon grafikun e tranzicioneve/daljeve të automatit SELLER që korrespondon me Tabelën 4. Gjendja fillestare e makinës ekuivalente Moore përfshin simbolin e hyrjes v(0). Prandaj, është e nevojshme të zhvendoset rryma e karaktereve hyrëse: .

Le të përshkruajmë sjelljen e një prindi që dërgoi djalin e tij në shkollë. Djali sjell deka dhe pesëshe. Babai nuk dëshiron të rrëmbejë rripin çdo herë, sapo djali të marrë një tjetër deuç, dhe zgjedh një taktikë më delikate edukimi. Është i përshtatshëm për të përcaktuar një automat me një grafik në të cilin kulmet korrespondojnë me gjendjet, dhe skaji nga gjendja s në gjendjen q, etiketuar x/y, vizatohet kur automati nga gjendja s nën ndikimin e një sinjali hyrës x kalon. për të deklaruar q me një reaksion dalës y. Grafiku i automatit që simulon sjelljen inteligjente të prindit është paraqitur në Fig. 5.

Oriz. 5. Automati që përshkruan sjelljen e një babai "të zgjuar".

Ky automat ka katër gjendje (s0, s1, s2, s3) dhe dy sinjale hyrëse - notat e marra nga djali në shkollë: (2,5). Duke u nisur nga gjendja fillestare s0 (shënohet me një shigjetë hyrëse), automati, nën ndikimin e sinjaleve hyrëse, kalon nga një gjendje në tjetrën dhe lëshon sinjale dalëse - reagime në hyrje. Rezultatet e automatit (y0,...,y5) do të interpretohen si veprime të prindit si më poshtë:

y0: - merr një rrip;

yl: - të qortojë djalin;

y2: - për të qetësuar djalin;

uZ: - shpresoj;.

y4: - gëzohu;

y5: - gëzohu.

Një djalë që mori të njëjtën notë - një deuce, pret një reagim krejtësisht të ndryshëm nga babai i tij në shtëpi, në varësi të sfondit të studimeve të tij. Babai kujton se si djali i tij ka studiuar më parë dhe e ndërton edukimin e tij duke marrë parasysh sukseset dhe dështimet e tij të mëparshme. Për shembull, pas ndeshjes së tretë në histori 2,2, 2 djemtë do të takohen me një rrip dhe në historinë 2, 2, 5, 2 ata do të qetësohen. Çdo histori përcakton gjendjen aktuale të automatit dhe disa histori hyrëse janë ekuivalente (domethënë ato që e sjellin automatikun në të njëjtën gjendje): historia 2, 2, 5 është ekuivalente me historinë boshe që korrespondon me gjendjen fillestare.

Gjendja aktuale e automatit përfaqëson gjithçka që automati di për të kaluarën për sa i përket sjelljes së tij në të ardhmen - reagimet ndaj hyrjeve të mëvonshme. Kjo histori në një formë të përqendruar përcaktohet nga gjendja aktuale dhe përcaktohet e gjithë sjellja e ardhshme e automatit, si reagimi i tij ndaj sinjaleve të mëvonshme hyrëse. gjegjësisht gjendjen aktuale, por jo mënyrën se si ka ardhur automatiku.

Pra, një makinë gjendje është një pajisje që funksionon në kohë (cikle) diskrete. Në hyrjen e automatit të fundëm në çdo cikël, merret një nga sinjalet hyrëse të mundshme dhe në daljen e tij shfaqet një sinjal dalës, i cili është një funksion i gjendjes së tij aktuale dhe sinjalit hyrës të marrë. Gjendja e brendshme e automatit gjithashtu ndryshon. Pikat e ndezjes (ciklet) përcaktohen ose nga sinjalet e orës së detyruar, ose në mënyrë asinkrone, nga fillimi i një ngjarjeje të jashtme - ardhja e një sinjali.

Le të përcaktojmë zyrtarisht automatikun e fundëm.

Përveç paraqitjes grafike për automatin, mund të përdorni edhe një tabelare, duke vendosur funksionet e tranzicioneve dhe daljeve në formën e tabelave. Shembulli i automatit do të përfaqësohet nga tabelat e mëposhtme.

tabela 5, a përcakton një funksion tranzicioni si ky:

dhe skedën. 5b përcakton funksionin e daljeve : .(s0, 2) = y2; (s2, 5) = y3; ....

Paraqitja e një automati të fundëm reduktohet në të vërtetë në një përshkrim të funksioneve të automatit që e përcaktojnë atë.

Ekzistojnë tre mënyra për të përcaktuar automatet e fundme:

· Tabela (matricat e kalimeve dhe daljeve);

Grafike (duke përdorur grafikët);

· Analitike (duke përdorur formula).

Metoda analitike– automati jepet nga një sistem ekuacionesh. Nga një sistem i tillë rrjedh se për një numër të kufizuar të gjendjeve të brendshme të mundshme, numri i vlerave të mundshme të funksioneve të automatit gjithashtu rezulton të jetë i kufizuar. Një shembull i një detyre të tillë është sistemi i ekuacioneve që përcaktojnë automatet Mealy dhe automatat Moore

mënyrë tabelare. Një tabelë e gjendjes së automatit është përpiluar për funksionin e tranzicionit - δ dhe funksionin e daljes. ku:

kolonat e tabelës korrespondojnë me elementet e alfabetit të hyrjes x,

Rreshtat e tabelës korrespondojnë me gjendjet (elemente të një grupi të fundëm Q).

Kryqëzimi i rreshtit të i-të dhe kolonës j-të i përgjigjet qelizës (i, j), e cila është argumenti i funksioneve 8 dhe λ të automatit në momentin kur ai është në gjendje qi në hyrje të saj - fjala x j, dhe në qelizën përkatëse shkruajmë vlerat e funksioneve 8 dhe λ. Kështu, e gjithë tabela korrespondon me grupin P X x.

Kur plotësoni tabelën e tranzicionit, çdo qelizë përcaktohet në mënyrë unike nga një palë simbolesh: simboli i gjendjes së ardhshme dhe simboli i sinjalit të daljes.

Në praktikë, funksionet e automatit jepen nga dy tabela të fundme, përkatësisht të emërtuara matrica e tranzicionit dhe matrica e përfundimit. Në këtë rast, rreshtat shënohen me shkronjat e alfabetit të hyrjes, dhe kolonat me shkronjat e alfabetit të brendshëm (simbolet që kodojnë gjendjen e brendshme të automatit).

Në matricën e tranzicionit, në kryqëzimin e rreshtit x k dhe kolonës q r, vlera e funksionit të tranzicionit δ(q i , X) dhe funksionet e konkluzionit λ(q, X). Në disa raste, të dyja tabelat kombinohen në një tabelë.

Mënyra grafike.

Një automat specifikohet duke përdorur një grafik, diagram, grafik, etj. Një detyrë që përdor një grafik të drejtuar është një formë më e përshtatshme dhe kompakte për të përshkruar një automat.

grafiku automatik përmban

· majat, që i përgjigjet shtetit qi OQ,

· harqe, kulmet lidhëse janë kalime të automatit nga një gjendje në tjetrën. Në harqe, është zakon të tregohen palë sinjale hyrëse dhe dalëse - sinjale tranzicioni.

Nëse automati kalon nga shteti q 1 në një gjendje q2 nën ndikimin e disa sinjaleve hyrëse, atëherë ky variant do të paraqitet në harkun përkatës të grafikut nëpërmjet një disjunksioni. Për të paraqitur automatikun, përdoren grafikë bipolarë me gjendje fillestare dhe përfundimtare të dallueshme.

Zhvillimi i shkallës së "instrumentit matës të kapacitetit".

Fig.2.5. Grafiku i shkallës së pajisjes për matjen e kapacitetit

konkluzioni

Meqenëse përdorimi i gjeneratorëve me qarqe lëkundëse (lloji RC) për gjenerimin e lëkundjeve me frekuencë të lartë nuk kënaq, për gjeneratorin e zhvilluar u mor një qark i tipit LC (një qark me tre pika me bashkim autotransformator u mor si qark fazash, aktivi elementi është një tranzistor).

Në pjesën teorike të kësaj pune lëndore janë marrë parasysh elementet e gjeneratorëve të tipit LC. U morën në konsideratë edhe klasifikimi i gjeneratorëve të tipit LC, qëllimi i tyre, si dhe qarqe të ndryshme gjeneratorësh. Si dhe karakteristikat teknike të elementeve të gjeneratorit.

Në pjesën praktike u shpalos tema për koduesit, dekoderat, qëllimi i tyre, si dhe u hartuan diagramet e qarkut elektrik funksional dhe elektrik të koduesve dhe dekoderëve. Tema e hartave të Karnot u zbulua. U zhvillua gjithashtu segmenti "b" i treguesit me shtatë segmente. U zhvillua një makinë shtetërore për shkallën e instrumentit për matjen e kapacitetit, si dhe një grafik për të.

Përkufizimet bazë të n Një automat i fundëm është një sistem M =(А, B, S, y) në të cilin n n n А = (а 1, . . . . , am) është një alfabet i kufizuar i hyrjes, B =(b 1, . . . ... n Nëse në automatikun M zgjidhet një gjendje, e quajtur gjendja fillestare (zakonisht do të konsiderohet se kjo është s 1), atëherë automati që rezulton quhet fillestar dhe shënohet me (M, s 1). n Ka dy mënyra për të përcaktuar një automat: Tabela automatike, diagrami i tranzicionit

Tabela automatike n 1) 2) 3) 4) Shembull: vendoseni automatikun për leximin e fjalës "001" nëse futen karakteret "0" dhe "1". Alfabeti i hyrjes A=(0, 1) Alfabeti dalës A=(Y, N) Alfabeti i gjendjes S=(s 0 "" , s 1 " 0" , s 2 " 00" s 3 "001" ) Tabela automatike në dy mënyra . 1) Rreshtat janë gjendjet e automatit. Kolonat janë simbolet hyrëse. Në kryqëzimin e rreshtave dhe kolonave, funksionet tregohen, y. 2) S, A, y jepen me kolona. Ushtrimi 25 Ndërtoni një automat për të kërkuar fjalën CAKADU 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 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 N S 1 S 2 S 3

Diagrami i tranzicionit n Një multigraf i orientuar, i quajtur diagramë tranzicioni, është një multigraf, tranzicion ose graf që korrespondon me gjendjet. Nëse (Si, aj)=Sk, y(Si, aj)=bl, atëherë nga kulmi Si në kulmin Sk ka një hark mbi të cilin shkruhet (aj, bl) n Në çdo kulm si, kushtet e saktësisë janë : 0 1 S 0 "" S 1, N S 0, N S 1 "0" n Kulmet, 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 plotësohet 1) për çdo shkronjë hyrëse aj ka një hark që del nga si, në të cilin shkruhet aj (kushti i plotësisë); 2) çdo shkronjë aj shfaqet vetëm në një skaj që del nga si (kushti i konsistencës ose determinizmit) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y) S 3

Automata dhe fjalët hyrëse n Për një automat të caktuar M, funksionet e tij janë M dhe y. M mund të përcaktohet jo vetëm në grupin A të të gjitha shkronjave hyrëse, por edhe në grupin A* të të gjitha fjalëve hyrëse. n Për çdo fjalë hyrëse = 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).

Shembull: Automata dhe fjalët hyrëse Shembull: = 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) \u003d N, y S 2, N S 3, Y S 3 "001" S 1, N S 0, N

Hartëzimi automatik n Le të rregullojmë një gjendje fillestare S 0 në M dhe për çdo fjalë hyrëse = a 1 a 2. . . ak caktojmë një fjalë në alfabetin dalës: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1. . . ak). (3 a) n Kjo korrespodencë, e cila harton fjalët hyrëse me fjalët dalëse, quhet një hartografi automatike n Nëse rezultati i aplikimit të një operatori në një fjalë është një fjalë dalëse, atëherë kjo do të shënohet përkatësisht me M() = .

Shembull: Hartë automatike Le t'i caktojmë fjalën hyrëse = 0101 fjalës në alfabetin e daljes: = 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

Vetitë automatike të shfaqjes 1) fjalët dhe = M() kanë të njëjtën gjatësi: | | = | | (vetia e ruajtjes së gjatësisë); 2) nëse = 1 2 dhe M(1 2) = 1 2, ku | 1| = | 1|, pastaj M(1) = 1; me fjalë të tjera, imazhi i një segmenti me gjatësi i është i barabartë me segmentin e figurës me të njëjtën gjatësi.

Llojet e automateve n Modeli i përgjithshëm i një automati të fundëm (S-fundit), i cili u konsiderua më herët, quhet automat Mealy. n Një automat quhet autonom nëse alfabeti i tij hyrës përbëhet nga një shkronjë: A=(a). Të gjitha fjalët hyrëse të automatit autonom kanë formën aa. . . a. n Një automat i fundëm quhet automat Moore nëse funksioni i tij i daljes varet vetëm nga gjendjet, d.m.th., për çdo s, ai, aj y(s, ai) = y(s, aj). Funksioni i daljes së automatit Moore është natyrshëm me një argument; zakonisht shënohet me shkronjë dhe quhet funksioni i shenjave. Në grafikun e automatit Moore, dalja shkruhet jo në skajet, por në krye.

Moore automata n Teorema: Për çdo automat Mealy ekziston një automat Moore ekuivalent. n Gjatë studimit të mundësive të automatave, mjafton të përdoren automata Moore. Kjo është e përshtatshme sepse automatiku Moore mund të shihet si një automat pa dalje, gjendjet e të cilit janë etiketuar në mënyra të ndryshme.

Një shembull i një automati 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 S A=(a), B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S9)

Gjendjet e padallueshme n Le të jenë M dhe T dy automata me të njëjtat alfabete hyrëse dhe dalëse. Një gjendje s e një automati M dhe një gjendje r e një automati T thuhet se janë të padallueshme nëse për ndonjë fjalë hyrëse M(s,) = T(r,). n Automatet M dhe T quhen të padallueshme nëse për çdo gjendje s të automatit M ekziston një gjendje r e automatit T që është e padallueshme prej tij dhe, anasjelltas, për çdo r nga T ekziston një gjendje e padallueshme s nga M. n Gjendjet e padallueshme quhen ekuivalente

Automati minimal n Kalimi nga një automat M në një automat M ekuivalent quhet transformim ekuivalent i një automati M. n Dikush mund të parashtrojë probleme të ndryshme për gjetjen e automateve që janë ekuivalente me një automat të caktuar dhe kanë dhënë veti. Më i studiuari ndër probleme të tilla është problemi i minimizimit të numrit të gjendjeve të një automati: midis automateve ekuivalente me M, gjeni automatikun me numrin më të vogël të gjendjeve - automatin minimal.

Aspektet e "punës" së automateve n Dy aspekte kryesore të "punës" së automateve mund të dallohen: 1) automatet njohin fjalët hyrëse, pra përgjigjen në pyetjen nëse fjala hyrëse i përket një grupi të caktuar (këto janë automata njohëse) ; 2) automatet i transformojnë fjalët hyrëse në fjalë dalëse, d.m.th., ato zbatojnë hartëzimin automatik (automatët e transformatorëve).

TA në kuadrin e metamatematikës n Tema e teorisë së algoritmeve dhe sistemeve formale në kuadrin e metamatematikës - cilat objekte dhe veprime mbi to duhet të konsiderohen të përcaktuara saktësisht, cilat veti dhe aftësi kanë kombinimet e veprimeve elementare, çfarë mund dhe nuk mund të jenë bëhet me ndihmën e tyre. n Zbatimi kryesor i teorisë së algoritmeve është vërtetimi i pamundësisë së një zgjidhjeje algoritmike (dmth. të saktë dhe të paqartë) të problemeve të caktuara matematikore.

Algoritmi n Një algoritëm është një recetë që specifikon në mënyrë unike procesin e transformimit të të dhënave fillestare në rezultatin e kërkuar n Vetë procesi i transformimit përbëhet nga hapa elementare diskrete, aplikimi i të cilave një numër i kufizuar herë çon në rezultat.

Llojet bazë të algoritmeve n Teoria e algoritmeve është një metateori që studion vetitë e ndryshme (cilësore dhe sasiore) të algoritmeve. n Për studimin e vetive cilësore përcaktohen 3 lloje kryesore algoritmesh: 1) Funksionet rekursive 2) Makina Turing 3) Sistemet postare kanonike dhe algoritmet normale Markov.

Funksionet më të thjeshta rekursive n S 1(x) = x+1 - funksioni varet nga një ndryshore x dhe është i barabartë me x+1. n On(x 1…xn) =0 - funksion në varësi të n variablave dhe gjithmonë i barabartë me 0. n Imn(x 1…xn) = xm - funksion në varësi të n variablave dhe gjithmonë i barabartë me vlerën e ndryshores xm

Rekursioni primitiv n Funksioni f(x 1...xn+1) merret nga algoritmi primitiv i rekursionit nga funksionet g(x 1...xn) dhe h(x 1...xn+2) nëse f(x 1, …xn, 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), ku z=f(x 1, …xn, y) (2) Funksioni f quhet rekursiv primitiv, nëse mund të merret nga funksionet më të thjeshta S 1, On, Imn nga një numër i fundëm superpozicioni dhe operacionesh rekursioni primitiv.

Shembull n Për të vërtetuar se një funksion është rekurziv primitiv: 1) Sipas ekuacioneve (1) dhe (2), përcaktoni në mënyrë eksplicite funksionet g() dhe h(). 2) Tregoni se g() dhe h() janë funksionet më të thjeshta S 1, On, Imn ose funksionet rekursive primitive të provuara më parë. Ushtrimi 26: Vërtetoni se funksioni f(x, y) = x+y është rekurziv primitiv Teza e Kishës: Klasa e funksioneve numerike të llogaritshme algoritmikisht përkon me klasën e të gjithë funksioneve rekurzive.

Makina Turing n Makina Turing përmban: n 1) Memorie e jashtme - një shirit prej n qelizave. Çdo qelizë i-të është në gjendjen ai. Është vendosur alfabeti i shteteve. Shiriti mund të jetë i pafund në të dy drejtimet. Gjendjet boshe janë hequr. n 2) Kujtesa e brendshme e makinës - pajisja aktualisht është në gjendjen qi. Jepet alfabeti i gjendjes së brendshme. Gjendja fillestare q 1, q përfundimtare 0 ose qz. n 3) Treguesi - tregon në qelizën aktuale dhe lëviz përgjatë shiritit. n 4) Pajisja e kontrollit - lexon karakterin e qelizës së drejtuar nga treguesi. Në përputhje me programin, ndryshon gjendjen e qelizës dhe lëviz treguesin.

Gjendja dhe programi MT n Gjendja e makinës Turing quhet fjala n n n n a 1…ak-1 qi ak…ar, e formuar duke futur simbolin e gjendjes së brendshme përpara qelizës së monitoruar. Programi i makinës Turing është një grup komandash që mund të ekzekutohen nga makina qi aj qi' aj' D, ku qi është gjendja e brendshme e makinës aj është gjendja e qelizës së monitoruar qi' është gjendja e re e makinës aj' është një karakter i ri i shkruar në qelizën e monitoruar D = ( L, R, E) - karaktere që simbolizojnë zhvendosjen e treguesit me një qelizë majtas, djathtas dhe mungesën e një zhvendosjeje, përkatësisht.

Shembull MT Ushtrimi 27: Gjeni gjendjen përfundimtare të makinës Turing Alfabeti fillestar: A = (0, 1) Alfabeti i gjendjes së brendshme: Q = (q 0, q 1, q 2) Programi: ( 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Fjala fillestare: q 111

Shembull MT Control 28 Gjeni gjendjen përfundimtare të makinës Turing Alfabeti fillestar: A \u003d (0, 1, ) Alfabeti i gjendjes së brendshme: Q \u003d (q 0, q 1, q 2, q 3) Programi: ( 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) Fjala fillestare: q 111 1 B) Fjala fillestare: q 11 111

Teza e Turingut Teza e Turingut: për çdo algoritëm A, mund të ndërtohet një makinë Turing, e cila, duke pasur të njëjtat të dhëna fillestare, jep të njëjtat rezultate si algoritmi A. n Nëse 1 q 1 2 1 qz 2, atëherë do të themi se makina T përpunon fjalën 1 2 në fjalën 1 2, dhe e shënojmë T(1 2) = 1 2. n Shënimi T() është përcaktimi i makinës T me vlera fillestare.

Algoritmet Normale të Markovit n Algoritmet Normale të Markovit (NAM) transformojnë fjalët me gjatësi të kufizuar në njëra-tjetrën duke përdorur zëvendësimin. n Detyra NAM Zëvendësimi Alfabeti u v Zëvendësimi përfundimtar u v n Kontrolli 29 Një algoritëm normal Markov është specifikuar: Alfabeti është alfabeti i gjuhës ruse. Skema e zëvendësimit (I U, L U, S M, V B, R T, T R, O X, N A) n Fjala fillestare SLON. n Gjeni fjalën fundore.

Vlerësimi i kompleksitetit të algoritmeve n Supozojmë se funksionet f(n) dhe g(n) matin performancën e dy algoritmeve, zakonisht quhen funksione të kompleksitetit kohor. Do të themi se rendi i rritjes së funksionit f(n) nuk është më i madh se ai i g(n) nëse ekziston një konstante pozitive C e tillë që | f(n) |

Efikasiteti i algoritmeve 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 1024 s 1024 s 100 ms 0.201 s . ditë 10176 shekuj 1000 ms 0,83 orë 1 ms

Teoria e Algoritmeve n Teoria e Algoritmeve - klasifikon problemet sipas kompleksitetit. Në këtë rast, klasifikohen vetëm detyrat e njohjes. n Një detyrë njohjeje është një detyrë që i përgjigjet pyetjes: a kanë të dhënat hyrëse disa veti. Në rastin tonë: të dhënat hyrëse janë një grafik, një veti - a është grafiku Hamiltonian?

Klasat P dhe NP n Klasa e kompleksitetit P: ekziston një algoritëm A që zgjidh problemin në kohë polinomiale. n Klasa e kompleksitetit NP - ekziston një algoritëm A që kontrollon zgjidhjen e propozuar në kohë polinomiale. n Problemi i ciklit Hamiltonian është për të gjetur nëse një graf i dhënë G ka një cikël Hamiltonian që i përket klasës NP.

Shembuj të problemeve NP n Problemi i kënaqshmërisë Boolean: për të gjetur nga një formulë e dhënë Boolean nëse ka një grup variablash të përfshirë në të që e kthejnë atë në 1. n Problema e klikës: për të gjetur nga një grafik i dhënë nëse ka klik (i plotësuar nëngrafët) të një madhësie të caktuar në të. n Problemi i ekzistencës së një cikli Hamiltonian në një grafik. n Ekzistenca e një zgjidhjeje të plotë për një sistem pabarazish lineare.

Mundësia e zgjidhjes së problemeve NP me numërimin e n Fillimisht nuk dihet zgjidhja. Prandaj, është e rëndësishme që çdo problem që lidhet me klasën NP mund të zgjidhet në kohë eksponenciale duke numëruar të gjitha kombinimet e mundshme të n, gjë që ndodh në algoritmin për gjetjen e ciklit Hamilton.

Marrëdhënia ndërmjet Р dhe NP n Çdo detyrë nga P i përket NP. n Kështu, klasa NP përfshin klasën P. Për momentin, nuk dihet nëse klasat P dhe NP janë të njëjta, por shumica e ekspertëve besojnë se nuk janë të njëjta.

Raporti i P dhe NP n Nëse rezulton se P = NP 1) detyrat NP do të zgjidhen në një kohë të arsyeshme. 2) Ka një sërë problemesh që përdorin qëllimisht probleme me kompleksitet eksponencial (d.m.th., duke supozuar se problemi nuk mund të zgjidhet). Për shembull, në kriptografi, ekziston një seksion mbi enkriptimin e çelësit publik, i cili është pothuajse i pamundur të deshifrohet. Nëse papritmas P = NP, atëherë shumë sekrete do të pushojnë së qeni të tilla.

Problemet NP-komplete n Arsyeja më bindëse për të besuar se P ≠ NP është ekzistenca e problemeve NP-komplete. n Joformalisht!!!, problema Q reduktohet në problem Q′ nëse problemi Q mund të zgjidhet në kohë polinomiale për çdo hyrje, duke supozuar se zgjidhja e problemit Q′ për ndonjë hyrje tjetër është e njohur. Për shembull, problemi i zgjidhjes së një ekuacioni linear reduktohet në problemin e zgjidhjes së një ekuacioni kuadratik.

Probleme NP-komplete n Një problem NP-komplet është një problem nga klasa NP tek e cila mund të reduktohet çdo problem tjetër nga klasa NP. n Problemet e plota NP formojnë një nëngrup të problemeve "më të vështira" në klasën NP. Nëse për ndonjë problem NP-të plotë gjendet një algoritëm zgjidhjeje polinomiale, atëherë çdo problem tjetër nga klasa NP mund të zgjidhet në kohë polinomiale. n Të gjitha problemet NP të listuara janë NP-të plota. Përfshirë problemin e ciklit Hamilton.

Baranov Viktor Pavlovich Matematikë diskrete. Seksioni 6. Automat e fundme dhe gjuhët formale.

Leksioni 31 Detyrë sinteze. Automata elementare

Leksioni 30

PROBLEMI I SINTEZËS. AUTOMATË KRYESORE

Plani i leksionit:

1. Përkufizimi i një automati të fundëm.

2. Metodat për përcaktimin e një automati të fundëm.

1. Problemi i sintezës së automatave.
2. Makinat elementare.
3. Problemi i plotësisë së një baze automatike.
4. Metoda kanonike për sintezën e automateve.

1. Përkufizimi i makinës së gjendjes

SFE nuk e merr parasysh faktin që pajisjet reale funksionojnë në kohë. Krahasuar me SFE, automati i fundëm është një model më i saktë i një konverteri informacioni diskret. Në të njëjtën kohë, koncepti i një automati të fundëm, si çdo model, shoqërohet me një numër supozimesh thjeshtuese.

Së pari, supozohet se hyrja dhe dalja e automatit mund të jenë vetëm në një nga një numër i kufizuar gjendjesh të ndryshme në çdo kohë. Nëse një transduktor i vërtetë ka një sinjal hyrës të vazhdueshëm, atëherë për ta përshkruar atë duke përdorur një automat të fundëm, është e nevojshme të kuantizohet ky sinjal. Në përkufizimin formal të automatit, grupi i fundëm i gjendjeve hyrëse dhe dalëse të automatit quhet përkatësisht alfabeti i hyrjes dhe i daljes, dhe gjendjet individuale quhen shkronjat e këtyre alfabeteve.

Së dyti, supozohet se koha ndryshon në mënyrë diskrete. Gjendjet e hyrjes dhe daljes korrespondojnë me një sekuencë kohore diskrete Meqenëse momenti i kohës përcaktohet në mënyrë unike nga indeksi i tij, për hir të thjeshtësisë do të supozojmë se koha merr vlerat 1, 2, ..., ... Intervali kohor quhet takt.

Funksionimi i makinës paraqitet si më poshtë.

Hyrja e automatit merr sinjale nga alfabeti i hyrjes, gjë që çon në shfaqjen e sinjaleve në dalje nga alfabeti i hyrjes. Varësia e sekuencës së daljes nga sekuenca hyrëse varet nga struktura e brendshme e automatit. Vini re se, ndryshe nga SFE, të cilat nuk kanë memorie, automati është një pajisje me memorie, d.m.th., dalja e automatit përcaktohet jo vetëm nga hyrja, por edhe nga parahistoria. Parahistoria merret parasysh nga varësia e sinjalit të daljes jo vetëm nga hyrja, por edhe nga gjendja aktuale, të cilën ne e shënojmë.

Le të japim një përkufizim zyrtar të një automati.

Një makinë shtetërore është një grup prej pesë objektesh

një grup i kufizuar i quajtur alfabeti hyrës; një nga gjendjet e mundshme të hyrjes;

një grup i kufizuar i quajtur alfabeti i daljes; elementet e këtij grupi përcaktojnë gjendjet e mundshme të daljes;

një grup i kufizuar i quajtur alfabeti i gjendjeve të brendshme;

funksioni i tranzicionit automatik: ; ky funksion i cakton një gjendje çdo çifti "input-state";

funksioni i daljeve të makinës: ; ky funksion lidh çdo çift të gjendjes hyrëse me një vlerë dalëse.

Ligji i funksionimit të automatit: automati ndryshon gjendjen e tij në përputhje me funksionin dhe gjeneron sinjale dalëse në përputhje me funksionin:

1. Mënyrat për të përcaktuar një makinë shtetërore

1. Mënyra tabelare e vendosjes. Meqenëse për funksionet si qëllimi ashtu edhe vlerat i përkasin një grupi të fundëm, ato specifikohen duke përdorur tabela.

Shembulli 1. Le të përkufizojmë automatikun si më poshtë: , .Funksionin e përcaktojmë duke përdorur tabelën e tranzicionit, dhe funksionin duke përdorur tabelën e daljes.

Tabela 1. Tabela e kërcimit Tabela 2. Tabela e daljes

Nëse dihet sekuenca e sinjaleve në hyrje të automatit, atëherë sekuenca e daljes përcaktohet në mënyrë unike nga tabelat e tranzicioneve dhe daljeve.

2. Mënyra grafike e vendosjes. Përdoret një diagram kalim-dalje. Është një multigraf i drejtuar në të cilin çdo gjendje e brendshme e automatit korrespondon me një kulm. Kalimet e automatit nga gjendja në gjendje përshkruhen me shigjeta, në secilën prej të cilave shkruhet simboli hyrës që shkakton këtë tranzicion dhe simboli dalës i gjeneruar nga automati.

Fig.1 Diagrami i kalimeve-daljeve

Shembulli 2. Kërkohet ndërtimi i një automati që do të funksiononte si më poshtë: në çdo cikël, shifrat e radhës binare të termave merren në hyrje të automatit, automati gjeneron shifrën binare përkatëse të shumës së tyre. Për termat dyshifrorë kemi: , .

Automatoni është në gjendjen 1 nëse ndodh një bartje gjatë shtimit të shifrave të mëparshme, dhe në gjendjen 0 ndryshe. Diagrami kalim-dalje është paraqitur në fig. 2.

1. Problemi i sintezës së automatave

Në analogji me problemin e sintezës SFE, mund të parashtrohet një problem sinteze për automatat. Ekziston një grup i pakufizuar i automatave bazë. Kërkohet të montoni një automat me një funksionim të paracaktuar. Në të njëjtën kohë, detyra e sintezës përballet me probleme të caktuara.

Supozoni se duhet të lidhni daljen e automatit me hyrjen e automatit. Kjo është e mundur me kusht, pasi përndryshe automatiku i dytë nuk do të kuptojë sinjalet që vijnë nga i pari. Kjo çon në një situatë konfuze ku disa lidhje nuk janë të mundshme.

Për të kapërcyer këtë pengesë, prezantohet koncepti i një automati strukturor, në të cilin të gjitha alfabetet (hyrja, prodhimi dhe gjendjet e brendshme) janë të koduara me fjalë binare.

Le të jetë një grup i kufizuar elementesh dhe një grup fjalësh binare me gjatësi, ku. Një hartë injektive arbitrare do të quhet një kodim i një grupi me fjalë binare.

Le të kodojmë alfabetet për një automat arbitrar:

Le të shënojmë përkatësisht hyrjen, daljen dhe gjendjen e koduar të automatit në momentin e kohës. Më pas ligji i funksionimit do të paraqitet në formë

Automatoni i marrë pas kodimit quhet automat strukturor. Supozojmë se automati strukturor ka hyrje binare, dalje binare dhe gjendja e brendshme e automatit jepet nga një fjalë binar me gjatësi. Në fig. Figura 3 tregon një automat abstrakt dhe automatin strukturor përkatës.

Kalimi në një automat strukturor ofron dy avantazhe të rëndësishme për sintezën.

1. Pajtueshmëria e hyrjeve dhe daljeve, pasi informacioni binar transmetohet përmes tyre. Ne nuk do të japim një përkufizim të përgjithshëm të një qarku nga automatet strukturore ai është i ngjashëm me SFE.

2. Le të shkruajmë relacionet (2) në "koordinata":

Nga (3) rezulton se ligji i funksionimit të një automati strukturor jepet nga një sistem funksionesh Boolean.

1. Automata elementare

Ne veçojmë automatet më të thjeshta strukturore dhe u japim një emër.

Vini re fillimisht se një element funksional që ka vetëm një gjendje mund të konsiderohet si një automat pa memorie.

Le të kalojmë te automata me dy gjendje. Le të ketë automatiku një hyrje binare dhe një dalje binare që përputhen me gjendjen e brendshme:

Për të vendosur automatikun e treguar në Fig. 4, mjafton të vendosni vetëm tabelën e tranzicionit:

Tabela 3

Në vend të yjeve, duhet të vendosni 0 dhe 1. Kjo mund të bëhet në 16 mënyra, megjithatë, jo të gjitha janë të pranueshme. Supozoni, për shembull, që në kolonën e parë të tabelës 3 të dy elementët janë zero. Një automat i tillë, pasi të jetë në gjendjen 0, nuk do të dalë më prej tij, domethënë do të funksionojë si një element funksional. Një analizë e situatave të ngjashme tregon se për të marrë një automat që nuk është i reduktueshëm në një automat pa memorie, është e nevojshme të kërkohet që zero dhe një të ndodhin në secilën kolonë të Tabelës 3. Ka vetëm katër tavolina të tilla.

Tabela 4 Tabela 5

Tabela 6 Tabela 7

Kemi vetëm dy automata më të thjeshta, pasi 7 fitohet nga 4, dhe 6 nga 5 me përmbysje të gjendjeve të brendshme.

Automatoni i dhënë nga Tabela 4 quhet vonesë ose -shkallëzues:

domethënë ky automat e vonon sinjalin me një cikël.

Automatoni i specifikuar në Tabelën 5 quhet një shkas me një hyrje numërimi ose një shkas. Gjendja e automatit ndryshon në të kundërtën nëse hyrja është 1 dhe mbetet e pandryshuar nëse hyrja është 0:

Le të jetë -trigger në gjendjen 0 në momentin fillestar të kohës.Nëse në një moment të caktuar kohor -trigger është në gjendjen 0, atëherë kjo do të thotë se një numër çift prej 1 është marrë në hyrje të automatit. Nëse në gjendjen 1, atëherë është tek. Kështu, trigger-i numëron numrin e njësive në hyrje, por duke qenë se ka vetëm dy gjendje, numëron deri në dy.

Në zbatimin fizik të trigerëve përdoren dy dalje: direkte dhe inverse (Fig. 5). Nëse i ndërrojmë ato, atëherë nga -trigger marrim automatikun e specifikuar në Tabelën 7, dhe nga -trigger automatin e specifikuar nga Tabela 6.

1. Problemi i plotësisë së një baze automatike

Një grup automatesh strukturore quhet një bazë e plotë (ose automatike) nëse ndonjë automat strukturor i caktuar mund të ndërtohet prej tyre.

Përpjekjet e matematikanëve për të marrë një analog të teoremës së Postit për automatet ishin të pasuksesshme. Në vitin 1964 M.I. Shkurtimisht vërtetoi mosekzistencën e një algoritmi për përcaktimin e plotësisë së një sistemi. Në këtë rast, janë me interes variantet e teoremës së plotësisë me supozime shtesë për sistemin. Le të shqyrtojmë më të njohurit prej tyre.

Teorema. Një sistem automatikësh që përmban një grup të plotë FE-sh dhe një shkas (ose -trigger) është i plotë.

Dëshmi. Konsideroni një automat arbitrar të dhënë nga relacionet (2) dhe përshkruani skemën e tij të automateve të treguara, të quajtur struktura kanonike (Fig. 6).

Skema përbëhet nga dy pjesë.

Gjysma e majtë quhet pjesa e kujtesës. Ai përbëhet nga shkas, grupi i gjendjeve të të cilave formon gjendjen e automatit: nëse në momentin e kohës

atëherë do të thotë se automati është në gjendje.

Gjysma e djathtë quhet pjesa kombinuese dhe përfaqëson SFE-në. Hyrjet e këtij qarku janë:

1. sinjali binar i hyrjes së fjalëve të automatit;
2. gjendja e brendshme aktuale e fjalës binare e automatit.

1. sinjali binar i daljes së fjalës së automatit, i cili zbatohet sipas formulave (3);
2. një fjalë binare që hyn në hyrjet e nxitësve në pjesën e ruajtjes dhe kontrollon kujtesën e automatit.

Le të tregojmë se sinjalet e kontrollit të memories janë funksione Boolean të të njëjtave variabla si dalja e automatit, që do të thotë se ato mund të zbatohen nga një sistem i plotë FE.

Në çdo moment të kohës, sinjalet e kontrollit të kujtesës duhet të transferojnë automatikun nga një gjendje në tjetrën. Për ta bërë këtë, ju duhet të ndryshoni gjendjen e secilit shkas

Treguesit - ose -triggers të përdorur në skemën kanonike kanë këtë veti: për çdo palë gjendjesh, ekziston një sinjal hyrës që transferon automatikun nga një gjendje në tjetrën. Le ta shënojmë këtë sinjal me . Për -trigger, pasi gjendja në të cilën është vendosur -trigger është e barabartë me sinjalin hyrës. Për -trigger: kur, 0 duhet të aplikohet në hyrje në mënyrë që gjendja të mos ndryshojë; në 1, në mënyrë që këmbëza të "rrokulliset".

Pra, ose në formë vektoriale

Le të shprehemi nga ligji i funksionimit të automatit (2). Pastaj

Teorema është vërtetuar.

1. Metoda kanonike për sintezën e automateve

Le ta shqyrtojmë këtë metodë në një shembull konkret.

Shembull. Në transportues është instaluar një makinë automatike përgjatë së cilës lëvizin pjesë të dy llojeve, detyra e së cilës është të renditë pjesët në atë mënyrë që pasi të kalojnë pranë makinës të formojnë grupe. Makina e shtyn pjesën e papërshtatshme nga transportuesi. Kërkohet të ndërtohet një qark i një automati të tillë duke përdorur një shkas dhe elementë "AND", "OR", "JO".

Sinteza e automatit ndahet në fazat e mëposhtme.

1. Ndërtimi i një automati abstrakt.

Alfabeti i hyrjes . Alfabeti i daljes është , ku C është përplasja e pjesës, P kapërcimi i saj. Gjendjet e brendshme të automatit pasqyrojnë kujtesën e tij se cila pjesë e grupit ka formuar tashmë: . Ndërsa grupi formohet, automati lëviz në mënyrë ciklike nëpër këto gjendje pa ndryshuar gjendjen kur arrin një pjesë e papërshtatshme. Diagrami kalim-dalje është paraqitur në fig. 7.

2. Kodimi i alfabeteve.

Një nga opsionet e mundshme të kodimit është paraqitur në tabelat e mëposhtme.

Statusi i daljes hyrëse

3. Ndërtimi i strukturës kanonike të automatit.

Struktura kanonike e automatit që po zhvillohet është paraqitur në fig. tetë.

Le të gjejmë varësitë e rezultateve të SFE nga variablat, së pari në formë tabelare (Tabela 8), sipas së cilës do të ndërtojmë më tej formulat

Tabela 8

Këto funksione quhen të përcaktuara pjesërisht sepse nuk janë të përcaktuara në. Për të paraqitur këto funksione me formula, ato zgjerohen në mënyrë të tillë që të përftohet një formë më e thjeshtë formulash.

4. Paraqitja e funksioneve të daljes së automateve dhe funksioneve të kontrollit të memories sipas formulave.

Duke përdorur metodat e minimizimit të funksioneve Boolean, ne ndërtojmë një paraqitje ekonomike të funksioneve, nëse është e mundur, me formula në bazë:

5. Zbatimi i SFE-së dhe skema përfundimtare e automatit (Fig. 9).

PËRKUFIZIMI DHE METODAT E PËRCAKTIMIT TË AUTOMATIT FINIT. PROBLEMI I SINTEZËS. AUTOMATË KRYESORE