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