Oppgave 1a
Strengene a,b,c,e er med i språket

Oppgave 1b
Strengene a,c,e er med i språket

Oppgave 2
automatene nummerert left-to-right, top-to-bottom (står feil i oppgaveteksten, der er det 2 automater som heter 5)
a. 2
b. 4
c. 6
d. 1
e. 5
f. 3

Oppgave 3
a.
Vanlig pumpelemmabevis for a^nc^n, men nå med et symbol b i mellom. Viktig er: ordentlig, matematisk bevis hvor *alle* conditions av pumpelemmaet brukes på en eller annen måte.

b.
Kan f.eks. lage en kontekstfri grammatikk:
S -> aSc
S -> b 

Kan selvfølgelig også lage en PDA hvis de vil.

Oppgave 4
a.
Viktige poeng: at det finnes minst et ord som har flere, ulike derivasjoner. Fullt score hvis de sier hva det betyr for to derivasjoner å være forskjellige: er ikke nok for variabelsubstitusjon å være i en annen rekkefølge,  det må være to "leftmost derivations" som er forskjellige.

b.
F.eks. den tomme strengen: S -> A -> e og S -> BAB -> eAB -> eeB -> eee. Finnes selvfølgelig masse forskjellige eksempler.

c.
helt standard PDA, finnes masse lignende, f.eks. i boka.

Oppgave 5.
a.
TM og NTM har samme uttrykningskraft. Forskjellen er i transisjonsfunksjonen (fint hvis de går litt mer i detalje, kanskje med definisjonen).

b.
Språket som gjenkjennes av automaten er a^+b^*, DFAen burde gjenkjenne det samme.

Oppgave 6 (vanskelig oppgave)
a.
Den formelle beskrivelsen burde være teknisk korrekt (som i boka). Det er ikke bare for å være streng, men gjør jobben mye enklere i de andre deloppgavene hvis de skriver, f.eks., den riktige definisjonen til delta funksjonen.

b.
Det er begge retninger å vise. Den ene er triviell (fra DFA til ORTM: først må man endre DFAen til en NFA med bare en accept og reject tilstand, og så er man faktisk nesten ferdig), den andre ganske enkel hvis man ser at transisjonsfunksjonen fra ORTM er faktisk allerede en DFA transisjonsfunksjon, bare skrevet på en litt annen måte.

c.
Begge retninger å vise. Den ene (DFA til ORSPTM) er ekstremt triviell, pga 6b. For den andre retningen må man bare kunne deale med "stay put" transisjonene i ORSPTM. De korresponderer til epsilontransisjoner i en NFA. Best hvis de skriver nøyaktig hvordan man oversetter ORSPTM transisjonsfunksjonen til en NFA transisjonsfunksjon.

Oppgave 7.
DS kan oversettes til en graf: hver brikke er en node, for hver brikkepar hvor høyre av den første er lik venstre av den andre fins det en kant i grafen. Så er spørsmålet om det finnes en sirkel i en mengde brikker ekvivalent til å finne en sirkel i grafen (som kan løses ved å bruke PATH eller CYCLE, som er i NL).

Oppgave 8.
Hint gir egentlig alt man trenger. Ideen er: gitt en graf så kan man konstruere en instans av HVIT-DS ved å lage en hvit brikke for hver node og en sort brikke for hver kante. Hvis man kan løse HVIT-DS, så får man da en sirkel med alle hvite brikker som tilsvarer en Hamilton path i grafen. Burde si noe om at reduksjonen er polynomielt. 

Oppgave 9.
a riktig, b feil. Hvis DS er PSPACE komplett får man PSPACE c NL c P c PSPACE. Hvis HVIT-DS er PSPACE komplett får man bare  PSPACE c NP.