?velser til uke 48

Denne uken?tar vi oss tid til ? gjennomg? eventuelle oppgaver fra tidligere uker som vi ikke har rukket ? se p?.?

For?vrig kan vi se p? turingmaskiner.? Det er en god ide ? gj?re i hvert fall noen av oppgavene under i JFLAP.? F?rst en liten kommentar om hva som skal til for at en turingmaskin stopper.? I JFLAP kan dette skje hvis kombinasjonen av tilstand og input ikke svarer til noen eksisterende transisjon, og det kan skje hvis maskinen havner i en (av muligens flere) sluttilstand(er), alts? en tilstand med dobbel ring rundt.? I tillegg kan transisjoner oppgi "S" i stedet for "L" eller "R".? Noen versjoner av turingmaskiner stopper n?r de kommer til slike transisjoner, men dette gj?r ikke JFLAP.? Her betyr S bare at lesehodet skal st? stille ved overgang til neste tilstand.? Gj?r oppgavene 1 til 4 side 773.? Gj?r ogs? en variant av oppgave 4 med minus i stedet for pluss.? Du kan anta at tallet som skal subtraheres ikke er st?rre enn det andre tallet.?? Skriv ogs? en Turingmaskin som avgj?r spr?ket {a^n b^n c^n | n >= 0}.? Denne maskinen skal alts? ha to stoppetilstander, og skal (til slutt)?havne i den ene hvis input er i dette spr?ket, og i den andre hvis input ikke er i dette spr?ket.