Prema načinu formiranja izlazne funkcije razlikuju se tri tipa apstraktnih automata: Mealyjev automat, Mooreov automat, C-automat. Mealy mašinu karakteriše sistem jednačina:
y (t) =(a (t), x (t));
a (t+1) = δ (a (t), x (t)). (1-1)
Moorov automat - sistem jednačina:
a (t+1) = δ (a (t), x (t)). (1-2)
C-automatski - sistem jednadžbi:
y 1 (t) =(a (t),x (t));
Y 2 (t) = 2 (a (t));
a (t+1) =δ (a (t),x (t)).
Proizvoljni apstraktni Mealy ili Moore 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 Apstraktni C-automat
Ako je ulaz apstraktnog Mealy ili Moore automata, postavljen na početno stanje a o, snabdjeven slovo po slovo određenim nizom slova ulazne abecede x (0), x (1),. je ulazna riječ, tada će se na izlazu mašine redom pojaviti slova izlazne abecede y (0), y (1). - izlazna riječ. Za slučaj C-automata, dvije sekvence će se pojaviti 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 sve vrijeme dok je automat u stanju a (t). Izlazni signal y 1 (t) =λ 1 (a (t),x (t)) se izdaje za vrijeme djelovanja ulaznog signala x (t) kada je C-automat u stanju a (t).
Dakle, na nivou apstraktne teorije, funkcionisanje digitalne mašine se shvata kao transformacija ulaznih reči u izlazne reči.
Postoje potpuno definisani i parcijalni automati.
Potpuno definiran apstraktni digitalni automat je onaj čija su prijelazna funkcija ili izlazna funkcija, ili obje ove funkcije, definirane za sve parove prijelaza (x i ,a j).
Apstraktni digitalni automat naziva se parcijalni ako njegova prijelazna funkcija ili izlazna funkcija, ili obje ove funkcije nisu definirane za sve parove prijelaza (x i ,a j).
Apstraktni digitalni automat naziva se početnim ako se početno stanje a o razlikuje na skupu njegovih stanja A.
1.3 Metode za specificiranje apstraktnih automata
Da bi se definisao konačni automat S, potrebno je opisati sve elemente skupa: S=( X,A,Y,,,a o ). Postoji nekoliko načina da se specificira rad mašine, ali najčešće se koriste tabelarni (matrični), grafički i analitički.
U tabelarnoj metodi, stroj je specificiran pomoću dvije tablice: prijelazne tablice i izlazne tablice ili matrice povezivanja. Prelazna tabela proizvoljnog potpuno definisanog automata konstruisana je na sledeći način: redovi tabele su označeni slovima ulazne abecede automata, a kolone tabele su označene slovima abecede stanja automata. automat; U ćeliji prelazne tablice nalazi se na Na preseku reda označenog ulaznim signalom x i i kolone označene stanjem a j, postavlja se stanje a k, koje je rezultat prelaska mašine iz stanja a j pod uticajem ulaznog signala x i, koji je određen izrazom a k = (a j, x j).
Tabela 1.1 Tabela prelaza automata
|
države | ||||
|
ulazni signali |
||||
|
(a k, x j) |
Primer popunjavanja prelazne tabele nekog apstraktnog potpuno definisanog automata sa ulaznim alfabetom X = (x 1, x 2) - i abecedom stanja A = (a 1, a 2, a 3) prikazan je u tabeli 1.2. .
Tabela 1.2
Ako je apstraktni automat parcijalan, tada se u ćeliji njegove prijelazne tablice nalazi na sjecištu reda označenog ulaznim signalom i stupca označenog odgovarajućim stanjem (pod uvjetom da se prijelaz u ovo stanje pod utjecajem ovog ulaznog signala nije definirano), stavlja se crtica, a svaka ulazna riječ koja vodi do navedenog prijelaza je nezakonita.
Popunjavanje preostalih ćelija slično je slučaju potpuno definiranog automata. Tip prelazne tablice ne zavisi od tipa mašine koja se specificira (Mili, Moore, S-automat). Tabele izlaza Mealy, Moore i S-automata imaju razlike.
Izlazna tabela potpuno definisanog Mealy automata je konstruisana na sledeći način: identifikacija kolona i redova, kao i format tabele, odgovaraju prelaznoj tabeli potpuno definisanog automata. U ćeliju izlazne tabele koja se nalazi na preseku reda označenog ulaznim signalom X j i kolone označene stanjem a k, smešten je izlazni signal Y m, koji mašina proizvodi dok je u stanju a k u prisustvu ulaznog signala Xj, koji je određen izrazom Ym = (a k, x j).
Tabela 1.3 Tabela izlaza apstraktnog Mealy automata.
|
države | ||||
|
Ulazni signali |
||||
Primjer popunjavanja izlazne tablice nekog apstraktnog potpuno definiranog automata sa ulaznim alfabetom X=(x 1, x 2), abecedom stanja A=(a 1, a 2, a 3) i izlaznom abecedom Y=(y 1, y) 2 , y 3 ) - prikazano u tabeli 1.4.
Tabela 1.4
Očigledno, apstraktni potpuno definiran C-automat je dat sa dvije izlazne tablice, od kojih je prva izlazna tablica Mealyjevog automata, a druga je Moore automat. Ako je stroj djelomičan, tada u nekim ćelijama njegove tablice može biti crtica, što znači odsustvo izlaznog signala.
U praksi se prelazne i izlazne tabele često kombinuju u jednu tabelu, nazvanu označena prelazna tabela mašine. Primjeri označenih prijelaznih tabela prikazani su u tabeli 1.6. - 1.8 (Opšti prikaz označene prelazne tabele - tabela 1.6., označena prelazna tabela Milijevog automata - tabela 1.7., označena prelazna tabela Mooreovog automata - tabela 1.8.).
Kao dodatak prijelaznim i izlaznim tablicama o kojima smo gore govorili, proizvoljni apstraktni automat može se specificirati pomoću matrice povezivanja.
Matrica povezivanja je kvadratna i sadrži onoliko kolona (redova) koliko različitih stanja sadrži abeceda stanja datog automata. Svaki stupac (red) matrice veze označen je slovom stanja mašine. U ćeliji koja se nalazi na raskrsnici kolone označene slovom a j i reda označenog slovom a s automata, postavlja se ulazni signal (ili disjunkcija ulaznih signala) pod čijim se utjecajem vrši ovaj prijelaz .
Za apstraktni Mealyjev automat, izlazni signal koji automat proizvodi kao rezultat ovog prijelaza također se stavlja u ćeliju pored stanja (Tabela 1.9.) Za Mooreov automat, izlazni signal se unosi u red pored stanje (ova stanja odgovaraju početnim stanjima automata).
Tabela 1.6
|
države | ||||
|
Ulazni signali |
||||
|
(a 2 , x j) |
(a k, x j) |
|||
|
(a 2 , x j) |
(a k, x j) |
Tabela 1.7
Tabela 1.9.
U grafičkoj metodi specificiranja, apstraktni automati su predstavljeni usmjerenim grafovima. Graf automata je usmjereni povezani graf čiji vrhovi odgovaraju stanjima automata, a lukovi između njih odgovaraju prijelazima između stanja. Dva vrha a k i a s povezana su lukom ako automat ima prijelaz iz stanja a k u stanje a s. Za Mealyjev automat, ulazni i izlazni signali se postavljaju na luk koji odgovara datom prijelazu (slika 1.3. za Moore automat, ulazni signal se postavlja na luk, a izlazni signal se nalazi pored); vrh koji odgovara stanju (slika 1.4.).
Ovdje razmatramo samo determinističke automate za koje je zadovoljen uslov nedvosmislenih prijelaza: automat koji je u određenom stanju ne može prijeći u više od jednog stanja pod utjecajem bilo kojeg ulaznog signala. U odnosu na grafičku metodu specificiranja automata, to znači da u grafu automata dva ili više lukova označenih istim ulaznim signalom ne mogu izaći iz bilo kojeg vrha.
|
|
|
Slika 1.3-Grafikon Mealy mašine Slika 1.4-Grafikon Moore mašine
U analitičkoj metodi specificiranja, apstraktni automati su definisani sa četiri objekta:
S=( X, A, Y, F), gdje F specificira za svako stanje a j automata preslikavanje (XxA) - > (AxY). Drugim riječima, analitičkom metodom specificiranja za svako stanje automata a j, naznačeno je preslikavanje F ai, koje je skup svih trojki a p, x m, y k, i takvo da pod utjecajem ulaznog signala x m automatske tranzicije iz stanja A j V stanje a p, dok proizvodi izlazni signal y k.
U odnosu na opštu definiciju apstraktnog automata, ovo drugo je ekvivalentno opisivanju funkcija δ i λ u skladu sa izrazom: a p = δ (a i, x m), y k = λ (a i, x m).
Preslikavanje F ai se piše na sljedeći način:
F ai (a p (X m /y k),a i (X f /y z) ...).
Za apstraktni Mealyjev automat (tabela 1.7.), analitički zadatak ima sljedeći oblik:
S=( X,A,Y,F), X=(x 1 ,x 2 ), A=(a 1 , a 2 , a 3 ), Y=(y 1 , y 2 , y 3 ),
F a1 =(a 2 (x 1 /y 2), a 1 (x 2 /y 3) ),
F a 2 = (a 3 (x 1 /y 3), a 1 (x 2 /y 1) ),
F a 3 = (a 1 (x 1 /y 3), a 2 (x 2 /y 2) ).
Treba napomenuti da je funkcija F ai uvijek napisana za početno stanje.
Definirajmo sinhrone i asinhrone automate. Stanje a s automata S naziva se stabilnim stanjem ako za bilo koji ulazni signal x j X takav da je s = δ (a i X m) vrijedi s = δ (a s , x m).
Automat S se naziva asinhronim ako je svako njegovo stanje a s A stabilno. Automat S se naziva sinhroni ako nije asinhroni.
Treba napomenuti da su automati izgrađeni u praksi uvijek asinhroni i stabilnost njihovih stanja se uvijek osigurava na ovaj ili onaj način, na primjer, uvođenjem signala sinhronizacije. Međutim, na nivou apstraktne teorije automata, kada je automat samo matematički model koji ne odražava mnoge specifične karakteristike njegove implementacije, često se ispostavi da je pogodnije raditi sa sinhronim automatima.
6 Osnovni pojmovi i definicije teorije apstraktnih automata (predavanje br. 9)
Digitalna (diskretna) automatska mašina (DA) je uređaj koji prima, pohranjuje i/ili pretvara diskretne informacije prema određenom algoritmu. Primjeri ciljne publike uključuju žive organizme, procesore, kućanske aparate, kalkulatore - to su pravi uređaji, a postoje i apstraktni, na primjer, modeli algoritama. TA pripada serijski uređaji. Ova klasa uređaja određena je činjenicom da vrijednost izlaza ovisi ne samo o ulaznim vrijednostima, već i o trenutnom stanju uređaja. One. koncept je uveden - stanje. Kako bi se pohranili podaci o stanju u kojem se uređaj nalazi, u ciljnoj publici koriste se elementi za pohranu – okidači.
6.1 Matematički model digitalne mašine
Digitalna mašina je uređaj koji karakteriše skup unutrašnjih stanja u koja će pasti pod uticajem komandi programa koji je u nju ugrađen. Prijelaz automata iz jednog stanja u drugo događa se u određenom trenutku.
Matematički model ciljne publike (i u općenitom slučaju bilo kojeg diskretnog uređaja) je takozvani apstraktni automat, definiran kao 6-komponentni tuple: S=(A,X,Y,,,a 1) koji ima:
A=(a 1 , a 2 , ... ,a m ) – abeceda stanja – skup stanja u kojima se projektovani digitalni automat može nalaziti. Broj država igra važnu ulogu u implementaciji CA. Što je više stanja, potrebno je više elemenata za pohranu (okidača) za izgradnju ciljne publike.
X=(x 1 , x 2 , ... ,x f ) – abeceda ulaznih vrijednosti – skup vrijednosti koji se može unijeti ciljnoj publici. Na primjer, ako mašina ima dvocifreni binarni ulaz, tada elementi abecede mogu biti 00, 01, 10 i 11.
Y=(y 1, y 2, ..., y g) – abeceda izlaznih vrijednosti – skup vrijednosti koji se može postaviti na izlazu ciljne publike.
: AXA – prelazna funkcija a(t+1)= (x(t),a(t)). Prijelazna funkcija određuje koje stanje a(t+1) mašina će se kretati pod uticajem ulaznog signala x(t), ako je u trenutnom trenutku mašina u stanju a(t).
: AZW – izlazna funkcija y(t)= (a(t), x(t)). Funkcija izlaza određuje koja izlazna vrijednost y(t) će se postaviti na izlazu stroja ovisno o ulaznoj vrijednosti x(t) i trenutno stanje a(t) .
a i A - početno stanje mašine - stanje u koje je DA instaliran nakon uključivanja napajanja ili nakon resetovanja
Slika 6.1 – Apstraktni automat
Apstraktni automat (slika 6.1) ima jedan ulaz i jedan izlaz. Automat radi u diskretnom vremenu, uzimajući nenegativne 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, u stanju a(t), automat je u stanju da percipira slovo ulaznog alfabeta X(t) kao ulaz Z. U skladu s izlaznom funkcijom, on će istovremeno proizvesti t slovo izlazne abecede y(t)=(a(t), z(t)) i, u skladu s prijelaznom funkcijom, prijeći u sljedeće stanje a(t+1)=, a(t) A, y(t) Y.
Značenje koncepta apstraktnog automata je da implementira neko mapiranje iz skupa riječi ulaznog alfabeta X u skup riječi izlaznog alfabeta Y. To jest, ako je ulaz automata, postavljen u početno stanje a1, snabdjeven slovo po slovo sa određenim nizom slova ulazne abecede x(0), x(1),... - ulazna riječ, onda slova izlazne abecede y(0) će se pojaviti sekvencijalno na izlazu automata ), y(1),... je izlazna riječ. To. izlazna riječ = (ulazna riječ), gdje je preslikavanje izvršeno od strane apstraktnog automata.
Na nivou apstraktne teorije, koncept „operacije automata“ shvata se kao transformacija ulaznih reči u izlazne reči. Možemo reći da u apstraktnom automatu apstrahujemo od njegove strukture – sadržaja pravougaonika (slika 6.1), smatrajući ga „crnom kutijom“, tj. Fokusiramo se na ponašanje mašine u odnosu na spoljašnje okruženje.
Koncept stanja u definiciji automata uveden je zbog činjenice da se često javlja potreba da se opiše ponašanje sistema čiji izlazi zavise ne samo od stanja ulaza u datom trenutku, već i od neke praistorije, tj. od signala koji su ranije stigli na sistemske ulaze. Stanja tačno odgovaraju nekom sjećanju prošlosti, dozvoljavajući da se vrijeme eliminira kao eksplicitna varijabla i da se izlazni signal izrazi kao funkcija stanja i ulaza u datom trenutku.
6.2 Klasifikacija digitalnih mašina
Apstraktni automati o kojima smo gore govorili mogu se podijeliti na:
potpuno definisano i djelomično;
deterministički i probabilistički;
sinhroni i asinhroni;
Djelomično je apstraktni automat čija prijelazna funkcija ili izlazna funkcija, ili obje ove funkcije nisu definirane za sve parove (a i, z j).
TO deterministički To uključuje automate za koje je zadovoljen uslov nedvosmislenih prijelaza: automat koji se nalazi u određenom stanju a i ne može prijeći u više od jednog stanja pod utjecajem bilo kojeg ulaznog signala z j.
Inače će biti probabilistički automat , u kojem je, za dato stanje a i i dati ulazni signal z j, moguć prijelaz sa datom vjerovatnoćom u različita stanja.
Za utvrđivanje sinhroni i asinhroni uvodi se koncept automata Stabilno stanje . Stanje a s automata naziva se stabilnim ako za bilo koje stanje a i i ulazni signal z j takve da je (a i , z j) = a s imamo (a s , z j) = a s, tj. stanje je stabilno ako, ušavši u ovo stanje pod uticajem nekog signala zj, automat ga napusti samo pod uticajem drugog signala zk, različitog od zj.
Automat u kojem su sva stanja stabilna - asinhroni .
Mašina se zove sinhroni , ako nije asinhrona.
Apstraktni automat se zove final
, ako su skupovi A = (a 1 , a 2 , ..., a m ) konačni, Z = (z 1 , z 2 , ..., z f ), W = (w 1 , w 2 , ... , w g ). Ime mašine je početni
, ako je u njemu odabrano početno stanje a 1.
6.3 Vrste digitalnih mašina
U praksi se najviše koriste dvije klase mašina - Mealy i Moore mašine.
Zakon rada Mealy mašine je dat jednadžbama:
a(t+1) = (a(t), z(t)); w(t) = (a(t), z(t)), t = 0,1,2,...
Zakon rada Moore mašine je dat jednadžbama:
a(t+1)=(a(t), z(t)); w(t) = (a(t)), t = 0,1,2,...
Iz poređenja zakona rada jasno je da, za razliku od Mealyjevog automata, izlazni signal kod Mooreovog automata zavisi samo od trenutnog stanja automata i ne zavisi eksplicitno od ulaznog signala. Da bi se u potpunosti specificirao Mealy ili Moore automat, pored zakona rada, potrebno je naznačiti početno stanje i definirati internu, ulaznu i izlaznu abecedu.
Uz Mealy i Moore automate, ponekad je zgodno koristiti i kombinovani model automata, takozvani C-automat.
Apstraktni C-automat se može predstaviti kao uređaj sa jednim ulazom, koji prima signale sa ulaznog alfabeta X, i dva izlaza, na kojima se pojavljuju signali iz abecede Y i U. Razlika između C-automata i Mealy-ja Moore model je u tome što istovremeno implementira dvije izlazne funkcije 1 i 2, od kojih je svaka karakteristična za ove modele posebno. Zakon o radu C-mašine 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) se emituje sve vreme dok je mašina u stanju a m. Izlazni signal Wg= 1 (a m , z f) se emituje tokom dejstva ulaznog signala Z f kada je mašina u stanju a m.
7 Metode opisivanja i specificiranja automata (predavanje br. 10)
Da bi se definirao automat, potrebno je opisati sve komponente skupa S=(A, X, Y, , , a 1). Skupovi A, X, Y su opisani i specificirani jednostavnim popisom njihovih elemenata. Među mnoštvom različitih metoda za specifikaciju funkcija i (a samim tim i cijele mašine u cjelini), najčešće se koriste tabelarne i grafičke.
7.1 Tabelarno opisivanje digitalnih mašina
U tabelarnoj metodi opisivanja digitalnih mašina koriste se dve vrste tabela - prelazna i izlazna tabela.
Prijelazni stol prikazuje funkciju prijelaza. Redovi tabele odgovaraju stanjima mašine, tj. U tabeli ima onoliko redova koliko ima stanja mašine. Kolone tabele odgovaraju ulaznim vrednostima koje se mogu dostaviti ulazima ciljne publike, tj. onoliko kolona koliko ima elemenata u ulaznoj abecedi. Na preseku i-kolone i j-reda u ćeliji tabele, stanje u koje će ciljna publika doći pod uticajem ulaznog signala x i (kojemu odgovara i-ta kolona) iz stanja a j (do kojoj odgovara j-ti red) je naznačeno. Tabela prijelaza je prikazana 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 – Tabela tranzicije cilja
Prijelazna tablica ima isti oblik i za Mooreov i za Mealyjev automat. Za delimične Mealy i Moore automate u razmatranim tabelama, crtica se stavlja na mesto nedefinisanih stanja i izlaznih signala. U takvim mašinama, izlazni signal na bilo kojoj tranziciji je uvijek nedefiniran ako je stanje prijelaza nedefinirano
Tabela izlaza Za Mili mašina ima isti oblik kao i prelazna tabela, samo na preseku i-kolone i j-reda u ćeliji tabele je naznačena izlazna vrednost koja će formirati ciljnu publiku pod uticajem ulaznog signala x i (na koji se i-ta kolona odgovara) u stanju a j (kome je j- I string). Tabela izlaza Mealy mašine je prikazana 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 – Tabela izlaza Mili mašine
Tabela izlaza Za Moore mitraljez sastoji se od jedne kolone. Redovi tabele odgovaraju stanjima mašine, tj. U tabeli ima onoliko redova koliko ima stanja mašine. Primjer tabele prikazan je na slici 6.4
|
x 1 |
|
|
a 1 |
y 1 |
|
a 2 |
y n-1 |
|
… | |
|
a n |
y 2 |
Slika 6.4 – Tabela izlaza Moore mašine
U nekim slučajevima, umjesto dvije tabele koje definiraju ciljnu publiku, zgodno je koristiti kombinovano tabela prelaza i izlaza. Slika 6.5 prikazuje kombinovanu tabelu za Mealy mašinu. Slika 6.6 prikazuje kombinovanu prelaznu tabelu za Moore mašinu.
|
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 /y 1 |
… |
a 2 /y 2 |
Slika 6.5 – Kombinovana tabela prelaza i izlaza Mealy mašine
|
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 – Kombinovana prelazna tabela Moore mašine
7.2 Grafička metoda specificiranja digitalnih mašina
U grafičkoj metodi, automat je specificiran u obliku usmjerenog grafa, čiji vrhovi odgovaraju stanjima, a lukovi odgovaraju prijelazima između njih. Luk usmjeren od vrha a m specificira prijelaz u automatu iz stanja a m u stanje a s. Na početku ovog luka snima se ulazni signal X f X, uzrokujući ovaj prijelaz a s =(a m ,x f). Za Mealyjev graf automata, izlazni signal y g Y generiran na prijelazu snima se na kraju luka, a za Mooreov automat - pored temena a m, označenog stanjem a m u kojem je formiran. Ako se prijelaz u automatu iz stanja am u stanje a s izvrši pod utjecajem više ulaznih signala, tada se svim tim ulaznim i odgovarajućim izlaznim signalima dodjeljuje luk grafa usmjeren od am do a s. Graf C-automata sadrži izlazne signale dva tipa i oni su na grafu označeni kao na grafovima odgovarajućih automata. Grafikon Mooreovog automata prikazan je na slici 6.7, a Mealyjevog automata na slici 6.8.
y 2
Slika 6.7 – Grafički prikaz Moore mašine
Slika 6.8 – Grafički prikaz Mili mašine
8 Apstraktna sinteza digitalnih automata
Teorija digitalnih automata razmatra apstraktnu i strukturnu sintezu digitalnih automata. Apstraktna sinteza ne opisuje unutrašnju strukturu automata, već daje opis interakcije sa okolinom. Apstraktna sinteza uključuje:
definicija ulaza, izlaza i abecede stanja, funkcije prijelaza i izlaza;
specificiranje automatskih grafova i tabela prelaza i izlaza;
minimiziranje broja država
8.1 Struktura digitalne mašine
Unutrašnja struktura digitalne mašine može se prikazati kao što je prikazano na slici 8.1.
Slika 8.1 – Blok dijagram digitalne mašine.
Kombinovano kolo br. 1 realizuje prelaze mašine iz jednog stanja u drugo pod uticajem ulaznih signala. Kolo je dizajnirano na osnovu kodirane prijelazne tablice i prijelaznog podgrafa odabranog skladišnog elementa.
Memorijski blok je skup flip-flopova koji pohranjuju bitove kodiranog broja stanja. Broj okidača zavisi od broja stanja u kojima mašina može biti. I izračunava se kao:
N=log 2 M
gdje je M broj stanja, a N broj okidača
Kombinovano kolo br. 2 implementira funkciju izlaza mašine i na njegovom izlazu se izlazne vrednosti mašine postavljaju u skladu sa trenutnim stanjem mašine i ulaznim vrednostima.
8.2 Minimiziranje broja stanja digitalne mašine
Često se prilikom izvođenja apstraktne sinteze uvode redundantna stanja čija ekvivalencija nije očigledna. Prevelik broj stanja može dovesti do upotrebe nepotrebnih okidača, što će zakomplikovati CS1 i CS2. Stoga je vrlo važno minimizirati broj stanja prije njegove strukturne sinteze.
Algoritam minimizacije zasniva se na particioniranju cijelog skupa stanja u parno disjunktne klase ekvivalentnih stanja i zamjeni cijele klase ekvivalencije jednim stanjem. Rezultirajući minimizirani automat će sadržavati onoliko stanja u onoliko klasa ekvivalencije na koliko je originalni skup stanja podijeljen.
Definicija
Dvije države a s i a m su ekvivalentni ako
(a s , E) =
(a m , E), gdje
- prelazna funkcija, E – ulazna riječ proizvoljne dužine.
Drugim riječima, stanja su ekvivalentna ako je isti niz stanja proizveden kao odgovor na iste ulazne riječi, bez obzira na to koje od ta dva stanja a s ili a m mašina se nalazila u početnom trenutku. Ako su dva stanja ekvivalentna, onda se jedno stanje može zamijeniti drugim.
Pored ekvivalentnih stanja, postoji koncept k-ekvivalentnih stanja: 1-ekvivalentna, 2-ekvivalentna itd.
Definicija
Dvije države a s i a m suk
-
ekvivalentno ako
(a s ,Ek) =
(a m ,Ek), Gdje
- prelazna funkcija, Ek– dužina ulazne riječik
.
Algoritam minimizacije:
Particije P 1, P 2, ... P K, P K+1 stanja automata nalaze se sekvencijalno sve dok na nekom K+1 koraku P K.+1 ne postane jednako P K. U ovom slučaju, rezultujuća k- Ekvivalentna particija će predstavljati potpuno ekvivalentne klase.
U svakoj klasi ekvivalencije se bira jedno stanje koje formira novi skup stanja minimiziranog automata.
Da bi se redefinirale funkcije prijelaza i izlaza, precrtani su redovi koji odgovaraju stanjima koja nisu uključena u novi skup stanja minimiziranog automata, a u preostalim redovima prijelazne tablice sva stanja se zamjenjuju njihovim ekvivalentima. stanja koja su uključena u novi skup.
Ako se skup sastoji od jednog stanja, onda nema ekvivalentnih stanja. Ako su sva stanja uključena u zasebne skupove iz jednog stanja, onda je automat ne može se minimizirati.
Particionisanje na skupove počinje sa 0-ekvivalentnom klasom. U ovom slučaju, stanja sa identičnim izlaznim signalima spadaju u iste skupove.
Tema 5.1. Obrada informacija korišćenjem mašina konačnih stanja
Poglavlje 5. Osnove teorije konačnih mašina
Sažetak na temu
Pregledajte pitanja
1. Koja je ovo ruta?
2. U kom slučaju se ruta naziva cikličkom?
3.Šta je strujni krug?
4. U kom slučaju 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 koherentne komponente šume?
9. Vrh se zove terminalni vrh ako?
Ova tema razmatra koncepte kao što su ruta, ciklus, lanac, kontura i tako dalje u vezi sa grafovima. Dati su Ojlerov i Hamiltonov ciklus. Prikazana je posebna struktura grafa, koja je definisana kao stablo. Zbirka ovih objekata okarakterisana je kao šuma.
Target: razmotriti osnove teorije konačnih mašina.
Zadaci:
1. Razmotrite koncept apstraktnog automata.
2. Identifikujte načine specificiranja automata.
3. Razmotrite odnos između Mil i Mooreovih automata.
Mašina- diskretni informacioni pretvarač sposoban za prelazak iz stanja u stanje pod uticajem ulaznih signala i generisanje izlaznih signala.
Apstraktni automat je definiran korištenjem sljedećih pet skupova:
A = (X, Y, S, d, l),
Gdje X = (X 1, X 2 ... X M)– ulazna abeceda mašine ili skup ulaznih simbola;
Y = (Y 1, Y 2 ... Y N)– izlazna abeceda mašine ili skup izlaznih simbola;
S = (S 0 , S 1 . . . S K-1 )– abeceda ili skup unutrašnjih stanja mašine;
S 0– početno stanje mašine (u trenutku t = 0).
d– prelazna funkcija;
l- funkcija izlaza mašine.
Mašina se zove konačni stroj , ako se postavlja X, Y, S konačan (ili prebrojiv).
Mašina radi u diskretnim trenucima vremena t = 0, 1, 2 ...n(Sl. 5.1) .
Rice. 5.1. Državni stroj
U svakom trenutku, automat se nalazi u jednom od brojnih stanja S.
Funkcija prijelaza d t sljedeće stanje stroja ovisno o trenutnom stanju i ulaznom signalu ili simbolu ulazne abecede. Drugim riječima, funkcija d Svaki par „stanje – ulazni signal“ povezan je sa sljedećim stanjem.
d: S´X ® S; d- je preslikavanje kartezijanskog proizvoda S´X V S.
Prijelazna funkcija se može napisati na sljedeći način: S t+1 = d(S t , X t).
Izlazna funkcija l određuje u svakom trenutku vremena t izlazni signal mašine.
Postoje dva modela slot mašina – Mealy slot mašina i Moore slot mašina. Razlikuju se po funkciji izlaza koja je definirana na sljedeći način:
Y t = l (S t , X t)- za Mili mašinu, ili l: S´X®Y.
Y t = l (S t)- za Moore mašinu.
U Mili mašini, izlazni signal u trenutku t zavisi od ulaznog signala u trenutku t, i iz trenutnog stanja.
U Moore mašini, izlazni signal jasno ne zavisi od ulaznog signala i određen je samo trenutnim stanjem.
Status mašine je memorija mašine prošlih ulaznih uticaja.
Zovu se i automati sekvencijalne mašine (Sekvencijalne mašine), pošto se ulazna sekvenca pretvara u sekvencu stanja i izlaznu sekvencu.
Možemo reći da apstraktni automat ima 1 ulaz i 1 izlaz. Na ulazu mašine se primaju nizovi slova ulazne abecede, a na izlazu se formiraju izlazni nizovi.
Riječ ili lanac je konačan niz simbola (slova) ulazne abecede. Moraju biti ispunjeni sljedeći uslovi (uslovi automatizacije):
1. Dužine 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.
Imati jedan ulaz, jedan izlaz i u svakom trenutku biti u jednom stanju od mnogo mogućih. Ulaz u ovaj uređaj su simboli jedne abecede, a na izlazu proizvodi simbole (u opštem slučaju) drugog alfabeta.
Formalno, apstraktni automat je definisan kao pet
Ograničavanje broja parametara apstraktnog automata definisalo je koncept konačnog automata.
Funkcionisanje automata sastoji se od generisanja dva niza: niza sledećih stanja automata i nizove izlaznih simbola , što za niz znakova odvijaju se u diskretnim vremenskim trenucima t = 1, 2, 3, ... Diskretni vremenski momenti se nazivaju takt ciklusa.
Funkcionisanje automata u diskretnim trenucima vremena t može se opisati sistemom rekurentnih relacija:
Da bi se razjasnila svojstva apstraktnih automata, uvedena je klasifikacija.
Apstraktni automati čine osnovnu klasu diskretnih modela, i kao model sam po sebi, i kao fundamentalna komponenta Turingovih mašina, automata za skladištenje memorije, mašina konačnih stanja i drugih informacijskih transformatora.
Napišite recenziju o članku "Apstraktni automat"
Odlomak koji karakteriše apstraktni automat
Car se sa osmehom okrenu prema jednom od svoje pratnje, pokazujući na ljude sa Abšerona, i reče mu nešto.Kutuzov je, u pratnji svojih ađutanata, jahao brzinom iza karabinjera.
Prešavši pola milje u repu kolone, zaustavio se u usamljenoj napuštenoj kući (vjerovatno nekadašnjoj gostionici) u blizini račvanja dva puta. Oba puta su išla nizbrdo, a trupe su marširali obama.
Magla je počela da se razilazi i nejasno, oko dve milje dalje, neprijateljske trupe su se već vidjele na suprotnim brdima. Lijevo ispod pucnjava je postala sve glasnija. Kutuzov je prestao da razgovara sa austrijskim generalom. Princ Andrej, koji je stajao nešto pozadi, zavirio je u njih i, želeći da zamoli ađutanta za teleskop, okrenuo se prema njemu.
„Vidi, vidi“, reče ovaj ađutant, gledajući ne u daleku vojsku, već niz planinu ispred sebe. - Ovo su Francuzi!
Dva generala i ađutanta počeše hvatati cijev, otimajući je jedan od drugog. Sva lica su se odjednom promijenila i svi su izrazili užas. Francuzi su trebali biti udaljeni dvije milje od nas, ali su se iznenada, neočekivano pojavili ispred nas.
- Da li je ovo neprijatelj?... Ne!... Da, vidi, on... verovatno... Šta je ovo? – čuli su se glasovi.
Knez Andrej je jednostavnim okom ugledao dole s desne strane gustu kolonu Francuza kako se diže prema Apšeroncima, ne dalje od pet stotina koraka od mesta gde je stajao Kutuzov.
“Evo ga, došao je odlučujući trenutak! Stvar je stigla do mene“, pomisli knez Andrej i, udarivši konja, odjaše do Kutuzova. "Moramo zaustaviti Apšeronce", povikao je, "Vaša Ekselencijo!" Ali baš u tom trenutku sve je bilo prekriveno dimom, čula se blizina pucnjave, a naivno uplašeni glas na dva koraka od kneza Andreja povikao je: „Pa, braćo, subota je!” I kao da je ovaj glas bio naredba. Na ovaj glas sve je krenulo.
Izmiješane, sve veće gomile pobjegle su nazad na mjesto gdje su prije pet minuta trupe prošle pored careva. Ne samo da je bilo teško zaustaviti ovu gomilu, već je bilo nemoguće ne pomaknuti se zajedno sa gomilom.
Bolkonski je samo pokušavao da održi korak sa njom i gledao oko sebe, zbunjen i nesposoban da shvati šta se dešava ispred njega. Nesvitsky ogorčenog pogleda, crven i ne nalik sebi, viknuo je Kutuzovu da će, ako sada ne ode, vjerovatno biti uhvaćen. Kutuzov je stajao na istom mestu i bez odgovora izvadio maramicu. Krv mu je tekla iz obraza. Princ Andrej mu je prišao.
-Jesi li povrijeđen? – upitao je jedva držeći donju vilicu da ne zadrhti.
– Rane nisu ovde, ali gde! - rekao je Kutuzov, prislonivši maramicu na ranjeni obraz i pokazao na ljude koji su bežali. - Zaustavite ih! - viknuo je i istovremeno, verovatno uverivši se da ih je nemoguće zaustaviti, udario konja i odjahao udesno.
Na izlazu proizvodi simbole (u opštem slučaju) drugačije abecede.
Apstraktni automat
Formalno, apstraktni automat je definisan kao pet
Ograničavanje broja parametara apstraktnog automata definisalo je koncept konačnog automata.
Funkcionisanje automata sastoji se od generisanja dva niza: niza narednih stanja automata i niza izlaznih simbola, koji se za niz simbola odvijaju u diskretnim vremenskim trenucima t = 1, 2, 3, ... Diskretno vremenski momenti se nazivaju ciklusi sata.
Funkcionisanje automata u diskretnim trenucima vremena t može se opisati sistemom rekurentnih relacija:
Da bi se razjasnila svojstva apstraktnih automata, uvedena je klasifikacija.
Apstraktni automati čine osnovnu klasu diskretnih modela, i kao model sam po sebi, i kao fundamentalna komponenta Turingovih mašina, automata za skladištenje memorije, mašina konačnih stanja i drugih informacijskih transformatora.
Wikimedia fondacija. 2010.
- Dijagram stanja (teorija automata)
- Nagorno-Karabah
Pogledajte šta je "Apstraktni automat" u drugim rječnicima:
apstraktni automat- abstraktusis automatas statusas T sritis automatika atitikmenys: engl. apstraktni automat vok. apstrakter Automat, m rus. apstraktni automat, m pranc. automate abstrait, m … Automatikos terminų žodynas
Mašina- U Vikirječniku postoji članak "automatski" Automatski: Automatski je uređaj koji samostalno izvodi neke radnje ... Wikipedia
Državni stroj- Mašina konačnog stanja je apstraktna mašina bez izlaznog toka, čiji je broj mogućih stanja konačan. Rezultat rada mašine je određen njenim konačnim stanjem. Postoje različite opcije za specificiranje konačnog stroja. Na primjer,... ... Wikipedia
TURING MACHINE- Apstraktni automat (tj. kompjuter ili drugi precizni, definisani mehanizam), teorijski okarakterisan od strane britanskog matematičara Alana M. Turinga 1930-ih. U osnovi, Turingova mašina se sastoji od trake i glave za čitanje. Traka… … Eksplanatorni rečnik psihologije
Teorija automata
Teorija automata- dio teorijske kibernetike koji proučava matematičke modele (ovdje se nazivaju automati ili mašine) stvarnih ili mogućih uređaja koji obrađuju diskretne informacije u diskretnim ciklusima. Glavni... ... Ekonomsko-matematički rječnik
teorija automata- Odeljak teorijske kibernetike koji proučava matematičke modele (ovde se nazivaju automati ili mašine) stvarnih ili mogućih uređaja koji obrađuju diskretne informacije u diskretnim ciklusima. Osnovni koncepti ove teorije ... ... Vodič za tehnički prevodilac
Teorija automata- Teorija automata je grana diskretne matematike koja proučava apstraktne automate, kompjutere, predstavljene u obliku matematičkih modela i problema koje oni mogu da reše. Teorija automata je najbliža ... ... Wikipediji
Kompjuter- Šema personalnog računara: 1. Monitor 2. Matična ploča 3 ... Wikipedia
Formalne metode- Primjer formalne specifikacije koristeći Z notaciju U računarskoj nauci i softverskom inženjerstvu, formalne metode su grupa tehnika zasnovanih na matematičkom aparatu za ... Wikipedia
