?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.