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