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.
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.
Potpis
I love the smell of napalm in the morning...
