TK7T. 125/R.Heinonen

Tik-79.148 Tietojenkäsittelyteorian perusteet

Tentti joulukuu 1995

1. Määrittele formaalisti seuraavat käsitteet

a) Tyypin 0 kielioppi

b) u (myy)-rekursiivinen funktio.

c) Kieliopillinen laskettavuus

Osoita, että (w^R)^i= (w^i)^R kaikille merkkijonoille w ja i > 0 (R tarkoittaa symbolien käännettyä järjestystä)

Tee detemiinistinen tilakone, joka hyväksyy lausekkeen R määrittelemän kielen. (+ vastaa oppikirjan unioni merkkiä)

R = (ba + bb)* + (ab + aa)*

4. Olkoon G kielioppi G = (V, E, P, S), missä

V={S, B, C, a, b,d}

E= (a, b, d)

P:

S -> aSaa | B

B -> bbBdd | C

C -> bd

Kuvaile sanallisesti kieli L(G) ja osoita, että G todella m ttelee kuvailusi mukaisen kielen.

5. a) Perustele, miksi ongelma "Kuuluuko sana w yhteydettömän kieliopin G määrittelemään kieleen L(G)?" on aina ratkeava.

Selitä muunnos, jonka avulla annetusta yhteydettömästä kieliopista voidaan muodostaa vastaava pinoautomaatti.

c) Määrittele ongelmaluokat P ja NP