[ jozef_k. @ 13.06.2009. 16:53 ] @
| Zadatak kaze: Konstruirati Turingov stroj koji zadane ulazne podatke sažima metodom LRE kompresije (length Run Encoding). Ćelija ulazne trake smatra se jednim nibbleom čija se vrijednost može kretati u rasponu 0-15 (preporuča se uporaba heksadekadskog zapisa). Turingov stroj treba slijedni zapis podataka prevesti u oblik u kojem će se za svaki podatak zapisati njegova vrijednost i broj uzastopnih ponavljanja na traci. Primjer: Podaci prije kompresije: 1125555AAAAA555FFF podaci nakon kompresije: 122154A553F2 Algoritam rješenja koji meni pada na pamet zvuči otprilike ovako: Turingov stroj bi se sastojao od jedne trake koja je beskonačna na desnoj strani. Pročita prvi znak upiše F na njegovo mjesto, te se miče do prvog blank (B) znaka u desno, kada naiđe na njega upiše taj znak na to mjesto i prelazi u odgovarajuće stanje. Onda se vraća lijevo do prvog F znaka te čita sljedeći, ako je znak kao prethodni prebacuje se u odgovarajuće stanje, opet ide desno do prvog blank polja i u njegovo mjesto upisuje broj 2. Pa ponovo lijevo do prvog F znaka procita sljedeci ako je isti upisuje 3 na krajnje desnom mjestu ako nije ide u neko drugo stanje, ponovo ide do kraja desno i upisuje odgovarajući znak... Malo jest komplicirano, ali nadam se da ste me shvatili. Buduci da je znak ćelije nibble (4 bita) najveći broj koji mogu zapisati je F tj. 15, a ako bi mi se neki znak pojavio npr. 17 puta ispis na kraju bi trebao izgledati (npr. ako se br 1 pojavio 17 puta) ...1F12 (svaki znak je odvojena ćelija). Sve ovo ovako lijepo izgleda, ali kad podjem raditi postaje haos radi broja stanja i prijelaza koja moram imati ovakvim načinom (trocifreni brojevi), stoga me zanima ima li kakav bolji način konstruiranja datog stroja ili modifikacija postojećeg te ako sam jos koji detalj zaboravio, a nisam smio itd. da ne duljim, svi komentari su dobrodosli. |