Formleg mál og reiknanleiki
09.12.52


Lokapróf 9. desember 1994

Allar spurningarnar hafa sama vægi. Einungis þarf að svara 5 spurningum af 6. Bestu 5 svörin gilda.
Leyfileg hjálpargögn: Kennslubók (Thomas A. Sudkamp: Languages and Machines). Fyrirlestranótur og heimadæmi.



1. a) Lát fjx(w) vera fjölda af tákninu x í strengnum w. Skilgreinum málið L þannig:
L = { w stakí {a, b, c}* | (fja(w) + 2fjb(w) + 3fjc(w)) mod 3 = 0 }
Sýnið reglulega segð, stöðuvél og málfræði fyrir L.

b) Sannið að málið {ai | i er samsett tala } er ekki reglulegt mál



2. a) Venjulega samhengisóháða málfræðin fyrir spegilstrengi (palindromes) er gefin á bls. 57 í kennslubókinni. Setjið málfræðina á Chomsky staðalform.

b) Sýnið ótvíræða samhengisóháða málfræði fyrir málið { aibjckdl | i = j eða k = l }. Rökstyðjið að málfræðin sé ótvíræð.



3. a) Búið til staflavél til að bera kennsl á málin

  1. { aibjck | i = j eða j = k eða i = k }
  2. { xy | len(x) = len(y) og x != y }
b) Sannið að málið { aibjckdk | i = k og j = l } er ekki samhengisóháð.



4. Hver af eftirfarandi verkefnum eru leysanleg og hver eru óleysanleg. Rökstyðjið svar ykkar með sönnun á óleysanleika eða lausnaraðferð.
  1. Gefið samhengisóháð málfræði G yfir stafrófið {a, b}. Er L(G) = (aa sam bb)*?
  2. Gefin samhengisóháð málfræði G yfir stafrófið {a, b} og strengur w stakí {a, b}*. Er L(G) = {w}?
  3. Gefið Turing vél T. Stöðvast T á færri en 17 inntökum?



5. Sýnið Turing vélar fyrir eftirfarandi talnaföll. Þið megið nota ykkur fjölvanna í kafla 12 í kennslubók.
  1. exp(n, m) = nm.
  2. sqrt(n) = int(sqrt(n)), þ.e., kvaðratrótin af n, eða næsta náttúrulega tala fyrir neðan hana.



6. a) Lát 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. Sýnið að f sé einfalt rakið.
(Vísbending: Reynið fyrst að átta ykkur á því hvað f(x, i) er fyrir i = 0, 1, 2,...

b) Búið til einfalt rakið fall f þannig að fyrir sérhverja náttúrulega tölu y þá er f(x) = y fyrir óendanlega mörg x.