Zadatak iz Turinga

[cereal]

Dobio sam ovaj zadatak za rijesit, ali ne znam kako. Ako bi mogao netko da baci ideju i pomogne rijesiti bio bih zahvalan.
Imam nekakvu ideju za rijesavanje na engleskom, pa da sad ne postam ovdje ako je netko voljan posljem na PM.

Konstruirati i opisati rad Touringovog stroja koji će izračunavati vrijednosti logičkih izraza s Booleovim operatorima I i ILI. Simbol ulazne trake koji odgovara logičkom operatoru I je *, a simbol ulazne trake koji odgovara logičkom operatoru ILI je +. Primjer zapisa funkcije na ulaznoj traci Touringova stroja: 1+1*0+1*1. Touringov stroj prvo mora ispitati da li je ulazni niz ispravno zadan, a nakon toga izračunati rezultat zadanog logičkog izraza.

[vsego]

Uhhh... cini mi se da tu ima posla.

Radim odvojeno; lako se poveze.

1. Provjera:
Trcis po cijeloj rijeci i provjeravas da se naizmjence pojavljuju 0 ili 1 i + ili *, te da su prvi i zadnji znak 0 ili 1 (procjenjujem da ti za ovo ti treba 2 stanja, plus jedno za "ne valja").

2. Racunanje:
Rijesio bih to u dva prolaza (zbog prioriteta operatora).
Kreces na nekom kraju rijeci (svejedno kojem), u stanju q.
2.1. Racunanje "I":
U prvom prolazu citas znak i ides u stanje q0 ili q1. Zatim citas znak. Ako je znak "+", vracas se u stanje q. Ako je "*", onda
1. ako si u stanju q0, brises "*" i iduci znak (koji god bio), jer je rezultat 0*x uvijek 0.
2. ako si u stanju q1, brises "*" i prethodni znak (to je 1), jer je rezultat 1*x uvijek x.
Nakon brisanja se vracas na prvi neobrisani znak (ili na pocetak izraza; svejedno) i ides u stanje q.
Brisanje (dva) znaka se radilo na vjezbama, a mislim da ima objasnjeno i u skripti iz Prog1 (ok, samo za 1 znak, no za 2 je slicno).
2.2. Racunanje "ILI":
Kad je ovo gore gotovo, ides opet kroz cijeli izraz, samo mijenjas ponasanje kad procitas znak (koji je sada sigurno "+" jer smo sve "*" obrisali):
1. ako si u stanju q0, brises "+" i prethodni znak (to je 0), jer je rezultat 0+x uvijek x.
2. ako si u stanju q1, brises "*" i iduci znak (koji god bio), jer je rezultat 1+x uvijek 1.
Pazi da ne pobrkas stanja q, q0 i q1 iz tocaka 2.1 i 2.2: to nisu ista stanja, nego ja svaki potproblem gledam odvojeno!

Rezultat je ono sto prezivi na traci.

Brisanje se moze i olaksati tako da stavis neki znak lijevo i desno od izraza, npr. "|". Tada seces po izrazu izmedju tih znakova, a u setanjima zanemarujes sve razmake. Tada se "brisanje" svodi na "zamijeni razmacima". Uz takvu implementaciju, pazi da na kraju pozicioniras glavu na rezultat.

Nadam se da nisam fulao.

Molim da ovdje objavis (ili mi posaljes na PM/mail) rjesenje... mozda bih zadatak iskoristio u nastavi (ako smijem, that is).

_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.