Primjeri apstraktnih automata koji izvode korisne radnje. Automat je diskretni informacijski transformator sposoban prihvatiti različita stanja, kretati se pod utjecajem ulaznih signala iz jednog stanja u drugo i izdavati izlaze
Tema 5.1. Obrada informacija pomoću strojeva s konačnim stanjima
Poglavlje 5. Osnove teorije konačnih automata
Sažetak po temama
Pregledajte pitanja
1. Je li to ruta?
2. U kojem se slučaju put naziva cikličkim?
3.Što je lanac?
4.Kada je lanac jednostavan lanac?
5. Dajte definiciju Eulerovog ciklusa?
6. Koja je razlika između Eulerovog i Hamiltonovog ciklusa?
7. Kada se graf naziva stablom?
8. Koje su povezane komponente šume?
9.Vrh se naziva terminal ako?
Ova tema raspravlja o konceptima kao što su put, ciklus, lanac, kontura i tako dalje u odnosu na grafikone. Dati su Eulerov i Hamiltonov ciklus. Prikazana je zasebna struktura grafa koja je definirana kao stablo. Sveukupnost ovih struktura karakterizira se kao šuma.
cilj: razmotriti temelje teorije konačnih automata.
Zadaci:
1. Razmotrimo koncept apstraktnog automata.
2. Otkrijte načine dodjeljivanja automata.
3. Razmotrite odnos između Mil i Moore automata.
Mašina - diskretni pretvarač informacija sposoban za prelazak iz stanja u stanje pod djelovanjem ulaznih signala i generiranje izlaznih signala.
Apstraktni automat definira se pomoću sljedećih pet skupova:
A \u003d (X, Y, S, d, l),
gdje X \u003d (X 1, X 2 ... X M) - ulazna abeceda automata ili skup ulaznih simbola;
Y \u003d (Y 1, Y 2 ... Y N) - izlazna abeceda automata ili skup izlaznih simbola;
S \u003d (S 0, S 1 ... S K-1) - abeceda ili skup unutarnjih stanja stroja;
S 0 Je početno stanje automata (u trenutku vremena t \u003d 0).
d - prijelazna funkcija;
l- funkcija izlaza stroja.
Stroj se zove državni stroj ako skupovi X, Y, S su konačni (ili izbrojivi).
Automat radi u diskretnim vremenima t \u003d 0, 1, 2 ... n(slika 5.1) .
Lik: 5.1. Konačni državni stroj
U svakom trenutku vremena automat se nalazi u jednom od stanja skupa S.
Prijelazna funkcija d tsljedeće stanje stroja ovisno o trenutna država i simbol unosa ili unosa abecede. Drugim riječima, funkcija dsvaki par "stanje - ulazni signal" dodjeljuje sljedeće stanje.
d: S'X® S; d- postoji mapiranje kartezijanskog proizvoda S´X u S.
Prijelazna funkcija može se napisati na sljedeći način: S t + 1 \u003d d (S t, X t).
Izlazna funkcija lodređuje u svakom trenutku vremena tizlazni signal stroja.
Postoje dva modela strojeva - Mealy stroj i Moore stroj. Oni se razlikuju u funkciji izlaza, koja je definirana kako slijedi:
Y t \u003d l (S t, X t) - za Milesov stroj, ili l: S´X®Y.
Y t \u003d l (S t) - za Mooreov stroj.
U Milesovom stroju, izlazni signal u to vrijeme t ovisi o ulaznom signalu u tom trenutku t, i iz trenutnog stanja.
U Mooreovom automatu, izlazni signal je očito neovisan o ulaznom signalu i određen je samo trenutnim stanjem.
Stanje stroja- ovo je sjećanje automata o prošlim ulaznim utjecajima.
Zovu se i automati sekvencijalni strojevi (Sekvencijalni strojevi) jer se ulazni slijed pretvara u slijed stanja i izlazni slijed.
Možemo reći da apstraktni automat ima 1 ulaz i 1 izlaz. Nizovi slova ulazne abecede dolaze na ulaz stroja, a izlazne sekvence se formiraju na izlazu.
Riječ ili lanac Je konačan niz znakova (slova) ulazne abecede. Moraju biti ispunjeni sljedeći uvjeti (uvjeti automatizacije):
1. Duljine ulaznih i izlaznih riječi su iste;
2. Identični početni segmenti ulaznih riječi odgovaraju identičnim početnim segmentima izlaznih riječi.
- 1.1 Osnovni pojmovi
- Zaključak
- Popis referenci
Uvod
Tema probni rad u disciplini "Primijenjena teorija digitalnih automata" - "Apstraktni digitalni automati".
Svrha rada je upoznati se s osnovnim pojmovima apstraktnih digitalnih automata; vrste apstraktni automati; načini definiranja apstraktnih automata; veza između modela Mealy i Moore; ekvivalentni automati i ekvivalentne transformacije automata; minimiziranje broja unutarnjih stanja automata i Aufenkamp-Hon algoritam.
1. Apstraktni digitalni automati
1.1 Osnovni pojmovi
Digitalni automat može se protumačiti kao uređaj koji prima, pohranjuje i transformira diskretne informacije prema nekom algoritmu. Sa određene točke gledišta, i stvarni uređaji (računala) i apstraktni sustavi (matematički modeli) mogu se klasificirati kao automati.
Automat je diskretni pretvarač informacija koji može prihvatiti različita stanja, kretati se pod utjecajem ulaznih signala iz jednog stanja u drugo i stvarati izlazne signale.
Opća teorija automata podijeljena je na apstraktnu i strukturnu.
Apstraktna teorija automata, apstrahirajući se od strukture automata (tj. Ne zanima ga način konstrukcije), proučava samo ponašanje automata u odnosu na vanjsko okruženje. Apstraktna teorija automata bliska je teoriji algoritama, u biti njena daljnja primjena.
Za razliku od apstraktne teorije automata, strukturnu teoriju automata zanimaju i struktura samog automata i struktura ulaznih radnji i odgovori automata na njih. Teorija strukture proučava metode konstruiranja automata, metode kodiranja ulaznih radnji i odgovora automata na njih. Strukturna teorija automata nastavak je i razvoj apstraktne teorije. Na temelju aparata logičkih funkcija i apstraktne teorije automata, strukturna teorija daje učinkovite preporuke za razvoj stvarnih računalnih uređaja.
Apstraktni digitalni automat (DA) matematički je model diskretnog upravljačkog uređaja.
Sažetak CA definiran je skupom koji se sastoji od šest elemenata:
S \u003d (X, A, Y, ao),
gdje:
X \u003d (x1, x2,. Xn) - skup ulaznih signala (ulazna abeceda);
Y \u003d (y1, y2, ym) - skup izlaznih signala (izlazna abeceda);
A \u003d (a0, a1, a2,. AN) - skup stanja (abeceda stanja);
ao - početno stanje (aoA);
- prijelazna funkcija automata koji specificira preslikavanje (HhA) A, tj. pridruživanje bilo kojeg para elemenata kartezijanskog proizvoda (XxA) s elementom skupa A;
- funkcija izlaza automata koja specificira ili preslikavanje (XxA) Y ili preslikavanje AY.
Drugim riječima, prijelazna funkcija pokazuje da automat S, budući da je u određenom stanju ajA, nakon pojave ulaznog signala xjX, prelazi u određeno stanje ajA. Ovo se može napisati:
ap \u003d (ai, Xj).
Izlazna funkcija pokazuje da automat S, budući da je u određenom stanju ajA, daje izlazni signal ukY kad se pojavi ulazni signal hjH. To se može zapisati: uk \u003d (ai , Xj).
Koncept stanja uveden je u definiciju automata zbog činjenice da je često potrebno opisati ponašanje sustava čiji izlazi ne ovise samo o stanju ulaza u ovaj trenutak vremena, ali i iz neke prapovijesti, t.j. iz signala koji su ranije primljeni na ulaze u sustav. Stanje samo odgovara nekom sjećanju na prošlost, omogućujući vam da eliminirate vrijeme kao eksplicitnu varijablu i izrazite izlazne signale u funkciji stanja i ulaza u određenom trenutku.
Apstraktni automat djeluje u diskretnom vremenu automata t \u003d 0,1,2,. a prijelazi države u državu su trenutni. U svakom trenutku t diskretnog vremena, automat je u određenom stanju a (t) iz skupa A stanja automata, a u početno vrijeme t \u003d 0 uvijek je u početnom stanju ao. U trenutku t, nalazeći se u stanju a (t), automat je u stanju opaziti signal x (t) X na ulaznom kanalu i izdati signal y (t) \u003d (a (t), x (t)) na izlaznom kanalu, prolazeći u stanje a (t + 1) \u003d \u003d (a (t), x (t)). Ovisnost izlaznog signala o ulaznom signalu i o stanju znači da on sadrži memoriju.
1.2 Vrste apstraktnih automata
Prema metodi generiranja izlazne funkcije razlikuju se tri vrste apstraktnih automata: Mealy automat, Moore automat, C-automat. Stroj Mealy karakterizira sustav jednadžbi:
y (t) \u003d (a (t), x (t));
a (t + 1) \u003d q (a (t), x (t)). (1-1)
Mooreov automat - sustavom jednadžbi:
y (t) \u003d (a (t));
a (t + 1) \u003d q (a (t), x (t)). (1-2)
S-automat - sustavom jednadžbi:
y \u003d y1y2
y1 (t) \u003d (a (t), x (t));
Y2 (t) \u003d 2 (a (t));
a (t + 1) \u003d q (a (t), x (t)).
Proizvoljni apstraktni Mealy ili Mooreov automat (slika 1.1.) Ima jedan ulazni i jedan izlazni kanal. Bilo koji apstraktni C-automat ima jedan ulazni i dva izlazna kanala (slika 1.2.).
Slika 1.1 - Apstraktni automat
Slika 1.2 Sažetak C-automata
Ako se ulaz apstraktnog Mealy ili Mooreova automata, postavljenog na početno stanje ao, hrani slovo po slovo nekim slijedom slova ulazne abecede x (0), x (1), je ulazna riječ, tada će se slova izlazne abecede pojaviti na izlazu automata y (0), y (1),. je izlazna riječ. Za slučaj C-automata na njegovim izlazima pojavit će se dvije sekvence: y1 (0), y1 (1),. i y2 (0), y2 (1),. U apstraktnom C - automatu, izlazni signal y2 (t) \u003d (a (t)) emitira se cijelo vrijeme dok je automat u stanju a (t). Izlazni signal y1 (t) \u003d l1 (a (t), x (t)) emitira se tijekom djelovanja ulaznog signala x (t) kada je C-stroj u stanju a (t).
Dakle, na razini apstraktne teorije, funkcioniranje digitalnog automata razumijeva se kao pretvaranje ulaznih riječi u izlazne riječi.
Razlikuju se potpuno definirani i djelomični automati.
Apstraktni digitalni automat naziva se potpuno definiranim, u kojem su prijelazna funkcija ili izlazna funkcija, ili obje ove funkcije definirane za sve parove prijelaza (xi, aj).
Apstraktni digitalni automat naziva se djelomičnim ako ima prijelaznu funkciju ili izlaznu funkciju, ili obje ove funkcije nisu definirane za sve parove prijelaza (xi, aj).
Apstraktni digitalni automat naziva se početnim ako se početno stanje Ao razlikuje na skupu njegovih stanja A.
1.3 Metode za definiranje apstraktnih automata
Za definiranje konačnog automata S potrebno je opisati sve elemente skupa: S \u003d (X, A, Y, ao). Postoji nekoliko načina za podešavanje rada stroja, ali najčešće se koriste tabelarni (matrični), grafički i analitički.
U tabličnom načinu rada automat je određen dvjema tablicama: prijelaznom tablicom i izlaznom tablicom ili matricom veza. Prijelazna tablica proizvoljnog potpuno definiranog automata konstruirana je na sljedeći način: redovi tablice označeni su slovima ulazne abecede automata, a stupci tablice slovima abecede stanja automata; U ćeliji prijelazne tablice koja se nalazi na presjek reda označenog ulaznim signalom xi i stupca označenog stanjem aj, postavlja se stanje ak, što je rezultat prijelaza automata iz stanja aj pod utjecajem ulaznog signala xi, što se određuje izrazom ak \u003d (aj, xj).
Tablica 1.1 Tablica strojnog prijelaza
Primjer popunjavanja prijelazne tablice nekog apstraktnog potpuno definiranog automata s ulaznom abecedom X \u003d (x1, x2) - i abecedom stanja A \u003d (a1, a2, a3) prikazan je u tablici 1.2.
Tablica 1.2
Ako je apstraktni automat djelomičan, tada se u ćeliju tablice njegovih prijelaza smještenih na presjeku crte označene ulaznim signalom i stupca označenog odgovarajućim stanjem (pod uvjetom da prijelaz u to stanje pod djelovanjem ovog ulaznog signala nije) stavlja crtica i svaka ulazna riječ što dovodi do naznačenog prijelaza je zabranjeno.
Ispunjavanje ostatka stanica slično je slučaju potpuno definiranog automata. Pogled prijelazne tablice ne ovisi o vrsti navedenog automata (Mealy, Moore, S-automat) Tablice izlaznih rezultata strojeva Mealy, Moore i S-automat imaju razlike.
Tablica rezultata potpuno definiranog Mealy automata konstruirana je na sljedeći način: identifikacija stupaca i redaka, kao i format tablice, odgovaraju prijelaznoj tablici potpuno definiranog automata. U ćeliji izlazne tablice, smještenoj na presjeku reda označenog ulaznim signalom Xj, i stupca označenog stanjem ak, postavljen je izlazni signal Um, koji automat izdaje, nalazeći se u stanju ak u prisutnosti ulaznog signala Xj, što je određeno izrazom Ym \u003d (ak, xj ).
Tablica 1.3. Tablica rezultata apstraktnog Mealy automata.
Primjer popunjavanja tablice rezultata nekog apstraktnog potpuno definiranog automata s ulaznom abecedom X \u003d (x1, x2), abecedom stanja A \u003d (a1, a2, a3) i izlaznom abecedom Y \u003d (y1, y2, y3) predstavljen je u tablici 1.4.
Tablica 1.4
Očito je da apstraktni potpuno definirani C-automat daju dvije tablice rezultata, od kojih je prva tablica rezultata Mealy-jevog automata, a druga Moore-a. Ako je automat djelomičan, tada u nekim ćelijama njegove tablice može biti crtica, što znači odsutnost izlaznog signala.
U praksi se prijelazni i izlazni stolovi često kombiniraju u jednu tablicu, koja se naziva označena tablica strojnog prijelaza. Primjeri označenih prijelaznih tablica prikazani su u tablici 1.6. - 1.8 (Opći prikaz označene prijelazne tablice - Tablica 1.6., Označena prijelazna tablica Mealy automata - Tablica 1.7., Označena prijelazna tablica Mooreovog automata - Tablica 1.8.).
Uz prethodno raspravljene tablice prijelaza i izlaza, proizvoljni apstraktni automat može se odrediti matricom veze.
Matrica veza je kvadratna i sadrži onoliko stupaca (redaka) koliko abeceda stanja datog automata sadrži različita stanja. Svaki je stupac (redak) matrice veza označen državnim slovom stroja. U ćeliji koja se nalazi na presjeku kolone označene slovom aj i crte označene slovom od automata, stavlja se ulazni signal (ili disjunkcija ulaznih signala) pod utjecajem kojeg se taj prijelaz provodi.
Za apstraktni Mealyjev automat, izlazni signal se također stavlja u ćeliju pored stanja, što automat izdaje kao rezultat ovog prijelaza (tablica 1.9.) Za Mooreov automat, izlazni signal stavlja se u red pored stanja (ta stanja odgovaraju početnim stanjima automata).
Tablica 1.6
Tablica 1.8
U grafičkom načinu postavljanja, apstraktni automati prikazani su usmjerenim grafovima. Graf automata usmjereni je povezani graf čiji vrhovi odgovaraju stanjima automata, a lukovi između njih odgovaraju prijelazima između stanja. Dva su vrha ak i as povezana lukom ako automat ima prijelaz iz stanja ak u stanje as. Za Mealyev automat ulazni i izlazni signali stavljaju se na luk koji odgovara ovom prijelazu (slika 1.3.), Za Mooreov automat ulazni signal stavlja se na luk, a izlazni signal stavlja u blizinu vrha koji odgovara stanju (slika 1.4.)
Ovdje se razmatraju samo deterministički automati za koje je ispunjen uvjet jedinstvenosti prijelaza: automat u određenom stanju ne može prijeći u više od jednog stanja pod djelovanjem bilo kojeg ulaznog signala. Što se primjenjuje na grafički način definiranja automata, to znači da u grafu automata dva ili više luka označenih istim ulaznim signalom ne mogu izaći iz bilo kojeg vrha.
Slika 1.3-Grafikon Mealyjeva automata Slika 1.4-Grafikon Mooreova automata
U analitičkom načinu postavljanja, apstraktni automati određeni su s četiri objekta:
S \u003d (X, A, Y, F), gdje F definira za svako stanje aj automata preslikavanje (XxA) - > (AxY). Drugim riječima, u analitičkoj metodi specificiranja za svako stanje automata aj naznačeno je preslikavanje Fai, što je skup svih trojki ap, xm, yk i takvo da pod utjecajem ulaznog signala xm automat prelazi iz stanja ij u stanje ap, dok daje izlazni signal yk.
Primijenjeno na opća definicija apstraktni automat, potonji je ekvivalentan opisu funkcija d i l u skladu s izrazom: ap \u003d d (ai, xm), yk \u003d l (ai, xm).
Fai mapiranje napisano je kako slijedi:
Fai (ap (Xm / yk), ai (Xf / yz) ...).
Za apstraktni Mealy automat (tablica 1.7.) Analitički je zadatak sljedeći:
S \u003d (X, A, Y, F), X \u003d (x1, x2), A \u003d (a1, a2, a3), Y \u003d (y1, y2, y3),
Fa1 \u003d (a2 (x1 / y2), a1 (x2 / y3)),
Fa2 \u003d (a3 (x1 / y3), a1 (x2 / y1)),
Fa3 \u003d (a1 (x1 / y3), a2 (x2 / y2)).
Treba imati na umu da se Fai funkcija uvijek snima u izvornom stanju.
Odredimo sinkrone i asinkrone automate. Stanje automata S naziva se stabilnim stanjem ako je za bilo koji ulazni signal xjX takav da je \u003d q (ai Xm) as \u003d q (as, xm).
Automat S naziva se asinkronim ako je svako njegovo stanje kao A stabilno. Automat S naziva se sinkroni ako nije asinkron.
Treba napomenuti da su automati konstruirani u praksi uvijek asinkroni i da se stabilnost njihovih stanja uvijek osigurava na ovaj ili onaj način, na primjer uvođenjem sinkronizacijskih signala. Međutim, na razini apstraktne teorije automata, kada je automat samo matematički model koji ne odražava mnoge specifične značajke njegove provedbe, često je prikladnije raditi sa sinkronim automatima.
1.4 Veza između modela Mealy i Moore
Kao što je već napomenuto, apstraktni automat radi kao pretvarač riječi ulazne abecede u riječi izlazne abecede.
Neka je graf na slici 1.5 apstraktni Mealyev automat.
Ulaz ovog automata, postavljen u početno stanje, prima ulaznu riječ X \u003d x1, x1, x2, x1, x2, x2.
Slika 1.5 - Grafikon stroja Mealy
Jer? (a1, x1) \u003d a3, a? (a1, x1) \u003d y1, tada će pod djelovanjem prvog slova riječi X ulaznog signala x1 automat ući u stanje a3 i na njegovom izlazu pojavit će se signal y1. Dalje,? (a3, x1) \u003d a1, ha? (a3, x1) \u003d y2, pa kad stigne drugi signal x1, automat će biti u stanju a1, a izlaz će mu biti signal y2. Tragom daljnjeg ponašanja automata izravno u grafu ili tablicama prijelaza i izlaza, opisujemo ga s tri retka, od kojih prvi odgovara ulaznoj riječi X, drugi redoslijedima stanja koja automat prolazi pod djelovanjem slova riječi X, a treći izlaznoj riječi Y koja se pojavljuje na izlazu mašina:
x1x1 x2 x1 x2 x2
a1a3 a1a1 a3 a2 a3
y1 y2 y1 y1 y1 y2
Nazovimo u = ? (a1, X) reakcijom Mealy automata u stanju a1 na ulaznu riječ X. Kao što se može vidjeti iz primjera, kao odgovor na ulaznu riječ duljine k, Mealy automat izbacuje slijed stanja duljine k + 1 i izlaznu riječ duljine k. Općenito, ponašanje Mealy automata postavljenog u stanje am može se opisati kako slijedi:
Na isti način možemo opisati ponašanje Mooreovog automata u stanju am kada je ulazna riječ xi1, xi2,., Hik . Podsjetimo da, u skladu s (1-2), izlazni signal u Mooreovom automatu u trenutku vremena t (Y (t)) ovisi samo o stanju u kojem se automat nalazi u trenutku t (a (t)):
Očito je da izlazni signal yi1 \u003d l (am) u trenutku i1 ne ovisi o ulaznom signalu xi1, već ga određuje samo stanje am.
Dakle, ovaj signal yi1 nema nikakve veze s ulaznom riječju koja ulazi u ulaz automata, počevši od trenutka i1. S tim u vezi, pod reakcijom Mooreova automata postavljenog u stanje am na ulaznu riječ X \u003d xi1, xi2 , . , xik mislimo na izlaznu riječ iste duljine y \u003d l (am, X) \u003d yi2, yi3,., yik + 1.
Kao primjer, razmotrite Mooreov automat S5, čiji je graf prikazan na sl. 1-6, i pronađite njegovu reakciju u početnom stanju na istu ulaznu riječ koju smo koristili za analizu ponašanja Mealy automata S1:
Slika 1-6 - Mooreov graf automata
Kao što se može vidjeti iz ovog i prethodnih primjera, odgovori automata S5 i S1 u početnom stanju na ulaznu riječ X podudaraju se do pomaka za 1 takta (odgovor Mooreova automata zaokružen je crtom). Sada dajemo rigoroznu definiciju ekvivalencije potpuno definiranih automata.
Dva automata SA i SB s istim ulaznim i izlaznim abecedama nazivaju se ekvivalentnima ako se, nakon postavljanja u početno stanje, reakcije na bilo koju ulaznu riječ podudaraju.
1.5 Ekvivalentni strojevi. Ekvivalentne transformacije automata
Može se pokazati da za bilo koji Mealyev automat postoji ekvivalentni Mooreov automat i, obratno, za bilo koji Mooreov automat postoji ekvivalentni Mealyev automat.
Pri opisivanju algoritama za međusobnu transformaciju Mealyjevih i Mooreovih automata u skladu s gore navedenim, zanemarit ćemo u Mooreovim automatima izlazni signal povezan s početnim stanjem (? (A1)).
Prvo razmotrimo transformaciju Mooreovog automata u Mealyev automat.
Neka je dan Mooreov automat: SA \u003d (HA, AA, UA ,? A ,? A, aoA), gdje:
XA \u003d (x1, x2, .xn); Y \u003d (y1, y2,. Ym); A \u003d (a0, a1, a2, aN); a0A \u003d a0 - početno stanje (a0AA); ? A - prijelazna funkcija automata, koja specificira preslikavanje (HAAAA) -\u003e AA; ? A - funkcija izlaza automata, postavljanje zaslona AA-\u003e UA.
Konstruirajmo Mealyev automat: SB \u003d (XB, AB, YB, ?? B,? B , a0B), u kojem je AB \u003d AA; XB \u003d XA; YB \u003d YA; ? B \u003d? A; a0B \u003d a0A. Funkcija izlaza? B definirana je kako slijedi. Ako je u Mooreovom automatu? A (am, x1) \u003d as i? A (as) \u003d \u200b\u200byg, onda u Mealyjevom stroju? B (am, x1) \u003d yg
Slika 1.7 - Ilustracija prijelaza s Mooreova na Mealyjev model
Prijelaz s Mooreova automata na Mealy automat na grafički način postavljanja prikazan je na slici 1-7: izlazni signal yg zapisan uz vrh (as) prenosi se na sve lukove koji ulaze u taj vrh.
Na tablični način specificiranja automata, prijelazna tablica Mealy automata podudara se s prijelaznom tablicom izvornog Mooreova automata, a izlazna tablica dobiva se iz prijelazne tablice zamjenom simbola na presjeku retka xf i stupca am simbolom izlaznog signala yg koji označava stupac kao u prijelaznoj tablici automata SA.
Iz same metode konstrukcije Mealy automat SB, očito je da je ekvivalentan Moore automatu SA. Indukcijom je lako pokazati da će bilo koja ulazna riječ konačne duljine primijenjena na ulaze automata SA i SB, postavljena na stanja am, uzrokovati pojavu identičnih izlaznih riječi i, prema tome, automati SA i SB su ekvivalentni.
Prije razmatranja transformacije Mealy stroja u stroj Moore, postavimo sljedeće ograničenje Mealy automatu: automat ne bi trebao imati prijelazna stanja. Pod privremenim podrazumijevamo stanje u kojem niti jedan luk ne ulazi kada je automat predstavljen u obliku grafa, ali koji ima barem jedan izlazni luk. Dakle, neka se dobije Milesov automat:
SA \u003d (XA, AA, YA ,? A ,? A, a0A),
gdje:
XA \u003d (x1, x2, .xn); Y \u003d (y1, y2,. Ym); A \u003d (a0, a1, a2, .aN); a0A \u003d a0 - početno stanje (a0AA); ? A - funkcija prijelaza automata, specificirajući preslikavanje (HAxAA) -\u003e AA; ? A - funkcija izlaza automata, specificirajući preslikavanje (HAxAA) -\u003e YA.
Konstruirajmo Mooreov automat: SB \u003d (XB, AB, YB ,? B ,? B, a0B), u kojem je XB \u003d XA; YB \u003d YA.
Da bismo definirali AB, svakom stanju kao AA pridružujemo skup As svih mogućih parova oblika (as, yg)
Funkcija izlaza? B definirana je kako slijedi. Svakom stanju Mooreova automata SB, koji je par oblika (kao, yg), dodjeljujemo izlazni signal yg.
Ako je u automatu SA Mealy došlo do prijelaza ΔA (am, xf) \u003d as i izlazni signal ΔA (am, xf) \u003d yg, tada će u SB doći do prijelaza iz skupa stanja Am koje generira am u stanje (kao, yg) ulaznim signalom xf.
Kao početno stanje a0B može se uzeti bilo koje stanje skupa A0, koje generira početno stanje a0 automata SA. U tom slučaju ne treba uzimati u obzir izlazni signal u trenutku t \u003d 0.
Pogledajmo primjer. Neka je dat automat Mealy (tablica 1.10.)
Dodijelimo svakom paru ai / xk stanje bik (i-broj stanja, k-broj ulaznog signala), uzimajući u obzir b0.
Sastavimo prijelaznu tablicu Mooreova automata, vodeći se sljedećim pravilima:
1) Zapišimo iz tablice 1.11 stanja Mealyjeva automata i skupove stanja Mooreova automata (bik) koji odgovaraju svakom od njih:
a0 \u003d (b0, b02, b11, b21); a1 \u003d (b22); a2 \u003d (b01, b12);
2) Ako je stanje Mooreova automata bik uključeno u skup koji odgovara stanju ap automata Mealy, tada bi u retku prijelazne tablice Mooreova automata za stanje bik trebao biti zapisan red iz prijelazne tablice Mealy automata koji odgovara stanju ap (od 1.10.).
3) Izlazna funkcija Mooreova automata definirana je na sljedeći način:? B (bik) \u003d? A (ai, xk). Za početno stanje b0, vrijednost izlaznog signala može se odabrati proizvoljno, ali generirano početnim stanjem a0 (uzimajući u obzir koncept ekvivalencije stanja). Rezultirajuća tablica prijelaza i izlaza Mooreova automata ekvivalentna Mealy automatu navedenom u tablici 1.10 predstavljena je u tablici 1.12.
4) Pronađite ekvivalentna stanja u tablici 1.12 i uklonite ih (zamijenite ih predstavnicima razreda ekvivalencije).
Ako se izlazni signal u blizini b0 proširi na definiranje y1, ispada da ova prijelazna tablica sadrži 3 ekvivalentna stanja (b0, b11, b02). Zamjenjujući razred ekvivalencije s jednim predstavnikom (b0), dobivamo konačnu prijelaznu tablicu (tablica 1.13).
Tablica 1.12
Iznesene metode međusobne transformacije automata Mealy i Moore pokazuju da se tijekom prijelaza s Mooreova automata na Mealy automat broj stanja automata ne mijenja, dok se tijekom obrnutog prijelaza broj stanja u Mooreovom automatu, u pravilu, povećava.
Dakle, automati međusobno ekvivalentni mogu imati različit broj stanja, u vezi s kojima je problem pronalaska minimuma (sa minimalni broj stanja) automata u klasi ekvivalentnih automata. Postojanje bilo kojeg apstraktnog automata ekvivalentnog apstraktnog automata s minimalnim brojem unutarnjih stanja prvi je dokazao Moore.
1.6 Minimiziranje broja unutarnjih stanja stroja
Aufenkamp-Hon algoritam.
Metoda minimiziranja stanja automata temelji se na ideji razdvajanja svih stanja izvornog, apstraktnog automata u uparene disjunktne klase ekvivalentnih stanja i zamjenu svake klase ekvivalencije jednim stanjem (predstavnikom ove klase). Kao rezultat ovih transformacija minimalni automat ima isti broj stanja kao i početna stanja podijeljena u klase ekvivalencije.
Dva stanja automata am i as nazivaju se ekvivalentnima (am \u003d kao) ako? (am, X) \u003d? (kao, X) za sve moguće ulazne riječi duljine X.
Ako am i kao nisu ekvivalentni, mogu se razlikovati. Slabija ekvivalencija je K-ekvivalencija. Države jesu i jesu li K ekvivalentne ako? (am, Xk) \u003d? (kao, Xk) za sve moguće ulazne riječi duljine K. Kada se minimalizira broj unutarnjih stanja Mealyjeva automata S \u003d (X, Y, A ,? , ?, a0), koristi se algoritam Aufenkamp-Hon:
1. Pronađite sukcesivne particije? 1,? 2, ...,? K ,? K + 1, postavite A u klase jedno-, dva -,., K-, (K + 1) - ekvivalentnih stanja do neki (K + 1) korak ne ispada da je? k \u003d? k + 1. U ovom su slučaju ekvivalentna K-stanja. Broj koraka K, na kojima? K \u003d? K + 1 ne prelazi N-1, gdje je N broj unutarnjih stanja stroja.
2. U svakoj klasi ekvivalencije? odaberite jedan element (predstavnik klase), koji tvori skupove A "stanja minimalnog automata S".
3. Funkcija prijelaza? "A izlazi?" automat S "definiran je na skupu A" xX.
Za to se u tablici prijelaza i izlaza brišu stupci koji odgovaraju "stanjima koja nisu uključena u skup A", a u preostalim stupcima tablice prijelaza sva stanja zamjenjuju se ekvivalentnima iz skupa A "(od predstavnika).
4. Jedno od stanja ekvivalentno stanju a0 odabire se kao "0. Konkretno, prikladno je uzeti samo stanje a0.
Kada se minimizira Mooreov automat, uvodi se koncept 0-ekvivalencije stanja i podjele skupa stanja u 0-klase: sva stanja Mooreova automata koja su jednako označena izlaznim signalima nazivaju se 0-ekvivalentima. Kao primjer, razmotrite minimiziranje Mooreova automata dato tablicom prijelaza i izlaza (tablica 1.14).
Tablica 1.14
Podijelimo? 0:
? 0 \u003d (B1, B2, B3);
B1 \u003d (a1, a2, a8), B2 \u003d (a6, a9, a10, a11, a12), B3 \u003d (a3, a4, a5, a7).
Izgradimo tablicu particija? 0:
Podijelimo? 1:
1 \u003d (C1, C2, C3, C4);
C1 \u003d (a1, a2, a8), C2 \u003d (a6, a9, a11), C3 \u003d (a10, a12), C4 \u003d (a3, a4, a5, a7).
Izgradimo tablicu particija? 1:
Učinite cijepanje? 2 .
1 \u003d (D1, D2, D3, D4);
D1 \u003d (a1, a2, a8), D2 \u003d (a6, a9, a11), D3 \u003d (a10, a12), D4 \u003d (a3, a4, a5, a7).
Particija? 2 ponavlja particiju? 1 - postupak particioniranja je završen.
Odaberemo proizvoljno iz svake klase ekvivalencije D1, D2, D3, D4 po jednog predstavnika - u ovom slučaju minimalnim brojem: A "\u003d (a1, a3, a6 , a10).
Uklanjajući "dodatna" stanja iz izvorne prijelazne tablice, definiramo minimalni Mooreov automat (tablica 1.15.)
Tablica 1.15.
Zaključak
U procesu izvođenja testa upoznali smo se s osnovnim konceptima apstraktnih digitalnih automata; vrste apstraktnih automata; načini definiranja apstraktnih automata; veza između modela Mealy i Moore; ekvivalentni automati i ekvivalentne transformacije automata; minimiziranjem broja unutarnjih stanja automata i Aufenkamp-Hon algoritma - dati su primjeri.
Popis referenci
1. Samofalov KG, Romankevich AM, et al. Primijenjena teorija digitalnih automata. - Kijev. "Škola Višća" 1987.
2. Solovjev G.N. Računalni računski uređaji. - M. "Energija". 1978.
3. Saveliev A.Ya. Primijenjena teorija digitalnih automata - M. "Viša škola". 1987.
4. Kagan B.M. Elektronička računala i sustavi. - M. Energoatomizdat. 1985. godine.
5. Lysikov B.G. Aritmetički i logički temelji digitalnih automata. - Minsk. "Srednja škola". 1980.
Na izlazu daje znakove (općenito) druge abecede.
Apstraktni automat
Formalno, apstraktni automat definira se kao petica
Ograničenje broja parametara apstraktnog automata definiralo je takav koncept kao konačni automat.
Rad automata sastoji se u generiranju dvije sekvence: niza uzastopnih stanja automata i niza izlaznih simbola, koji se za niz simbola odvijaju u trenucima diskretnog vremena t \u003d 1, 2, 3, ... Trenuci diskretnog vremena nazivaju se krpeljima.
Rad automata u diskretnim trenucima vremena t može se opisati sustavom ponavljajućih odnosa:
Uvedena je klasifikacija kako bi se pojasnila svojstva apstraktnih automata.
Apstraktni automati čine temeljnu klasu diskretnih modela kao neovisni model i kao glavna komponenta Turingovih strojeva, FFS strojeva, strojeva s konačnim stanjima i ostalih pretvarača informacija.
Zaklada Wikimedia. 2010.
- Dijagram stanja (teorija automata)
- Nagorno-Karabah
Pogledajte što je "Apstraktni automat" u drugim rječnicima:
apstraktni automat - apstraktusis automatas statusas T sritis automatika atitikmenys: angl. apstraktni automat vok. sažetak Automat, m rus. apstraktni automat, m pranc. automatizirati sažetak, m ... Automatikos terminų žodynas
Mašina - U Wiktionary-u postoji članak "automatski" Automatski: Automatski uređaj koji samostalno izvodi neke radnje ... Wikipedia
Konačni državni stroj - Konačni automat je apstraktni automat bez izlaznog toka, čiji je broj mogućih stanja konačan. Rezultat rada automata određen je konačnim stanjem. Postoje razne mogućnosti za specificiranje državnog stroja. Na primjer, ... ... Wikipedia
TURING STROJ - Apstraktni automat (odnosno računalo ili neki drugi precizan, određen mehanizam), kojeg je teoretski okarakterizirao britanski matematičar Alan M. Turing 1930-ih. U osnovi se Turingov stroj sastoji od vrpce i glave za čitanje. Vrpca ... ... Rječnik u psihologiji
Teorija automata
Teorija automata - dio teorijske kibernetike koji proučava matematičke modele (ovdje se nazivaju automati ili strojevi) stvarnih ili mogućih uređaja koji obrađuju diskretne informacije u diskretnim ciklusima. Glavni ... ... Ekonomsko-matematički rječnik
teorija automata - Ogranak teorijske kibernetike, koji proučava matematičke modele (ovdje se nazivaju automati ili strojevi) stvarnih ili mogućih uređaja koji diskretne informacije obrađuju u diskretnim koracima. Osnovni pojmovi ove teorije ... ... Vodič za tehničkog prevoditelja
Teorija automata - Teorija automata grana je diskretne matematike koja proučava apstraktne automate računarskih strojeva, predstavljena u obliku matematičkih modela i problema koje mogu riješiti. Teorija automata najuže je povezana s ... ... Wikipedijom
Računalo - Dijagram osobnog računala: 1. Monitor 2. Matična ploča 3 ... Wikipedia
Formalne metode - Primjer formalne specifikacije pomoću Z notacije U računalnoj znanosti i softverskom inženjerstvu, formalne metode su skupina tehnika koje se temelje na matematičkom aparatu za ... Wikipedia
Prema metodi generiranja izlazne funkcije razlikuju se tri vrste apstraktnih automata: Mealy automat, Moore automat, C-automat. Stroj Mealy karakterizira sustav jednadžbi:
y (t) \u003d (a (t), x (t));
a (t + 1) \u003d δ (a (t), x (t)). (1-1)
Mooreov automat - sustavom jednadžbi:
a (t + 1) \u003d δ (a (t), x (t)). (1-2)
S-automat - sustavom jednadžbi:
y 1 (t) \u003d (a (t), x (t));
Y2 (t) \u003d 2 (a (t));
a (t + 1) \u003d δ (a (t), x (t)).
Proizvoljni apstraktni Mealy ili Mooreov automat (slika 1.1.) Ima jedan ulazni i jedan izlazni kanal. Proizvoljni apstraktni C-automat ima jedan ulazni i dva izlazna kanala (slika 1.2.).
Slika 1.1 - Apstraktni automat
Slika 1.2 Sažetak C-automata
Ako je ulaz apstraktnog Mealy-ovog ili Mooreova automata, postavljen na početno stanje a, pošaljite slovo po slovo određeni niz slova ulazne abecede x (0), x (1),. je ulazna riječ, tada će se slova izlazne abecede pojaviti na izlazu automata y (0), y (1),. je izlazna riječ. Za slučaj C-automata, na njegovim izlazima pojavit će se dvije sekvence: y 1 (0), y 1 (1),. i y 2 (0), y 2 (1),. U apstraktnom C - automatu, izlazni signal y 2 (t) \u003d (a (t)) emitira se cijelo vrijeme dok je automat u stanju a (t). Izlazni signal y 1 (t) \u003d λ 1 (a (t), x (t)) emitira se tijekom djelovanja ulaznog signala x (t) kada je C-stroj u stanju a (t).
Dakle, na razini apstraktne teorije, funkcioniranje digitalnog automata razumijeva se kao transformacija ulaznih riječi u izlazne riječi.
Razlikuju se potpuno definirani i djelomični automati.
Apstraktni digitalni automat naziva se potpuno definiranim ako ima prijelaznu funkciju ili izlaznu funkciju ili su obje ove funkcije definirane za sve parove prijelaza (x i, a j).
Apstraktni digitalni automat naziva se djelomičnim ako ima prijelaznu funkciju ili izlaznu funkciju, ili obje ove funkcije nisu definirane za sve parove prijelaza (x i, a j).
Apstraktni digitalni automat naziva se početnim ako se na skupu njegovih stanja A razlikuje početno stanje ao.
1.3 Metode za definiranje apstraktnih automata
Za definiranje konačnog automata S potrebno je opisati sve elemente skupa: S \u003d (X, A, Y ,,, a o). Postoji nekoliko načina za podešavanje rada stroja, ali najčešće se koriste tabelarni (matrični), grafički i analitički.
U tabličnom načinu rada automat je određen dvjema tablicama: prijelaznom tablicom i izlaznom tablicom ili matricom veza. Prijelazna tablica proizvoljnog potpuno definiranog automata konstruirana je na sljedeći način: redovi tablice označeni su slovima ulazne abecede automata, a stupci tablice slovima abecede stanja automata; U ćeliji prijelazne tablice koja se nalazi na presjek crte označene ulaznim signalom x i stupca označenog stanjem a j, postavlja se stanje a k, što je rezultat prijelaza automata iz stanja a j pod utjecajem ulaznog signala x i, što je određeno izrazom a k \u003d (a j, x j).
Tablica 1.1 Tablica strojnog prijelaza
|
Države | ||||
|
ulazni signali |
||||
|
(a k, x j) |
Primjer popunjavanja prijelazne tablice nekog apstraktnog potpuno definiranog automata s ulaznom abecedom X \u003d (x 1, x 2) - i abecedom stanja A \u003d (a 1, a 2, a 3) prikazan je u tablici 1.2.
Tablica 1.2
Ako je apstraktni automat djelomičan, tada se u ćeliji tablice njegovih prijelaza smještenih na presjeku crte označene ulaznim signalom i stupca označenog odgovarajućim stanjem (pod uvjetom da prijelaz u to stanje pod djelovanjem ovog ulaznog signala nije) stavlja crtica i svaka ulazna riječ što dovodi do naznačenog prijelaza je zabranjeno.
Ispunjavanje ostatka stanica slično je slučaju potpuno definiranog automata. Pogled prijelazne tablice ne ovisi o vrsti navedenog automata (Mealy, Moore, S-automat). Tablice rezultata strojeva Mealy, Moore i S-stroj imaju razlike.
Izlazna tablica potpuno definiranog Mealy-jevog automata konstruirana je na sljedeći način: identifikacija stupaca i redaka, kao i format tablice, odgovaraju prijelaznoj tablici potpuno definiranog automata. U ćeliju izlazne tablice, smještenu na presjeku reda označenog ulaznim signalom X j, i stupca označenog stanjem a k, stavlja se izlazni signal Y m, koji automat izdaje, nalazeći se u stanju a k u prisutnosti ulaznog signala Xj, što je određeno izrazom Ym \u003d (a k, x j).
Tablica 1.3. Tablica rezultata apstraktnog Mealy automata.
|
Države | ||||
|
Ulazni signali |
||||
Primjer popunjavanja tablice rezultata nekog apstraktnog potpuno definiranog automata s ulaznom abecedom X \u003d (x 1, x 2), abecedom stanja A \u003d (a 1, a 2, a 3) i izlaznom abecedom Y \u003d (y 1, y 2, y 3 ) -predstavljeno u tablici 1.4.
Tablica 1.4
Očito je da apstraktni potpuno definirani C-automat daju dvije tablice rezultata, od kojih je prva tablica rezultata Mealy-jevog automata, a druga Moore-a. Ako je automat djelomičan, tada u nekim ćelijama njegove tablice može biti crtica, što znači da nema izlaznog signala.
U praksi se prijelazni i izlazni stolovi često kombiniraju u jednu tablicu, koja se naziva označena tablica strojnog prijelaza. Primjeri označenih prijelaznih tablica prikazani su u tablici 1.6. - 1.8 (Opći prikaz označene prijelazne tablice - Tablica 1.6., Označena prijelazna tablica Mealy automata - Tablica 1.7., Označena prijelazna tablica Mooreovog automata - Tablica 1.8.).
Uz prethodno raspravljene tablice prijelaza i izlaza, matricom veze može se odrediti proizvoljni apstraktni automat.
Matrica veza je kvadratna i sadrži onoliko stupaca (redaka) koliko abeceda stanja datog automata sadrži različita stanja. Svaki je stupac (redak) matrice veza označen državnim slovom stroja. U ćeliji smještenoj na presjeku stupca označenog slovom a j i retka označenog slovom a s automata stavlja se ulazni signal (ili disjunkcija ulaznih signala) pod čijim se utjecajem provodi taj prijelaz.
Za apstraktni Mealyev automat, izlazni signal se također stavlja u ćeliju pored stanja, što automat izdaje kao rezultat ovog prijelaza (tablica 1.9.) Za Mooreov automat, izlazni signal stavlja se u red pored stanja (ta stanja odgovaraju početnim stanjima automata).
Tablica 1.6
|
Države | ||||
|
Ulazni signali |
||||
|
(a 2, x j) |
(a k, x j) |
|||
|
(a 2, x j) |
(a k, x j) |
Tablica 1.7
Tablica 1.9.
U grafičkom načinu postavljanja, apstraktni automati predstavljeni su usmjerenim grafovima. Graf automata usmjereni je povezani graf čiji vrhovi odgovaraju stanjima automata, a lukovi između njih odgovaraju prijelazima između stanja. Dva vrha a k i s povezana su lukom ako automat ima prijelaz iz stanja a k u stanje a. Za Mealyev automat ulazni i izlazni signali stavljaju se na luk koji odgovara ovom prijelazu (slika 1.3.), Za Mooreov automat ulazni signal stavlja se na luk, a izlazni signal spušta se uz vrh koji odgovara stanju (slika 1.4.).
Ovdje se razmatraju samo deterministički automati za koje je zadovoljen uvjet jednoznačnih prijelaza: automat u određenom stanju, pod djelovanjem bilo kojeg ulaznog signala, ne može ići u više stanja. Što se primjenjuje na grafički način definiranja automata, to znači da u grafu automata dva ili više luka označenih istim ulaznim signalom ne mogu izaći iz bilo kojeg vrha.
|
|
|
Slika 1.3-Grafikon Mealy-jevog automata Slika 1.4-Grafikon Moore-ovog automata
U analitičkom načinu postavljanja, apstraktni automati određeni su s četiri objekta:
S \u003d (X, A, Y, F), gdje F definira za svako stanje i j automata preslikavanje (XxA) - > (AxY). Drugim riječima, u analitičkoj metodi postavljanja za svako stanje automata a j naznačeno je preslikavanje F ai, što je skup svih trojki a p, x m, y k, i takvo da pod utjecajem ulaznog signala x m automat prelazi iz stanja i j u stanje a p, dok daje izlazni signal y k.
S obzirom na opću definiciju apstraktnog automata, potonji je ekvivalentan opisu funkcija δ i λ u skladu s izrazom: a p \u003d δ (a i, x m), y k \u003d λ (a i, x m).
Mapiranje F ai zapisano je kako slijedi:
F ai (a p (X m / y k), a i (X f / y z) ...).
Za apstraktni Mealy automat (tablica 1.7.) Analitički je zadatak sljedeći:
S \u003d (X, A, Y, F), X \u003d (x 1, x 2), A \u003d (a 1, a 2, a 3), Y \u003d (y 1, y 2, y 3),
F a1 \u003d (a 2 (x 1 / y 2), a 1 (x 2 / y 3)),
F a 2 \u003d (a 3 (x 1 / y 3), a 1 (x 2 / y 1)),
F a 3 \u003d (a 1 (x 1 / y 3) i 2 (x 2 / y 2)).
Treba napomenuti da se funkcija F ai uvijek bilježi za početno stanje.
Odredimo sinkrone i asinkrone automate. Stanje a s automata S naziva se stabilnim stanjem ako se za bilo koji ulazni signal x j X takav da je a s \u003d δ (a i X m) a s \u003d δ (a s, x m).
Automat S naziva se asinkronim ako je svako njegovo stanje a s A stabilno. Automat S naziva se sinkroni ako nije asinkron.
Treba napomenuti da su automati konstruirani u praksi uvijek asinkroni i da se stabilnost njihovih stanja uvijek osigurava na ovaj ili onaj način, na primjer uvođenjem sinkronizacijskih signala. Međutim, na razini apstraktne teorije automata, kada je automat samo matematički model koji ne odražava mnoga specifična obilježja njegove provedbe, često je prikladnije raditi sa sinkronim automatima.
