Oppgave 1. 
I denne oppgaven tar vi utgangspunkt i en kontekstfri grammatikk med terminalalfabet {a,b}, hjelpealfabet {S,A,B}, startsymbol S, og med følgende regler.

S  a B
S  b A
A  a
A  a S
B  b
B  b S

a) Finn et regulært uttrykk og en endelig automat som begge definerer samme språk.

b) Vi legger nå til de to reglene  

A  b A A
B  a B B

Tegn opp to mulige parsetrær for ordet aabbab i forhold til denne nye grammatikken.

c) Lag en stakkautomat som definerer samme språk som grammatikken i punkt b.

Oppgave 2. 
I denne oppgaven tar vi utgangspunkt i språket for utsagnslogikk, og vi konsentrerer oss om utsagn i disjunktiv normalform.  I en slik sammenheng kan vi sløyfe alle parenteser og likevel vite hva som er ment.  For eksempel kan følgende  utsagn (som egentlig allerede mangler noen parenteser)

   (P   Q  R)  (R    P   Q)      skrives som       P   Q  R  R    P   Q  

Så lenge vi vet at dette er i disjunktiv normalform, vet vi hva som er ment.  I oppgaven videre går vi ut fra at bare de tre atomære utsagnene P, Q, R er i bruk.

a) Skriv et regulært uttrykk for språket av slike parentesfrie utsagn i disjunktiv normalform.

b) Vi tar nå utgangspunkt i en tolkning som gjør P og R sanne, og Q usann.  Lag en endelig automat som leser slike parentesfrie utsagn i disjunktiv normalfrom (fra venstre mot høyre), og som aksepterer nøyaktig de utsagnene som er sanne i denne tolkningen.  Maskinen skal altså akseptere 
 P  Q  R   R   P  (fordi dette her bare kan oppfattes som ( P  Q)  (R   R)   P ) og den skal ikke akseptere  P  Q  Q   R   P  

c) Lag nå en turingmaskin som undersøker om et slikt utsagn både er sant i tolkningen over, og i tolkningen der P og Q er usanne mens R er sann.  Du kan selv velge hvor lesehodet skal stå når maskinen starter. (Hint:  Det enkleste er nok å lage en ny endelig automat som sjekker sannhet i forhold til den nye tolkningen, og la turingmaskinen simulere de to endelige automatene i tur og orden.)  Skisser hvordan dette kan bygges ut til en turingmaskin som sjekker om et slikt utsagn er logisk gyldig.

Oppgave 3. 
Gjør kort rede for hva beverfunksjonen er, og forklar hvorfor det alltid må være slik at B(n)  B(m) hvis n  m.

                                 -------------   SLUTT PÅ OPPGAVESETTET  ------------------------------