Turingova mašina - komprimiranje niza?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.
I love the smell of napalm in the morning...
