Apstraktni automat. Opća teorija automata dijeli se na apstraktnu i strukturnu
Digitalni (diskretni) automat može se tumačiti kao uređaj koji prima, pohranjuje i pretvara diskretne informacije prema nekom algoritmu. S određenog gledišta, i stvarni uređaji (računala, živi organizmi itd.) I apstraktni sustavi (matematički strojevi, aksiomatske teorije
Opća teorija automata dijeli se na apstraktnu i strukturnu. Razlika među njima leži u činjenici da apstraktna teorija, apstrahirana iz strukture automata (tj. Ne zanima ga metoda konstruiranja), proučava samo ponašanje automata u odnosu na vanjsko okruženje. Apstraktna teorija automata stoga je bliska teoriji algoritama, te je u biti njezina daljnja pojedinost. Za razliku od apstraktne teorije, strukturalnu zanima i struktura samog automata i struktura ulaznih radnji i odgovora automata na njih. U strukturnoj teoriji proučavaju se metode konstruiranja automata, metode kodiranja ulaznih radnji i reakcija automata. Dakle, strukturna teorija automata nastavak je i daljnji razvoj apstraktna teorija. Na temelju aparata Booleovih funkcija i apstraktne teorije automata, strukturna teorija daje učinkovite preporuke za razvoj stvarnih računalnih uređaja.
Apstraktni digitalni automat A određen je skupom od pet objekata gdje je skup ulaznih signala automata A (ulazna abeceda automata A); - skup stanja automata A (abeceda stanja automata je skup izlaznih signala automata A (izlazna abeceda automata A); - prijelazna funkcija
automat A, koji definira preslikavanje, tj. dodjeljuje u skladu s bilo kojim parom elemenata kartezijanskog proizvoda skupova element skupa - funkciju izlaza automata A, koji određuje preslikavanje ili preslikavanje
Drugim riječima, prijelazna funkcija pokazuje da automat A, koji se nalazi u određenom stanju kad se pojavi ulazni signal, prelazi u određeno stanje.daje izlazni signal Potonji se može napisati izrazom
Prema metodi generiranja izlazne funkcije razlikuju se tri vrste apstraktnih automata: Mealyjev automat, Mooreov automat i C-automat. U apstraktnom Miles -ovom automatu izlazna funkcija X definira preslikavanje. U apstraktnom Mooreovom automatu, izlazna funkcija specificira preslikavanje na apstraktni C-automat, uvode se dvije izlazne funkcije X i definiraju preslikavanje. U ovom slučaju, abeceda izlaza C-automata je ili
Proizvoljan apstraktni Milan ili Mooreov automat ima jedan ulazni i jedan izlazni kanal (slika 10.1). Proizvoljan apstraktni C-automat ima jedan ulazni i dva izlazna kanala (slika 10.2).
Razlikuju se potpuno definirani i djelomični automati.
Apstraktni digitalni automat naziva se potpuno definiran, u kojem su prijelazna funkcija i izlazna funkcija definirane za sve parove
Apstraktni digitalni automat naziva se djelomičnim ako ima prijelaznu funkciju ili izlaznu funkciju, ili obje ove funkcije nisu definirane za sve parove.
Apstraktni digitalni automat naziva se početnim ako je na skupu njegovih stanja 5 dodijeljeno posebno početno stanje, tj. Početni apstraktni automat određen je skupom od šest objekata. Odabir na skupu početnog stanja objašnjava se čisto praktična razmatranja povezana s često nastalom potrebom da se utvrde uvjeti za početak rada automata.
Kaže se da apstraktni automat djeluje u diskretnom vremenu automata, a prijelazi iz stanja u stanje provode se trenutno. U svakom trenutku diskretnog vremena automat je u nekom stanju iz skupa stanja. Ako je automat početni, tada je u početnom trenutku uvijek u početnom stanju. U trenutku dok je u stanju, automat može na ulazu uočiti slovo ulazne abecede u skladu s funkcijom izlaza X, istodobno će dati slovo izlazne abecede, a u u skladu s prijelaznom funkcijom, prijeđite na sljedeći
stanje Prema definiciji apstraktnog automata, Mealyjev automat u ovom slučaju karakterizira sustav jednadžbi:
Mooreov automat - sustavom jednadžbi;
a C-automat je sustav jednadžbi:
Drugim riječima, ako se ulazna riječ isporučuje slovo po slovo na ulaz početnog apstraktnog Mealy ili Moore automata, postavljenog na početno stanje, niz slova ulazne abecede, izlazna će se riječ pojavljivati uzastopno na izlazu automat. U slučaju C-automata, dvije sekvence pojavit će se na njegovim izlazima: za apstraktni C-automat izlaznom signalu se daju svi bonusi dok je lntomit u stanju.
Tako se na razini apstraktne teorije funkcioniranje digitalnog automata shvaća kao transformacija ulaznih riječi u izlazne riječi.
Koncept stanja u definiciji apstraktnog automata uveden je zbog činjenice da većina stvarnih procesa kojima upravljaju zapravo konstruirani digitalni automati zahtijevaju poznavanje prapovijesti razvoja procesa na vrijeme za njihov ispravan tijek. Drugim riječima, izlazni signal koji stroj izdaje u ovaj trenutak vrijeme, određuje ne samo ulazna radnja na automatu, već i stanje u kojem se automat u tom trenutku nalazio. vrijeme za organiziranje ispravnog rada stroja, pored ulaznog signala "prekidač semafora" ", potrebno je imati podatke o položaju semafora u prethodnom trenutku u vremenu. Ove informacije pruža prisutnost različitih stanja apstraktnog automata. Apstraktni digitalni automati koji odgovaraju uvedenoj definiciji apstraktnog automata nazivaju se i apstraktnim automatima s memorijom, budući da je postojanje u različitim automatima različitih stanja moguće samo ako automat ima memoriju.
Brojni procesi koji su kontrolirani stvarnim automatima ne zahtijevaju poznavanje pretpovijesti razvoja procesa na vrijeme za njihov ispravan tijek. U strojevima koji kontroliraju takve procese,
Tablica 10.1
izlazni signal određuje se samo ulaznom radnjom na stroju. Gore navedeni automati na razini apstraktne prezentacije definirani su pomoću tripleta, gdje izlazna funkcija specificira preslikavanje i naziva se apstraktnim automatima s trivijalnom memorijom ili kombinacijskim automatima. Najjednostavniji analog kombiniranog stroja može čitati običnu električnu svjetiljku, pod uvjetom da ulazna radnja pritisne tipku "Uključeno", a izlazni signal je osvjetljenje žarulje svjetiljke.
Abecede ulaza, stanja i izlaza automata specificirane su kao obični skupovi, na primjer, navođenjem njihovih elemenata. Funkcije prijelaza i izlaza mogu se definirati matrično, grafički i analitički. Stoga se svaki apstraktni automat može specificirati na tri načina! matrična, grafička i analitička
U matričnoj metodi, automat je predstavljen ili s dvije tablice: prijelaznom tablicom i izlaznom tablicom, ili matricom povezivanja.izlazima automata.
Prijelazna tablica proizvoljnog potpuno definiranog apstraktnog automata konstruirana je na sljedeći način. Stupci tablice označeni su slovima ulazne abecede automata, a redovi tablice slovima abecede stanja automata. U ćeliji prijelazne tablice, koja se nalazi na sjecištu stupca označenog ulaznim signalom i crte označene stanjem, postavlja se stanje koje je rezultat prijelaza automata iz stanja pod utjecajem ulazni signal, koji je određen karticom izraza. 10.1. Ako je apstraktni automat djelomičan, tada se u ćeliji tablice njegovih prijelaza nalazi na sjecištu stupca označenog ulaznim signalom i crte označene stanjem (pod uvjetom da prijelaz iz stanja pod utjecajem ulaza signal nije definiran), stavlja se crtica i zabranjena je svaka ulazna riječ koja vodi do navedenog prijelaza. Popunjavanje ostatka ćelija isto je kao u slučaju potpuno definiranog automata. Primjer prijelazne tablice nekog apstraktnog djelomičnog automata s ulaznom abecedom i abecedom stanja prikazan je u tablici. 10.2. Prikaz prijelazne tablice ne ovisi o vrsti postavljenog automata (Mooreov automat, Miles, S-automat). Tablice Mooreovih, Milesovih i C -ovih izlaza automata imaju razlike. Tablica rezultata potpuno definiranog Miles stroja izrađena je na sljedeći način. Identifikacija stupaca i redaka, kao i format tablice, odgovaraju tablici skokova potpuno definiranog automata. U ćeliji tablice izlaza,
Tablica 10.2
Tablica 10.3
Tablica 10.4
koji se nalazi na sjecištu stupca označenog ulaznim signalom i crte označene stanjem, postavlja se izlazni signal koji Mealy automat izdaje, budući da je u stanju uz prisutnost ulaznog signala, što je određeno izrazom tab. 10.3.
Tablica izlaza potpuno definiranog Mooreovog automata konstruirana je jednostavnije: svakom stanju automata dodijeljen je vlastiti izlazni signal. Primjer tablice Mooreovih automatovih izlaza s abecedom stanja i izlaznom abecedom prikazan je u tablici 10.4.
Očito, apstraktni potpuno definirani C-automat dan je s dvije tablice izlaza, od kojih je prva tablica izlaza Mealyjevog automata, a druga tablica izlaza Mooreova automata.
Ako je automat Miles djelomičan, tada u nekim ćelijama njegove izlazne tablice može biti crtica, što znači da nema izlaznog signala. U tom slučaju crtica se mora postaviti u one ćelije izlazne tablice koje odgovaraju istim ćelijama s crticom u prijelaznoj tablici Miles -ovog automata. Ovo posljednje je posljedica činjenice da ako postoji par u Mealyjevom djelomičnom automatu i takav da je prijelaz iz stanja pod utjecajem ulaznog signala neodređen, tada je, naravno, vrijednost izlaznog signala na takvom ( nepostojeći) prijelaz je također nedefiniran. Primjer tablice izlaza djelomičnog Mealy automata dane prijelaznom tablicom (tablica 10.2) s izlaznom abecedom predstavljen je u tablici. 10.5
Crtice u nekim ćelijama izlazne tablice Mooreovog djelomičnog automata nisu povezane s crticama u ćelijama njegove prijelazne tablice. To je određeno činjenicom da izlazni signal Mooreovog automata ovisi samo o stanju u kojem se automat nalazi. Na primjer, tablica izlaza djelomičnog Mooreovog automata koju daje prijelazna tablica (tablica 10.2),
Tablica 10.5
Tablica 10.6.
Tablica 10.7
može se prikazati kao tablica. 10.4, ako u svakom od svojih stanja stroj izdaje neku vrstu izlaznog signala, a kao tablica. 10.6, ako je vrijednost izlaznog signala stroja za neka stanja nedefinirana.
U praksi se tablice prijelaza i izlaza stroja često kombiniraju u jednu tablicu, koja se naziva označena tablica prijelaza stroja. Označena tablica prijelaza potpuno definiranog Mealyjevog automata, predstavljena tablicom prijelaza (tablica 10.1) i tablicom izlaza (tablica 10.3), sažeta je u tablici. 10.7. Zabilježena tablica prijelaza djelomičnog Mooreova automata (tablica 10.2) i tablica izlaza (tablica 10.4) sažeta su u tablici. 10.8.
Osim gore opisanih prijelaznih i izlaznih tablica, proizvoljni apstraktni automat može se opisati i matricom veza. Takav opis jedan je od načina definiranja apstraktnih automata u matrici. Matrica veza proizvoljnog apstraktnog automata je kvadratna i sadrži onoliko stupaca (redaka) koliko broj različitih stanja ima automat koji se razmatra. Svaki stupac (redak) matrice veza označen je slovom stanja stroja. Ako je automat početni, tada se prvi stupac s lijeve strane i prvi redak s vrha matrice njegovih veza označavaju slovom početnog stanja automata., Pod čijim utjecajem dolazi do prijelaza automata iz stanja u stanje. Ako je apstraktni Milneov automat specificiran matricom veze, tada je slovo izlaznog signala naznačeno u zagradama pored slova ulaznog signala, što automat Mealy izdaje, čineći prijelaznu matricu veza nekih Mealyjevih automata predstavljenih označenom prijelaznom tablicom (Tablica 10.7) prikazana je na Sl. 10.3.
Ako je apstraktni Mooreov automat naveden matricom veze, tada su stanja automata koja identificiraju redove matrice veze označena izlaznim signalima.
Tablica 10.8
U grafičkom načinu postavljanja, apstraktni su automati prikazani usmjerenim grafovima; stanja automata prikazana su vrhovima grafa, a prijelazi između stanja predstavljeni su lukovima između odgovarajućih vrhova. U tom slučaju, svako slovo ulazne abecede automata dodjeljuje se svakom luku grafikona, što ukazuje da se ovaj prijelaz automata vrši samo kada se pojavi ulazni signal i svaki vrh grafa je slovo odgovarajuće stanje automata. Ako graf predstavlja automat Mila, tada se izlazni signali automata stavljaju na lukove grafikona (u skladu s tablicom izlaza automata) pored slova ulaznog signala. Primjer Mealyjevog automatiziranog grafikona, danog prijelaznom tablicom (tablica 10.1) i izlaznom tablicom (tablica 10.3), prikazan je na sl. 10.4. Ako je Mooreov automat predstavljen grafikonom, tada se izlazni signali automata postavljaju blizu vrhova grafa (u skladu s izlaznom tablicom automata). Primjer Mooreovog automat grafikona, dan prijelaznom tablicom (tablica 10.2) i izlaznom tablicom (tablica 10.4), prikazan je na sl. 10.5.
U analitičkoj metodi dodjeljivanja apstraktni su automati predstavljeni s četiri objekta gdje postavlja preslikavanje za svako stanje automata. Drugim riječima, u analitičkoj metodi postavljanja za svako stanje automata prikazan je zaslon koji je skup svih trojki i takav da pod utjecajem ulaznog signala automat vrši prijelaz iz stanja u stanje, dok izdaje izlazni signal. opća definicija apstraktni automat, potonji je ekvivalentan opisu funkcija i X u skladu s izrazima: Mapiranje je napisano na sljedeći način:
Analitički zadatak automata Mealy, predstavljen označenom prijelaznom tablicom (tablica 10.7), ima sljedeći oblik.
Razmotrimo ekvivalentnu transformaciju automata. Ekvivalentni automati su oni koji induciraju isto preslikavanje skupa riječi u ulaznoj abecedi u skup riječi u izlaznoj abecedi. Razmotrimo samo transformaciju Mooreova automata u ekvivalentni Mealyjev automat. Pretvaranje Mealyjevog automata u ekvivalentni Mooreov automat nešto je složenije.
Prijelaz s Mooreova automata na ekvivalentni Mealyjev automat prikladno je izvesti pomoću grafičke metode definiranja automata. U tom se slučaju svodi na prijenos izlaznog signala koji je Mooreov automat izdao u stanju u lukove koji ulaze u vrh označen slovom. U matričnoj metodi postavljanja, prijelazna tablica Mealyjevog automata poklapa se s prijelazom tablica Mooreova automata, a tablica izlaza Mealyjevog automata dobiva se iz njegove prijelazne tablice zamjenom slovnog stanja koje se nalazi na sjecištu stupca označenog ulaznim signalom i redaka do izlaznog signala koji izdaje Mooreov automat u državi
Razvoj pravih automata (predstavljen barem na razini temeljnog električni krugovi) zahtijeva njihovo dodjeljivanje najprije na apstraktnoj razini s naknadnim prijelazom na strukturnu razinu, uzimajući u obzir logičke elemente korištene u krugu automata i veze među njima. S tim u vezi, javlja se problem sinteze apstraktnog automata, polazeći od nekog početnog, na primjer, verbalnog opisa njegovog rada. Postojeći algoritmi za sintezu apstraktnih automata obično se ne koriste u praksi zbog složenosti i glomaznosti izračuna, pa se stoga ne uključuju u udžbeničko gradivo. Međutim, radi boljeg razumijevanja koncepta apstraktnog automata i načina njegovog definiranja, ovdje ćemo razmotriti primjer sinteze apstraktnog automata, temeljen na čisto spekulativnim razmatranjima.
Primjer. Konstruirajte apstraktnu digitalnu automatsku kontrolu za uključivanje semafora, pod uvjetom da samo signal "prebaci semafor" stiže na ulaz automatskog uređaja. Označimo ovaj signal slovom, a njegov nedostatak slovom
Očito će se ulazna abeceda X takvog automata sastojati od dva slova: Budući da sintetizirani automat mora osigurati da se semafor prebaci na crveno, žuto i zelena boja, tada uvodimo tri odgovarajuća izlazna upravljačka signala Uzmimo također da je u trenutku početka rada automat u stanju Algoritam rada je trivilan; moguće rješenje za stroj Mealy prikazano je na sl. 10.6, a za Mooreov automat - na Sl. 10.7. Za (pojednostavljenje, pretpostavljamo da u početnom trenutku Mooreov automat izdaje izlazni signal "uključi zelenu boju". Imajte na umu da ćete za konstruiranje automatiziranog grafikona morati unijeti četiri različita stanja. Broj stanja može smanjiti, na primjer, povećanjem broja ulaznih signala automata ili proširenjem mogućnosti plana pamćenja povijesti razvoja procesa upravljanja u vremenu (u ovom primjeru samo trenutak izdavanja posljednjeg izlaza signal se memorira).
Zaključno, napominjemo da razmatramo samo determinističke automate za koje je zadovoljen uvjet nedvosmislenih prijelaza: automat u određenom stanju ne može prijeći u više od jednog stanja pod djelovanjem bilo kojeg ulaznog signala. Automat naveden prijelaznom tablicom uvijek je deterministički, budući da se na sjecištu stupca i retka prijelazne tablice zapisuje samo jedno stanje ako je prijelaz definiran, a crtica je umetnuta ako prijelaz nije definiran. Primijenjeno na grafičku metodu definiranja automata, uvjet jedinstvenosti znači da u grafikonu automata dva ili više lukova označenih istim ulaznim signalom ne mogu izaći iz bilo kojeg vrha.
1.1 Osnovni pojmovi
1.4 Odnos između modela Mealy i Moore
1.5 Ekvivalentni strojevi. Ekvivalentne transformacije automata
1.6 Minimiziranje broja unutarnjih stanja automata
Bibliografija
Uvod
Tema probni rad u disciplini "Primijenjena teorija digitalnih automata" - "Apstraktni digitalni automati".
Svrha je rada upoznati osnovne pojmove apstraktnih digitalnih automata; vrste apstraktnih automata; načini definiranja apstraktnih automata; povezanost modela Mealy i Moore; ekvivalentni automati i ekvivalentne transformacije automata; minimiziranje broja unutarnjih stanja automata i Aufenkamp-Hon algoritma.
1. Apstraktni digitalni automati
1.1 Osnovni pojmovi
Digitalni automat može se tumačiti kao uređaj koji prima, pohranjuje i transformira diskretne informacije prema nekom algoritmu. S određenog gledišta, i stvarni uređaji (računala) i apstraktni sustavi (matematički modeli) mogu se klasificirati kao automati.
Automat se naziva diskretni pretvarač informacije, sposobne prihvatiti različita stanja, kretati se pod utjecajem ulaznih signala iz jednog stanja u drugo i stvarati izlazne signale.
Opća teorija automata dijeli se na apstraktnu i strukturnu.
Apstraktna teorija automata, apstrahirajući se iz strukture automata (tj. Ne zanima ga metoda njegove konstrukcije), proučava samo ponašanje automata s obzirom na vanjsko okruženje. Apstraktna teorija automata bliska je teoriji algoritama i u biti je njezina daljnja implementacija.
Za razliku od apstraktne teorije automata, strukturnu teoriju automata zanima i struktura samog automata i struktura ulaznih radnji i odgovora automata na njih. U strukturnoj teoriji proučavaju se metode konstruiranja automata, metode kodiranja ulaznih radnji i odgovora automata na njih. Strukturna teorija automata nastavak je i razvoj apstraktne teorije. Na temelju aparata Booleovih 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:
, a o),X = (x 1, x 2 ,. X n) - skup ulaznih signala (ulazna abeceda);
Y = (y 1, y 2, y m) - skup izlaznih signala (izlazna abeceda);
A = (a 0, a 1, a 2 ,. A N) - skup stanja (abeceda stanja);
a o - početno stanje (a o
A); - prijelazna funkcija automata koja specificira preslikavanje (XxA) A, tj. povezivanje bilo kojeg para elemenata kartezijanskog proizvoda (XxA) s elementom skupa A;- funkcija izlaza automata, specificirajući preslikavanje (XxA)
Y ili preslikavanje AY.Drugim riječima, prijelazna funkcija
pokazuje da automat S, koji je u određenom stanju a j A, kada se pojavi ulazni signal x j X, prelazi u određeno stanje a p A. To se može napisati: (a i, X j).Izlazna funkcija pokazuje da je automat S, koji je u nekom stanju a j
A kad se pojavi ulazni signal x j X, on daje izlazni signal y k Y. To se može napisati: y k = (a i , X j).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 određenom trenutku vremena, već i o nekim prapovijesti, tj od signala koji su ranije dolazili na ulaze sustava. Stanje samo odgovara nekom sjećanju na prošlost, omogućujući vam da eliminirate vrijeme kao eksplicitnu varijablu i izrazite izlazne signale kao funkciju stanja i ulaza u danom trenutku.
Apstraktni automat radi u diskretnom vremenu automata t = 0,1,2,. a prijelazi iz stanja u stanje su trenutačni. U svakom trenutku t diskretnog vremena automat je u određenom stanju a (t) iz skupa A stanja automata, a u početnom trenutku vremena t = 0 uvijek je u početnom stanju a o. U trenutku t, u stanju a (t), automat je u stanju opaziti signal x (t) na ulaznom kanalu
X, a signal y (t) = (a (t), x (t)) na izlaznom kanalu, prelazeći u stanje a (t + 1) = (a (t), x (t)). Ovisnost izlaznog signala o ulaznom signalu i stanju znači da sadrži memoriju.1.2 Vrste apstraktnih automata
Prema metodi generiranja izlazne funkcije razlikuju se tri vrste apstraktnih automata: Mealyjev automat, Mooreov automat i C-automat. Mealyjev automat karakterizira sustav jednadžbi:
(a (t), x (t));a (t + 1) = δ (a (t), x (t)). (1-1)
Mooreov automat - sustavom jednadžbi:
(a (t));a (t + 1) = δ (a (t), x (t)). (1-2)
S -automat - sustavom jednadžbi:
y 2 (a (t), x (t)); 2 (a (t));a (t + 1) = δ (a (t), x (t)).
Proizvoljan apstraktni Mealy ili Mooreov automat (slika 1.1.) Ima jedan ulazni i jedan izlazni kanal. Proizvoljan 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 unos apstraktnog Mealy ili Moore automata, postavljen na početno stanje a o, pošaljite slovo po slovo određeni slijed 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č. U slučaju C-automata, dvije sekvence pojavit će se na njegovim izlazima: y 1 (0), y 1 (1),. i y 2 (0), y 2 (1),. U apstraktnom C -automatu, izlazni signal y 2 (t) =
(a (t)) se izdaje cijelo vrijeme dok je automat u stanju a (t). Izlazni signal y 1 (t) = λ 1 (a (t), x (t)) izdaje se tijekom djelovanja ulaznog signala x (t) kada je C-stroj u stanju a (t).Tako se na razini apstraktne teorije funkcioniranje digitalnog automata shvaća 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 je skupu njegovih stanja A dodijeljeno početno stanje ao.
1.3 Metode definiranja apstraktnih automata
Za definiranje konačnog automata S potrebno je opisati sve elemente skupa: S = (X, A, Y,
,, a o). Postoji nekoliko načina za podešavanje rada stroja, ali najčešće se koriste tablični (matrični), grafički i analitički.U tabličnom načinu rada automat je određen s dvije tablice: 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 označeni su slovima abecede stanja automat; U ćeliju prijelazne tablice, koja se nalazi na sjecištu retka označenog ulaznim signalom xi, i stupca označenog stanjem aj, stavlja se stanje ak, koje je rezultat prijelaza automata iz stanja aj pod utjecajem ulaznog signala xi, koji je određen izrazom ak =
(a j, x j).6 Osnovni pojmovi i definicije teorije apstraktnih automata (predavanje broj 9)
Digitalni (diskretni) automat (DA) je uređaj koji prima, pohranjuje i / ili pretvara diskretne informacije prema nekom algoritmu. Primjeri CA mogu biti živi organizmi, procesori, kućanski aparati, kalkulatori - to su stvarni uređaji, a postoje i apstraktni, na primjer, modeli algoritama. Ciljna publika se odnosi na serijski uređaji. Ova klasa uređaja određena je činjenicom da vrijednost izlaza ne ovisi samo o ulaznim vrijednostima, već i o trenutnom stanju uređaja. Oni. uveden je koncept - stanje... Za spremanje podataka o stanju uređaja u ciljanu publiku koriste se elementi za pohranu - okidači.
6.1 Matematički model digitalnog automata
Digitalni automat je uređaj koji karakterizira skup unutarnjih stanja u koja će pasti pod utjecajem naredbi programa ugrađenih u njega. Prijelaz automata iz jednog stanja u drugo vrši se u određenom vremenskom trenutku.
Matematički model ciljne publike (i u općem slučaju bilo kojeg diskretnog uređaja) je takozvani apstraktni automat, definiran kao 6-komponentni niz: S = (A, X, Y, , , a 1) u kojem:
A = (a 1, a 2, ..., a m) - abeceda stanja - skup stanja u kojima se može nalaziti projektirani digitalni automat. Broj država igra važnu ulogu u provedbi ciljne publike. Što je više država, to je više memorijskih elemenata (okidača) potrebno za izgradnju ciljne publike.
X = (x 1, x 2, ..., x f) - abeceda ulaznih vrijednosti - skup vrijednosti koje mogu ući u CA ulaz. Na primjer, ako stroj ima dvoznamenkasti binarni ulaz, tada elementi abecede mogu biti 00, 01, 10 i 11.
Y = (y 1, y 2, ..., y g) - abeceda izlaznih vrijednosti - skup vrijednosti koje se mogu postaviti na izlazu CA.
: A • XA - prijelazna funkcija a (t + 1) = (x (t), a (t))... Prijelazna funkcija određuje koje stanje a (t + 1) uključit će stroj pod utjecajem ulaznog signala x (t), ako je u trenutnom trenutku automat u stanju a (t).
: A • ZW - funkcija izlaza y(t)= (a(t), x(t)). Funkcija izlaza određuje koju izlaznu vrijednost y(t) bit će instaliran na izlazu stroja ovisno o ulaznoj vrijednosti x(t) i trenutno stanje a(t) .
a i A - početno stanje stroja - stanje u kojem je DA postavljen nakon uključivanja ili nakon resetiranja
Slika 6.1 - Apstraktni automat
Apstraktni automat (slika 6.1) ima jedan ulaz i jedan izlaz. Automat radi u diskretnom vremenu, uzimajući negativne cjelobrojne vrijednosti t = 0,1,2, ... U svakom trenutku t diskretnog vremena, automat je u nekom stanju a (t) iz skupa stanja automat, a u početnom trenutku t = 0 uvijek je u početnom stanju a (0) = a1. U trenutku t, koji je u stanju a (t), automat je sposoban opaziti na ulazu slovo ulazne abecede X (t) Z. U skladu s funkcijom izlaza, on će istodobno ispisati t slova izlazne abecede y (t) = (a (t), z (t)) i, u skladu s prijelaznom funkcijom, , preći će u sljedeće stanje a (t + 1) = , a (t) A, y (t) Y.
Značenje koncepta apstraktnog automata je da on ostvaruje određeno preslikavanje skupa riječi ulazne abecede X u skup riječi izlazne abecede Y. To jest, ako je niz slova ulazne abecede x (0), x (1), ... ulazna riječ koja se dovodi na ulaz automata, postavljena na početno stanje a1, tada slova izlazne abecede y (0), y (1), ... je izlazna riječ. Da. izlazna riječ = (ulazna riječ), gdje je pping preslikavanje izvedeno apstraktnim automatom.
Na razini apstraktne teorije koncept "rada automata" shvaća se kao transformacija ulaznih riječi u izlazne. Možemo reći da u apstraktnom automatu odvraćamo pozornost od njegove strukture - sadržaja pravokutnika (slika 6.1), smatrajući ga "crnom kutijom", t.j. usredotočujemo se na ponašanje automata u odnosu na vanjsko okruženje.
Koncept stanja u definiciji automata uveden je zbog činjenice da je često potrebno opisati ponašanje sustava čiji izlazi ne ovise samo o stanju ulaza u određenom trenutku vremena, već i o nekim prapovijesti, tj od signala koji su ranije primljeni na ulaze sustava. Stanja samo odgovaraju nekom sjećanju na prošlost, omogućujući vam da eliminirate vrijeme kao eksplicitnu varijablu i izrazite izlazni signal kao funkciju stanja i unosa u danom trenutku u vremenu.
6.2 Klasifikacija digitalnih strojeva
Gore opisani apstraktni automati mogu se podijeliti na:
potpuno definirano i djelomično;
deterministički i vjerojatni;
sinkrone i asinkrone;
Djelomično naziva se apstraktnim automatom, čija prijelazna funkcija ili izlazna funkcija, ili obje ove funkcije nisu definirane za sve parove (a i, z j).
DO deterministički Postoje automati za koje je zadovoljen uvjet jedinstvenosti prijelaza: automat u određenom stanju a i ne može prijeći u više od jednog stanja pod djelovanjem bilo kojeg ulaznog signala z j.
Inače će biti vjerojatni automat , u kojem je za zadano stanje a i i zadani ulazni signal z j moguć prijelaz s zadanom vjerojatnošću u različita stanja.
Za utvrđivanje sinkrone i asinkrone automata uvodi koncept stacionarno stanje ... Stanje a s automata naziva se stabilnim ako je za bilo koje stanje a i i ulazni signal z j takvo da je (a i, z j) = a s (a s, z j) = a s, tj. stanje je stabilno ako automat, ušavši u to stanje pod djelovanjem nekog signala zj, napusti samo pod djelovanjem drugog signala z k, različitog od z j.
Automat u kojem su sva stanja stabilna - asinkroni .
Stroj se zove sinkroni ako nije asinkrono.
Apstraktni automat naziva se konačni
ako su skupovi A = (a 1, a 2, ..., am), Z = (z 1, z 2, ..., zf), W = (w 1, w 2, ..., wg) . Stroj se zove početni
ako je u njemu odabrano početno stanje a 1.
6.3 Vrste digitalnih strojeva
U praksi su najraširenije dvije klase strojeva - strojevi Mealy i Moore.
Zakon funkcioniranja Mealyjevog automata dan je jednadžbama:
a (t + 1) = (a (t), z (t)); w (t) = (a (t), z (t)), t = 0,1,2, ...
Zakon funkcioniranja Mooreovog automata dan je jednadžbama:
a (t + 1) = (a (t), z (t)); w (t) = (a (t)), t = 0,1,2, ...
Usporedba zakona rada pokazuje da, za razliku od Mealyjevog automata, izlazni signal u Mooreovom automatu ovisi samo o trenutnom stanju automata i ne ovisi izričito o ulaznom signalu. Za potpunu dodjelu Mealy ili Moore automata, osim zakona rada, potrebno je naznačiti početno stanje i odrediti unutarnje, ulazno i izlazno pismo.
Osim automata Mealy i Moore, ponekad se pokaže prikladnim koristiti kombinirani model automata, takozvani C-automat.
Apstraktni C-automat može se predstaviti kao uređaj s jednim ulazom, koji prima signale iz ulazne abecede X, i dva izlaza, na kojima se pojavljuju signali iz abecede Y i U. Razlika između C-automata i Mealy i Mooreovi modeli su da istodobno implementira dvije funkcije izlaza 1 i 2, od kojih je svaki karakterističan za ove modele zasebno. Zakon funkcioniranja S-automata može se opisati sljedećim jednadžbama:
a (t + 1) = (a (t), z (t)); w (t) = 1 (a (t), z (t)); u (t) = 2 (a (t)); t = 0, 1, 2, ...
Izlazni signal U h = 2 (a m) emitira se cijelo vrijeme dok je automat u stanju a m. Izlazni signal Wg = 1 (a m, z f) izdaje se za vrijeme djelovanja ulaznog signala Z f kada je automat u stanju a m.
7 Metode za opisivanje i dodjeljivanje strojeva (predavanje broj 10)
Da bi se definirao automat, potrebno je opisati sve komponente torte S = (A, X, Y, , , a 1). Skupovi A, X, Y opisani su i specificirani jednostavnim nabrajanjem njihovih elemenata. Među mnoštvom različitih načina specificiranja funkcija i (pa stoga i cijelog automata u cjelini), tablični i grafički najrašireniji su.
7.1 Tablični način opisa digitalnih strojeva
U tabličnom načinu opisa digitalnih strojeva koriste se dvije vrste tablica - tablica skoka i tablica izlaza.
Skočni stol prikazuje prijelaznu funkciju. Linije tablice odgovaraju stanju automata, t.j. u tablici postoji onoliko redaka koliko ima stanja u stroju. Stupci tablice odgovaraju ulaznim vrijednostima koje mogu ići na ulaze DA -a, tj. stupac onoliko - koliko elemenata ima u ulaznoj abecedi. Na sjecištu i-stupca i j-retka u ćeliji tablice stanje u koje će CA ući pod utjecajem ulaznog signala xi (što odgovara i-tom stupcu) iz stanja aj (koje odgovara j-tom retku). Prijelazna tablica prikazana je na slici 6.2.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
a 2 |
a 1 |
… |
a 2 |
|
a 2 |
a n-1 |
a 3 |
… |
a 1 |
|
… |
… | |||
|
a n |
- |
a n |
… |
a 2 |
Slika 6.2 - Tablica CA prijelaza
Prijelazna tablica izgleda isto i za Moore i za Miles stroj. Za djelomične Mealy i Moore automate, crtica se stavlja na mjesto nedefiniranih stanja i izlaznih signala u tablicama koje se razmatraju. U takvim automatima izlazni signal pri svakom prijelazu uvijek je nedefiniran ako je prijelazno stanje nedefinirano
Izlazni stol za Stroj za milje ima isti oblik kao i prijelazna tablica, samo je na sjecištu i-stupca i j-retka u ćeliji tablice naznačena izlazna vrijednost koja će tvoriti CA pod utjecajem ulaznog signala xi (što odgovara i-ti stupac) u stanju aj (što odgovara j- i nizu). Tablica izlaza stroja Mealy prikazana je na slici 6.3.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
y 1 |
y 3 |
… |
y 1 |
|
a 2 |
y n-1 |
y 2 |
… |
y n-1 |
|
… |
… | |||
|
a n |
- |
y 1 |
… |
y 2 |
Slika 6.3 - Tablica izlaza stroja Miles
Izlazni stol za Mooreova jurišna puška sastoji se od jedne kolone. Linije tablice odgovaraju stanju automata, t.j. u tablici postoji onoliko redova koliko ima stanja u stroju. Primjer tablice prikazan je na slici 6.4.
|
x 1 |
|
|
a 1 |
y 1 |
|
a 2 |
y n-1 |
|
… | |
|
a n |
y 2 |
Slika 6.4 - Tablica Mooreovih automatiziranih izlaza
U nekim je slučajevima prikladno koristiti umjesto dvije tablice koje definiraju ciljanu publiku kombinirano tablica prijelaza i izlaza. Slika 6.5 prikazuje kombiniranu tablicu za stroj Mealy. Slika 6.6 prikazuje kombiniranu prijelaznu tablicu za Mooreov automat.
|
x 1 |
x 2 |
… |
x m |
|
|
a 1 |
a 2 / y 1 |
a 1 / y 3 |
… |
a 2 / y 1 |
|
a 2 |
a n-1 / y n-1 |
a 3 / y 2 |
… |
a 1 / y n-1 |
|
… |
… | |||
|
a n |
- |
a n / g 1 |
… |
a 2 / y 2 |
Slika 6.5 - Kombinirana tablica prijelaza i izlaza iz stroja Miles
|
x 1 |
x 2 |
… |
x m |
Y |
|
|
a 1 |
a 2 |
a 1 |
… |
a 2 |
y 2 |
|
a 2 |
a n-1 |
a 3 |
… |
a 1 |
y 1 |
|
… |
… | ||||
|
a n |
- |
a n |
… |
a 2 |
y 2 |
Slika 6.6 - Kombinirana Mooreova automatizirana prijelazna tablica
7.2 Grafički način postavljanja digitalnih strojeva
U grafičkoj metodi automat je naveden u obliku usmjerenog grafa, čiji vrhovi odgovaraju stanjima, a lukovi odgovaraju prijelazima između njih. Luk usmjeren od vrha a m definira prijelaz u automatu iz stanja a m u stanje a s. Na početku ovog luka upisuje se ulazni signal X f X, uzrokujući ovaj prijelaz a s = (a m, x f). Za grafikon Mealyjevog automata izlazni signal yg Y, generiran na prijelazu, zapisuje se na kraju luka, a za Mooreov automat - u blizini vrha am, označen stanjem am, u kojem je generirano. Ako se prijelaz u automatu iz stanja a m u stanje a s izvede pod djelovanjem više ulaznih signala, tada se svi ti ulazni i odgovarajući izlazni signali dodjeljuju luku grafikona usmjerenom od m do s. Grafikon C-automata sadrži izlazne signale dva tipa, a oni su označeni na grafikonu kao i na grafikonima odgovarajućih automata. Grafikon Mooreova automata prikazan je na slici 6.7, a Mealyjevog automata - na slici 6.8.
y 2
Slika 6.7 - Grafički prikaz Mooreovog automata
Slika 6.8 - Grafički prikaz stroja Miles
8 Sažetak sinteze digitalnih automata
Teorija digitalnih automata ispituje apstraktnu i strukturnu sintezu digitalnih automata. Apstraktna sinteza ne opisuje unutarnju strukturu automata, već daje opis interakcije s okoliš... Apstraktna sinteza uključuje:
definicija ulaza, izlaza i abecede stanja, funkcija prijelaza i izlaza;
dodjeljivanje grafikona stroja i tablica prijelaza i izlaza;
minimiziranje broja stanja
8.1 Struktura digitalnog stroja
Unutarnja struktura digitalnog stroja može se prikazati kao što je prikazano na slici 8.1.
Slika 8.1 - Blok dijagram digitalnog stroja.
Kombinirani krug # 1 provodi prijelaze stroja iz jednog stanja u drugo pod utjecajem ulaznih signala. Krug je projektiran na temelju kodirane prijelazne tablice i prijelaznog podgrafa odabranog memorijskog elementa.
Memorijski blok je skup japanki koje pohranjuju bitove kodiranog broja stanja. Broj okidača ovisi o broju stanja u kojima se automat može nalaziti. I izračunava se ovako:
N = log 2 M
gdje je M broj stanja, a N broj okidača
Kombinirani krug br. 2 ostvaruje funkciju izlaza stroja, a na izlazu se izlazne vrijednosti stroja postavljaju u skladu s Trenutna država automat i ulazne vrijednosti.
8.2 Minimiziranje broja stanja digitalnog stroja
Često se prilikom izvođenja apstraktne sinteze uvode suvišna stanja čija ekvivalentnost nije očita. Prevelik broj stanja može dovesti do korištenja nepotrebnih okidača, što će zakomplicirati KC1 i KC2. Stoga je vrlo važno provesti minimiziranje broja stanja prije njegove strukturne sinteze.
Algoritam minimizacije temelji se na cijepanju cijelog skupa stanja u parno nespojive klase ekvivalentnih stanja i zamjeni cijele klase ekvivalencije s jednim stanjem. Rezultirajući minimizirani automat sadržavat će onoliko stanja u koliko je klasa ekvivalencije podijeljen izvorni skup stanja.
Definicija
Dva stanja a s i a m su ekvivalentni ako
(a s , E) =
(a m , E), gdje
- prijelazna funkcija, E - ulazna riječ proizvoljne duljine.
Drugim riječima, stanja su ekvivalentna ako se, kao odgovor na iste ulazne riječi, generira isti slijed stanja, bez obzira na to koje od dva stanja a s ili a m postojao je automat u početnom trenutku. Ako su dva stanja ekvivalentna, onda se jedno stanje može zamijeniti drugim.
Osim ekvivalentnih stanja, postoji koncept k-ekvivalentnih stanja: 1-ekvivalentno, 2-ekvivalentno itd.
Definicija
Dva stanja a s i a m suk
-
ekvivalent ako
(a s , Ek) =
(a m , Ek), gdje
- prijelazna funkcija, Ek- ulazna riječ dužinek
.
Algoritam minimizacije:
Pregrade P 1, P 2, ... PK, PK + 1 stanja automata nalaze se uzastopno sve dok u nekom koraku K + 1 PK + 1 ne postane jednak P K. U tom slučaju rezultirajuća k-ekvivalentna particija će predstavljati potpuno ekvivalentne klase.
U svakoj klasi ekvivalencije bira se jedno stanje koje tvori novi skup stanja minimiziranog automata.
Kako bi se redefinirale funkcije prijelaza i izlaza, linije koje odgovaraju stanjima koja nisu uključena u novi skup stanja minimiziranog automata brišu se, a u ostalim redovima prijelazne tablice sva se stanja zamjenjuju svojim ekvivalentna stanja koja su ušla u novi skup.
Ako se skup sastoji od jednog stanja, onda nema ekvivalentnih stanja. Ako sva stanja ulaze u zasebne skupove iz jednog stanja, tada je automat ne može se minimizirati.
Particioniranje počinje klasom ekvivalentnom 0. U tom slučaju stanja s istim izlaznim signalima spadaju u iste skupove.
Imajući jedan ulaz, jedan izlaz i u svakom trenutku vremena je u jednom stanju od mnogih mogućih. Ulaz u ovaj uređaj prima simbole jedne abecede, na izlazu emitira simbole (u općenitom slučaju) druge abecede.
Formalno, apstraktni automat definiran je kao petica
Ograničenje broja parametara apstraktnog automata definiralo je takav koncept kao konačni automat.
Rad automata sastoji se u generiranju dva niza: slijeda uzastopnih stanja automata i nizovi izlaznih znakova , što za niz znakova odvijaju se u trenucima diskretnog vremena t = 1, 2, 3, ... Momente diskretnog vremena nazivamo krpeljima.
Rad automata u diskretnim trenucima vremena t može se opisati sustavom ponavljajućih odnosa:
Kako bi se pojasnila svojstva apstraktnih automata, uvedena je klasifikacija.
Sažeti automati tvore temeljnu klasu diskretnih modela kao neovisni model i kao glavna komponenta Turingovih strojeva, FFS strojeva, strojeva konačnih stanja i drugih pretvarača informacija.
Napišite recenziju članka "Apstraktni automat"
Odlomak koji karakterizira apstraktni automat
Car se s osmijehom okrenuo prema jednoj svojoj pratnji, pokazujući na dobre drugove Apšerona, i rekao mu nešto.Kutuzov je u pratnji svojih pobočnika korak po korak slijedio karabinjere.
Prošavši oko pola milje u repu kolone, zaustavio se u usamljenoj napuštenoj kući (vjerojatno bivšoj gostionici) u blizini račvanja na dvije ceste. Obje su ceste krenule nizbrdo, a trupe su išle uz obje.
Magla se počela razilaziti, pa se neodređeno vrijeme, dvije milje dalje, neprijateljske trupe mogle vidjeti na suprotnim visinama. U donjem lijevom kutu pucnjava je postajala sve glasnija. Kutuzov je prestao razgovarati s austrijskim generalom. Princ Andrew, koji je stajao nešto straga, zavirio je u njih i, želeći zatražiti od ađutanta teleskop, okrenuo se prema njemu.
"Gle, gle", rekao je ovaj ađutant, ne gledajući u daleku vojsku, već niz planinu ispred sebe. - Ovo su Francuzi!
Dva generala i ađutanti počeli su hvatati cijev, povlačeći je jedan od drugog. Sva su se lica odjednom promijenila, a na svima je izražen užas. Francuzi su trebali biti udaljeni dvije milje od nas, ali su se iznenada, neočekivano pojavili ispred nas.
- Je li ovo neprijatelj? ... Ne! ... Da, vidi, on ... vjerojatno ... Što je ovo? - začuli su se glasovi.
Princ Andrey svojim je jednostavnim okom ugledao debelu kolonu Francuza kako se diže u susret s Abšeronima dolje desno, ne više od petsto koraka od mjesta gdje je stajao Kutuzov.
“Evo ga, došao je odlučujući trenutak! Došlo mi je ”, pomislio je princ Andrew i udario u konja odvezavši se do Kutuzova. "Moramo zaustaviti Abšerone", povikao je, "vaša ekselencijo!" Ali u istom trenutku sve je bilo prekriveno dimom, začula se bliska pucnjava, a naivno uplašen glas dva koraka od princa Andreya povikao je: "Pa, braćo, subota!" I kao da je ovaj glas naredba. Na taj glas sve je krenulo.
Mješovita, sve veća gomila pobjegla je natrag na mjesto gdje su prije pet minuta trupe prošle pokraj careva. Ne samo da je bilo teško zaustaviti ovu gomilu, nego je bilo nemoguće ne vratiti se zajedno s gomilom.
Bolkonski je samo pokušavao držati korak s njom i gledao je oko sebe, zbunjen i nesposoban razumjeti što se radi pred njim. Nesvitsky, ogorčenog pogleda, crven i ne nalikuje sebi, viknuo je Kutuzovu da će, ako sada ne ode, vjerojatno biti zarobljen. Kutuzov je stajao na istom mjestu i, bez odgovora, izvadio rupčić. Krv mu je tekla iz obraza. Princ Andrew progurao se do njega.
- Jeste li ozlijeđeni? - upitao je, jedva držeći vilicu da drhti.
- Rane nisu ovdje, nego gdje! - rekao je Kutuzov, pritisnuvši rupčić na ranjeni obraz i pokazao prema bježanju. - Zaustavite ih! - povikao je i u isto vrijeme, vjerojatno pazeći da ih je nemoguće zaustaviti, udario konja i odjahao desno.
Samostalno proučavanje sklopova. Apstraktni automat. 2. dio
- Elektronika za početnike
Članak je napisan, prikupljen i složen. Hvala vam puno.
U prethodnom sam članku pokušao izložiti sve osnovne definicije i načela kako bi ovaj članak bio što jasniji. Sve se nije uklapalo, pa vam toplo savjetujem da se upoznate s ovim datotekama:
Osnova, Osnova2, Minimiziranje. Kasnije u ovom članku ostavio sam neke objašnjenja u kurzivu.
U ovom članku ću pokušati objasniti pristupačan jezikšto je apstraktni automat, načini njegovog predstavljanja. Budući da je teorija automata puna matematike i složena, pokušat ću pisati ljudskim jezikom kako bi nespremni čitatelj mogao razumjeti o čemu je riječ.
Elektronički digitalni sklopovi mogu se formalno podijeliti u 2 klase:
- Kombinirane sheme (CC) - nemaju memoriju. Izlazni signal se formira ovisno o kombinacije ulazni podaci u fiksnom trenutku (uzimajući u obzir kašnjenje pretvorbe signala) Kombinirani krugovi, njihovi tipovi i principi konstrukcije mogu biti tema za zasebni članak, a kao primjeri: Kontrolirane sabirnice, multiplekseri i demultiplekseri, dekoderi i koderi, pretvarači kodova, kombinirani brojači i sabirači itd.
- Memorijski krugovi - algoritam njihova rada ovisi o stanju ulaza i memorija(ono što je bilo u prethodnim trenucima u vremenu). Ove su sheme opisane pomoću teorije konačnih automata. O njima ćemo dalje govoriti.
Apstraktni automat
Stroj će morati implementirati neke funkcije koje je naveo programer. To može biti jednostavno zbrajanje, može implementirati bilo koju mikroinstrukciju procesora, odabrati riječi iz RAM -a ili raščlaniti izraz.Općenito, bez ulaženja u detalje, apstraktni se automat može predstaviti na sljedeći način:
Ili, ako idemo od ilustracije do matematičkog opisa:
A =
Legenda:
- Skup (A) - skup je vrijednosti na fizičkim ulazima stroja. Na ulazu će u našem slučaju biti neki slijed visokih i niskih naponskih razina, koji će kodirati logičke nule i jedinice.
- Skup (B) - skup je vrijednosti na fizičkim izlazima stroja.
- Skup (C) - a skup koji predstavlja unutarnje stanje stroja je memorija. U budućnosti će C0 označavati početno stanje automata.
- δ = X × Z → Z su prijelazne funkcije automata, one jednoznačno određuju stanje ai u koje automat prelazi iz stanja aj.
- λ = X × Z → Y su izlazne funkcije, one određuju što je na izlazu stroja ovisno o ulazima i unutarnjem stanju.
Takav automat djeluje diskretno u vremenu, odnosno vrijednosti ulaza, izlaza i unutarnjeg stanja automata mijenjaju se u diskretnim vremenima.
Dakle, općenito smo opisali što je apstraktni automat. Primjer takvog automata može biti japanka, računalni registar ili zbrajalica.
Postoje 2 vrste strojeva:
- Miles Automata. Opisano sustavom jednadžbi:
c (t) = δ (a (t), c (t-1));
b (t) = λ (a (t), c (t-1)). - Mooreovi automati. Opisano jednadžbama:
c (t) = δ (a (t), c (t-1));
b (t) = λ (a (t), c (t)).
Strojevi se razlikuju po vrsti izlazne funkcije. U stroju Mealy izlazni signal određen je ulaznim signalom a (t) i stanjem stroja u prethodnom vremenu c (t-1). Izlazni signal Mooreovog automata određen je parom ulaznog signala a (t) i stanjem u trenutku c (t).
Također se može primijetiti da se može preći s jednog tipa na drugi i obrnuto, a pri prelasku s Mealyjevog automata na Mooreov broj, unutarnja stanja automata ostat će ista, a tijekom obrnutog prijelaza, može se povećati broj unutarnjih stanja. Nećemo se na ovome detaljno zadržavati, pod pretpostavkom da smo sintetizirali (nacrtali grafikon) automat potrebne vrste.
Dakle, ovo je gotovo s materijalom. Pokušajmo opisati strojeve.
Oni. automat tipa Mealy generira izlazni signal kad se njegov ulaz promijeni, ovisno o prethodnom stanju. U tom slučaju trajanje izlaznog signala ne ovisi o trajanju ulaznog signala, već samo o njegovoj prisutnosti. U strojevima tipa Moore izlazni signal ovisi o stanju stroja u trenutnom vremenu, tj. stroj će generirati određeni izlazni signal sve dok ne promijeni svoje stanje.
Metode definiranja automata
Kako smo otkrili u prvom dijelu, automat je zbirka ulaznih i izlaznih abeceda, skup unutarnjih stanja i funkcija koje određuju prijelaze i izlaze. Međutim, obično funkcije δ i λ nisu specificirane, pa se ponašanje automata mora opisati na drugačiji način.Postoje dva glavna načina definiranja automata:
- Korištenje grafikona.
- Uz pomoć prijelaznih tablica i izlaza.
Grafovi
Graf automata je usmjereni povezani graf čiji vrhovi simboliziraju unutarnja stanja automata, a lukovi predstavljaju prijelaze iz jednog stanja u drugo.
Za grafikon Miles slična i izlazna slova označena su lukovima. Izlazna slova ispisana su iznad lukova, simbolizirajući činjenicu da izlazno stanje ovisi o stanju automata u prethodnom trenutku.
Za grafikon Mooreovog automata samo su ulazna slova napisana na lukovima, dok su izlazi naznačeni u blizini vrhova.
Važna točka: Ako iz svakog vrha izađe onoliko lukova koliko ima ulaznih slova, tada se naziva automat potpuna... Drugim riječima, ako su prijelazi definirani iz svakog vrha za svako slovo unosa. U našim primjerima stroj Kilometri su kompletni, i stroj Moore - djelomičan.
I još nešto: Ako iz jednog vrha izlazi više lukova nego ulaznih slova (to jest 2 ili više lukova s istim ulaznim slovima), tada se takav automat naziva neodređen... To se može dogoditi prilikom izrade formaliziranog opisa i tada će biti potrebno napraviti prijelaz na deterministički automatski stroj, ali to se ne može uvijek učiniti. Također izostavljam opis ovog procesa, odmah povlačeći deterministički automat.
To je sve o grafikonima.
Tablice prijelaza i izlaza.
Grafovi su jasniji za ljude, a tablice za strojeve. Svaki automat može se prikazati kao tablica prijelaza i izlaza (TPV). U TPV -u redovi su unutarnja stanja automata, a stupci su ulazna slova.Izgradimo TPV za naše Miles i Mooreove grafikone. Ako nije definirano ulazno ili izlazno slovo, umjesto toga se umeće crtica. Ako nije navedeno stanje, vrijedi isto jednostavno pravilo.
TPV Earl Miles
U TPV miljama prijelazi i izlazi bilježe se u svakoj ćeliji. Na primjer, ako je automat u stanju C0 i slovo a1 stigne na ulaz, tada će otići u stanje C1, a slovo b3 će se pojaviti na izlazu.
TPV grofa Moorea
Za grofa Moorea izgrađena je označena tablica za preskakanje. Dodatni stupac dodijeljen je izlaznim slovima.U ćeliji ispod ulaznog slova napisano je u koje stanje automat prolazi, u krajnjoj desnoj ćeliji - koje izlazno slovo vraća.
Primjer sinteze automata
Gotovo se sve može opisati apstraktnim automatima. Možete opisati rad digitalnog sklopa ili sintaksički ili leksički analizator. Pokušajmo opisati okidač - nije li to automat?Za postavljanje grafikona potreban vam je usmeni opis algoritma okidača. Mi čitamo:
Kodiramo ulazne i izlazne abecede:
A = (a0, a1), gdje je a0 logička 1 na ulazu R, a1 je logička na ulazu S.
B = (b0, b1), gdje je b0 logička 0 na izlazu Q, b1 je logička na izlazu Q
Gradimo grafikon Miles automata: 
Evo smiješne Čeburaške ispalo je :-). Sada možete sastaviti tablicu prijelaza i izlaza: 
Ako ovu tablicu oslikamo pretvaranjem legende u stvarnu, tada dobivamo tablicu koja je prijelazna tablica okidača. Tada se to može pojednostaviti: 
Primijenimo rezultirajuću funkciju na Weichovu kartu i smanjimo:
Zapišimo što se dogodilo: 
Izrađujemo shemu prema funkciji (Jeste li učinili domaću zadaću?).
