|
|
Normalni algoritmi
Normalni algoritmi su algoritmi za transformaciju reči u nekom alfabetu pomoću uredjenog sistema usmerenih zamena. Normalni algoritam je odredjen nizom usmerenih zamena oblika A1->->'strelica'B1; A2->->'strelica'B2 ... An ->'strelica'->Bn gde su Ai,Bi reči u AR medju kojima se nalazi i završna zamena Aj ->'strelica' -> Bj za neko j. Primena završne zamene na reč X znači završetak rada algoritma. Neka je Uk operator izvršavanja zamene Ak->->'strelica'Bk,njegovom primenom na reč X vrši se zamena prvog sleva ulaženja Ak u X sa Bk. Neka je Φk identifikator koji prepoznaje ulaženje reči Ak u reč X, a Zk identifikator koji prepoznaje završnu zamenu. Normalni algoritam izgleda: NACRTAJ SLIKU.
Normalni algoritam za bilo koju ulaznu reč X uvek završava rad na dva moguća načina: ili je primenjena završna zamena ili je generisana reč na koju se ne može primeniti ni jedna od datih zamena. Na jeziku normalnih algoritama Osnovna hipoteza teorije algoritama glasi: Svaki algoritam moze se pretstaviti u obliku normalnog algoritma.
