Formleg ml og reiknanleiki
09.12.52


Lokaprf 9. desember 1994

Allar spurningarnar hafa sama vgi. Einungis arf a svara 5 spurningum af 6. Bestu 5 svrin gilda.
Leyfileg hjlparggn: Kennslubk (Thomas A. Sudkamp: Languages and Machines). Fyrirlestrantur og heimadmi.




1. a) Lt fjx(w) vera fjlda af tkninu x strengnum w. Skilgreinum mli L annig:
L = { w stak {a, b, c}* | (fja(w) + 2fjb(w) + 3fjc(w)) mod 3 = 0 }
Sni reglulega seg, stuvl og mlfri fyrir L.

b) Sanni a mli {ai | i er samsett tala } er ekki reglulegt ml



2. a) Venjulega samhengisha mlfrin fyrir spegilstrengi (palindromes) er gefin bls. 57 kennslubkinni. Setji mlfrina Chomsky staalform.

b) Sni tvra samhengisha mlfri fyrir mli { aibjckdl | i = j ea k = l }. Rkstyji a mlfrin s tvr.



3. a) Bi til staflavl til a bera kennsl mlin

  1. { aibjck | i = j ea j = k ea i = k }
  2. { xy | len(x) = len(y) og x != y }
b) Sanni a mli { aibjckdk | i = k og j = l } er ekki samhengish.



4. Hver af eftirfarandi verkefnum eru leysanleg og hver eru leysanleg. Rkstyji svar ykkar me snnun leysanleika ea lausnarafer.
  1. Gefi samhengish mlfri G yfir stafrfi {a, b}. Er L(G) = (aa sam bb)*?
  2. Gefin samhengish mlfri G yfir stafrfi {a, b} og strengur w stak {a, b}*. Er L(G) = {w}?
  3. Gefi Turing vl T. Stvast T frri en 17 inntkum?



5. Sni Turing vlar fyrir eftirfarandi talnafll. i megi nota ykkur fjlvanna kafla 12 kennslubk.
  1. exp(n, m) = nm.
  2. sqrt(n) = int(sqrt(n)), .e., kvaratrtin af n, ea nsta nttrulega tala fyrir nean hana.



6. a) Lt f vera gefi me

f(x,0) = g(x)
f(x, y+1) = f(f(x, y), y)
ar sem g er einfalt raki fall. Sni a f s einfalt raki.
(Vsbending: Reyni fyrst a tta ykkur v hva f(x, i) er fyrir i = 0, 1, 2,...

b) Bi til einfalt raki fall f annig a fyrir srhverja nttrulega tlu y er f(x) = y fyrir endanlega mrg x.