|
|
Pojam analize i sinteze konačnih automata
Dogadjaj D(α) je skup svih reči ulaznog alfabeta koje automat prevede iz početnog stanja s0 u stanje α. Kaže se da automat prepoznaje te ulazne reči. Prepoznavanje reči ulaznog alfabeta može se vršiti i na osnovu izlaznog alfabeta B. φ je automatno preslikavanje.Dogadjaj D(yi) je skup svih reči p ulaznog alfabeta A za koje postoji reč φ(p) takva da se završava slovom yi. Time je svakim izlaznim slovom automata definisan jedan dogadjaj kao skup reči ulaznog alfabeta. Skupovi D(yi) se ne seku i reči ulaznog alfabeta koje ne pripadaju ni jednom skupu D(yi) predstavljaju zabranjene reči automata. Svako automatno preslikavanje φ realizovano automatom sa ulaznim alfabetom A={x1,...,xn} i izlaznim alfabetom B={y1,...,yn} jednoznačno razbija skup svih reči alfabeta A na m+1 disjunktnih dogadjaja i to onih koji se u automatu prikazuju izlaznim signalima y1,y2,...,ym i zabranjenim rečima koje predstavljaju nemoguće dogadjaje. Važi i obrnuto,znajući dogadjaje D(y1),...,D(ym) jednoznačno se rekonstruiše (parcijalno) preslikavanje φ izmdju reču ulaznog i izlaznog alfabeta.
Zadatak analize konačnih automata sastoji se u odredjivanju dogadjaja D(y1),...,D(ym) na osnovu datog automatnog preslikavanja, ili na osnovu datih tablica prelaza i izlaza. Zadatak sinteze suprotan: Na osnovu dogadjaja D(y1),...,D(ym) treba odrediti automatno preslikavanje, odnosno tablice prelaza i izlaza. Pri analizi konačnog automata, koji je zadan tablicama prelaza i izlaza,traga se za disjunktnim skupovima dozvoljenih reči za svaki simbol izlaznog alfabeta. Pri apstraktnoj sintezi konačnog automata polazi se od nekih zahteva funkcionisanje automata, pa se traži odovarajući automat. Usled pottrebe za sintezom automata sa što manjim brojem stanja traženi automat se odredjuje postupkom minimizacije.