|
|
Asocijativni računi
Asocijativni računi (AR) su specifični formalni sistemi koji se definišu alfabetom i skupom transformacija reči u tom alfabetu.
Alfabet A je konačan skup simbol - slova. Skup F je skup svih reči koje su konačni nizovi slova. Skup pravila R sadrži dopustive zamene oblika P - Q (neusmerena zamena) ili P → Q (usmerena zamena), gde su P,Q reči iz F. Asocijativni račun je skup svih reči u nekom alfabetu zajedno sa konačnim sistemom dopustivih zamena. Primena usmerene zamene P → Q na reč S, znači zamenu jednog nastupa reči P u S sa Q. Ako se reč P ne pojavljuje u reči S,primena zamene P → Q na reč S nije moguća. Neusmerena zamena P - Q dopušta zamenu jednog pojavljivanja P u S sa Q ali i zamenu jednog pojavljivanja Q u S sa P.
AR karakteriše jednostavnost polazne strukture, ali i širok domen značajnih primena. Medju istraživanjima u oblasti AR posebno mesto zauzima problem ekvivalentnosti reči. Ako se reč U može transformisati u reč V pomoću jedne primene dopustive(neusmerene) zamene, onda se i V može preoblikovati u U na taj način.Tada kažemo da us reči U i V susedne. Niz reči S1,S2,...,Sn-1,Sn takvih da su Si i Si+1 susedne zove se deduktivni lanackoji povezuje Si sa Sn. Ako postoji deduktivni lanac koji povezuje reč S sa reči R, tada postoji deduktivni lanac koji spaja R sa S. Tada kažemo da su reči R i S ekvivalentne ( R~S ). Tada važi: ako je S~R i R~T, onda je S~T.