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.