|
|
Konačni automati - graf automata
Alfabetske transformacije mogu se zadavati i simulirati pomoću automata.Konačni automati sačinjavaju posebnu klasu automata. Konačni automat vrši preradu simbola ulaznog alfabeta A={x1,...} u simbole izlaznog alfabeta B={y1,...}, pri čemu se može nalaziti u različitim stanjima skupa mogućih stanja S={s1,..}. Automat radi u diskretnom vremenu koje se označava prirodnim brojevima t=0,1,... Stanje automata si=si(t) zavisi od takta ,tj vremena t ,za t=0,s(0)=s 0 zove se početno stanje. Novo stanje je odredjeno zatečenim stanjem i ulaznim simbolom. Automat vrši dva preslikavanja:
S x A ->'strelica' S i S x A ->'strelica' B Prvo odredjuje funkciju prelaza Fs,a drugo funkciju izlaza Fy:
s(t)=Fs(s(t-1),x(t)) i y(t)= Fy(s(t-1),x(t)) Automat je konačan, ako su skupovi a,b,s konačni. Automat je potpun, ako su Fs i Fy definisane za sve parove (si,xj), u protivnom automat je parcijalan.
Konačni automati se mogu zadati sa dve tablice: tabica prelaza i tablica izlaza,čije vrste predstavljaju slova ulaznog alfabeta A , a kolone oznake stanja skupa S. Elementi u tablici prelaza su vrednosti funckije prelaza(stanje iz S),a elementi u tablici izlaza su vrednosti funkcije izlaza. Druga mogućnost zadavanja konačnog automata je korišćenje usmerenih grafova. Ovo su Milijevi automati. Ako se umesto funkcije izlaza Fy uzme funkcija: Ψy(t)=y(s(t)) dobija se Murov automat,kod koga izlazni signal zavisi samo od stanja u kojem se automat nalazi. U strukturnoj teoriji automata mora se praviti razlika izmedju Milijevih i Murovih automata ,zato što izlaz kod Milijevog automata nastaje istovremeno sa odgovarajućim ulaznim signalom,dok kod Murovog kasni za jedan takt. Za ulaznu reč p=x(1)x(2)...x(k) i početno stanje s(0) automata, pomoću Fs i Fy sukcesivno se dobijaju slova izlazne reči q=φ(p)=y(1)y(2)...y(k). Uslovi automatnosti preslikavanja: 1) φ pridružuje svakoj reči p ulaznog alfabeta A, reč φ(p)=q izlaznog alfabeta B iste duzine; 2) Ako se reč p1 poklapa sa početnim delom reči p, onda je reč φ(p1) početni deo reči φ(p).