{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1033{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f3\froman\fcharset2\fprq2{\*\panose 05050102010706020507}Symbol;}
{\f30\froman\fcharset238\fprq2 Times New Roman CE;}{\f31\froman\fcharset204\fprq2 Times New Roman Cyr;}{\f33\froman\fcharset161\fprq2 Times New Roman Greek;}{\f34\froman\fcharset162\fprq2 Times New Roman Tur;}
{\f35\froman\fcharset177\fprq2 Times New Roman (Hebrew);}{\f36\froman\fcharset178\fprq2 Times New Roman (Arabic);}{\f37\froman\fcharset186\fprq2 Times New Roman Baltic;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;
\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;
\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\ql \li0\ri0\widctlpar\faauto\adjustright\rin0\lin0\itap0 \fs20\lang2057\langfe1033\cgrid\langnp2057\langfenp1033 \snext0 Normal;}{\*\cs10 \additive Default Paragraph Font;}{
\s15\ql \li0\ri0\widctlpar\tqc\tx4153\tqr\tx8306\faauto\adjustright\rin0\lin0\itap0 \fs20\lang2057\langfe1033\cgrid\langnp2057\langfenp1033 \sbasedon0 \snext15 header;}{\s16\ql \li0\ri0\widctlpar\tqc\tx4153\tqr\tx8306\faauto\adjustright\rin0\lin0\itap0 
\fs20\lang2057\langfe1033\cgrid\langnp2057\langfenp1033 \sbasedon0 \snext16 footer;}{\*\cs17 \additive \fs24\lang1044\langfe0\langnp1044\langfenp0 \sbasedon10 page number;}}{\*\listtable{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4
\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid161627449}
{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 
\fi-360\li360\jclisttab\tx360 }{\listname ;}\listid162285693}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr
\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid454757145}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0
\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid535506856}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4
\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid952513192}
{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 
\fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1134058176}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr
\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1335762655}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0
\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1386877677}{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4
\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1644771598}
{\list\listtemplateid23919096\listsimple{\listlevel\levelnfc4\levelnfcn4\leveljc0\leveljcn0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\chbrdr\brdrnone\brdrcf1 \chshdng0\chcfpat1\chcbpat1\fbias0 
\fi-360\li360\jclisttab\tx360 }{\listname ;}\listid2141796477}}{\*\listoverridetable{\listoverride\listid1644771598\listoverridecount0\ls1}{\listoverride\listid162285693\listoverridecount0\ls2}{\listoverride\listid952513192\listoverridecount0\ls3}
{\listoverride\listid454757145\listoverridecount0\ls4}{\listoverride\listid2141796477\listoverridecount0\ls5}{\listoverride\listid1335762655\listoverridecount0\ls6}{\listoverride\listid161627449\listoverridecount0\ls7}{\listoverride\listid1134058176
\listoverridecount0\ls8}{\listoverride\listid1386877677\listoverridecount0\ls9}{\listoverride\listid535506856\listoverridecount0\ls10}}{\info{\title OPPGAVER I INF 120 - H\'f8sten 2001}{\author H R Jervell}{\operator Linda Langholm}
{\creatim\yr2001\mo11\dy16\hr10}{\revtim\yr2003\mo12\dy4\hr13\min14}{\printim\yr2003\mo12\dy2\hr14\min9}{\version40}{\edmins440}{\nofpages1}{\nofwords243}{\nofchars1386}{\*\company Universitetet i Oslo}{\nofcharsws0}{\vern8269}}
\paperw11906\paperh16838\margl1417\margr849\margt1417\margb1417 \widowctrl\ftnbj\aenddoc\pgnstart2\noxlattoyen\expshrtn\noultrlspc\dntblnsbdb\nospaceforul\hyphcaps0\formshade\horzdoc\dghspace120\dgvspace120\dghorigin1701\dgvorigin1984\dghshow0\dgvshow3
\jcompress\viewkind1\viewscale120\pgbrdrhead\pgbrdrfoot\nolnhtadjtbl \fet0\sectd \pgnrestart\pgnstarts2\linex0\headery709\footery709\colsx709\endnhere\sectdefaultcl {\footer \pard\plain \s16\ql \li0\ri0\widctlpar
\tqc\tx4153\tqr\tx8306\pvpara\phmrg\posxr\posy0\faauto\adjustright\rin0\lin0\itap0 \fs20\lang2057\langfe1033\cgrid\langnp2057\langfenp1033 {\cs17\fs24\lang1044\langfe1033\langnp1044 
\par }\pard \s16\qr \li0\ri360\widctlpar\tqc\tx4153\tqr\tx8306\faauto\adjustright\rin360\lin0\itap0 {\lang1044\langfe1033\langnp1044 Side }{\field{\*\fldinst {\cs17\fs24\lang1044\langfe1033\langnp1044  PAGE }}{\fldrslt {
\cs17\fs24\lang1024\langfe1024\noproof\langnp1044 2}}}{\cs17\fs24\lang1044\langfe1033\langnp1044  av 3}{\lang1044\langfe1033\langnp1044 
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \ql \li0\ri0\widctlpar\faauto\adjustright\rin0\lin0\itap0 
\fs20\lang2057\langfe1033\cgrid\langnp2057\langfenp1033 {\b\fs24\lang1044\langfe1033\langnp1044 Oppgave 1. }{\fs16\lang1044\langfe1033\langnp1044 
\par }{\fs24\lang1044\langfe1033\langnp1044 I denne oppgaven tar vi utgangspunkt i en kontekstfri grammatikk med terminalalfabet }{\lang1044\langfe1033\langnp1044 \{a,b\},}{\fs24\lang1044\langfe1033\langnp1044  hjelpealfabet }{\lang1044\langfe1033\langnp1044 
\{S,A,B\}}{\fs24\lang1044\langfe1033\langnp1044 , startsymbol }{\lang1044\langfe1033\langnp1044 S}{\fs24\lang1044\langfe1033\langnp1044 , og med f\'f8lgende regler.
\par }{\fs16\lang1044\langfe1033\langnp1044 
\par }{\lang1033\langfe1033\langnp1033 S }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  a B
\par S }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  b A
\par A }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  a
\par A }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  a S
\par B }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  b
\par B }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  b S
\par }{\fs16\lang1033\langfe1033\langnp1033 
\par }{\fs24\lang1044\langfe1033\langnp1044 a) Finn et regul\'e6rt uttrykk og en endelig automat som begge definerer samme spr\'e5k.
\par 
\par b) Vi legger n\'e5 til de to reglene  
\par }{\fs16\lang1044\langfe1033\langnp1044 
\par }{\lang1033\langfe1033\langnp1033 A }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  b A A
\par B }{\lang1033\langfe1033\langnp1033 {\field{\*\fldinst SYMBOL 174 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1033\langfe1033\langnp1033  a B B
\par }{\fs16\lang1033\langfe1033\langnp1033 
\par }{\fs24\lang1044\langfe1033\langnp1044 Tegn opp to mulige parsetr\'e6r for ordet aabbab i forhold til denne nye grammatikken.
\par 
\par c) Lag en stakkautomat som definerer samme spr\'e5k som grammatikken i punkt b.
\par 
\par }{\b\fs24\lang1044\langfe1033\langnp1044 Oppgave 2. }{\fs16\lang1044\langfe1033\langnp1044 
\par }\pard \ql \li0\ri0\widctlpar\aspalpha\aspnum\faauto\adjustright\rin0\lin0\itap0 {\fs24\lang1044\langfe1033\langnp1044 I denne oppgaven tar vi utgangspunkt i spr\'e5ket for utsagnslogikk, og vi konsentrerer oss om utsagn i disjunktiv normalf
orm.  I en slik sammenheng kan vi sl\'f8yfe alle parenteser og likevel vite hva som er ment.  For eksempel kan f\'f8lgende  utsagn (som egentlig allerede mangler noen parenteser)
\par }{\fs16\lang1044\langfe1033\langnp1044 
\par }\pard \ql \li0\ri0\widctlpar\faauto\adjustright\rin0\lin0\itap0 {\lang1044\langfe1033\langnp1044    (P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{
\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{
\lang1044\langfe1033\langnp1044  R) }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  (R  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst 
SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q)      }{
\fs24\lang1044\langfe1033\langnp1044 skrives som}{\lang1044\langfe1033\langnp1044        P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{
\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{
\lang1044\langfe1033\langnp1044  R }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  R  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst 
SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q  
\par }{\fs16\lang1044\langfe1033\langnp1044 
\par }{\fs24\lang1044\langfe1033\langnp1044 S\'e5 lenge vi vet at dette er i disjunktiv normalform, vet vi hva som er ment.  I oppgaven videre g\'e5r vi ut fra at bare de tre atom\'e6re utsagnene }{\lang1044\langfe1033\langnp1044 P, Q, R }{
\fs24\lang1044\langfe1033\langnp1044 er i bruk.
\par 
\par a) Skriv et regul\'e6rt uttrykk for spr\'e5ket av slike parentesfrie utsagn i disjunktiv normalform.
\par 
\par b) Vi tar n\'e5 utgangspunkt i en tolkning som gj\'f8r }{\lang1044\langfe1033\langnp1044 P}{\fs24\lang1044\langfe1033\langnp1044  og }{\lang1044\langfe1033\langnp1044 R}{\fs24\lang1044\langfe1033\langnp1044  sanne, og }{\lang1044\langfe1033\langnp1044 Q}{
\fs24\lang1044\langfe1033\langnp1044  usann.  Lag en endelig automat som leser slike parentesfrie utsagn i disjunktiv normalfrom (fra venstre mot h\'f8yre), og som aksepterer n\'f8yaktig de utsagnene som er sanne i denne tolkningen.  Maskinen skal alts
\'e5 akseptere 
\par }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{
\lang1044\langfe1033\langnp1044  Q }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  R  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  R }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst 
SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P  }{\fs24\lang1044\langfe1033\langnp1044 (fordi dette her bare kan oppfattes som }{\lang1044\langfe1033\langnp1044 (}{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst 
SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q) }{
\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  (R  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{
\lang1044\langfe1033\langnp1044  R) }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P }{\fs24\lang1044\langfe1033\langnp1044 ) og den skal ikke akseptere }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{
\lang1044\langfe1033\langnp1044  P }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 218 \\f "Symbol"
 \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  Q  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 217 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  R }{\lang1044\langfe1033\langnp1044 
{\field{\*\fldinst SYMBOL 218 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  }{\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 216 \\f "Symbol" \\s 10}{\fldrslt\f3\fs20}}}{\lang1044\langfe1033\langnp1044  P  
\par 
\par }{\fs24\lang1044\langfe1033\langnp1044 c) Lag n\'e5 en turingmaskin som unders\'f8ker om et slikt utsagn b\'e5de er sant i tolkningen over, og i tolkningen der }{\lang1044\langfe1033\langnp1044 P}{\fs24\lang1044\langfe1033\langnp1044  og }{
\lang1044\langfe1033\langnp1044 Q}{\fs24\lang1044\langfe1033\langnp1044  er usanne mens }{\lang1044\langfe1033\langnp1044 R}{\fs24\lang1044\langfe1033\langnp1044  er sann.  Du kan selv velge hvor lesehodet skal st\'e5 n\'e5
r maskinen starter. (Hint:  Det enkleste er nok \'e5 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.
\par 
\par }{\b\fs24\lang1044\langfe1033\langnp1044 Oppgave 3. 
\par }{\fs24\lang1044\langfe1033\langnp1044 Gj\'f8r kort rede for hva beverfunksjonen er, og forklar hvorfor det alltid m\'e5 v\'e6re slik at B(n) }{\fs24\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 163 \\f "Symbol" \\s 12}{\fldrslt\f3\fs24}}}{
\fs24\lang1044\langfe1033\langnp1044  B(m) hvis n }{\fs24\lang1044\langfe1033\langnp1044 {\field{\*\fldinst SYMBOL 163 \\f "Symbol" \\s 12}{\fldrslt\f3\fs24}}}{\fs24\lang1044\langfe1033\langnp1044  m.
\par                            
\par 
\par                                  -------------   SLUTT P\'c5 OPPGAVESETTET  ------------------------------}{\b\fs24\lang1044\langfe1033\langnp1044 
\par }}