581336 Laskennan teoria (kevät 2006) Harjoitus 3, ratkaisuja
1.
S ! aXc X ! aXc X ! bY c
Y ! bY c Y ! "
2. (a) Tehtävänä on konstruoida rajoittamaton kielioppi, joka tuottaa kielen f0n1njn 1g.
Vaihe1: alkutilanteen tuottaminen Vaiheessa 1 tuotetaan lähtösymbolista muotoa x[q0x] oleva merkkijono, missä x 2 f0; 1g. Vaiheen 1 toteuttava kielioppi:
S ! T [q0] T ! T ! 0T A T ! 1T B A[q0! [q0A A0 ! 0A A1 ! 1A A] ! 0]
B[q0! [q0B B0 ! 0B B1 ! 1B B] ! 1]
Vaihe2: siirtymien simulointi Vaiheessa 2 simuloidaan turingin koneen toimintaa vai- heessa 1 generoidulla syötteellä. Jokaista Turingin koneen siirtymää kohti tulee yksi tai useampia kieliopin produktioita.
Siirtymä vastaava(t) produktio(t) (q0; 0) = (q1; X; R) q00 ! Xq1
(q0; Y ) = (q3; Y; R) q0Y ! Y q3 (q1; 0) = (q1; 0; R) q10 ! 0q1
(q1; Y ) = (q1; Y; R) q1Y ! Y q1 (q1; 1) = (q2; Y; L) 0q11 ! q20Y
1q11 ! q21Y Xq11 ! q2XY Y q11 ! q2Y Y [q11 ! [q2#Y (q2; Y ) = (q2; Y; L) 0q2Y ! q20Y 1q2Y ! q21Y Xq2Y ! q2XY Y q2Y ! q2Y Y [q2Y ! [q2#Y (q2; 0) = (q2; 0; L) 0q20 ! q200
1q20 ! q210 Xq20 ! q2X0 Y q20 ! q2Y 0 [q20 ! [q2#0 (q2; X) = (q0; X; R) q2X ! Xq0
(q3; Y ) = (q3; Y; R) q3Y ! Y q3 (q3; #) = (q4; #; R) q3] ! #q4]
Vaihe3: lopputilanteen siistiminen Vaiheessa 3 "siistitään"pois Turingin koneen ti- lannetta kuvaava osa. Jäljelle jää "arvattu"merkkijono x. Siistimisvaihe käynnistyy vain, jos simulointi on hyväksyvässä lopputilassa.
q4! X0Y0
#X0! X0 XX0! X0 Y X0! X0 0X0! X0 1X0! X0 [X0! Y0# ! Y0 Y0X ! Y0 Y0Y ! Y0 Y00 ! Y0 Y01 ! Y0 Y0] !
(b) Johto Merkkijonolle "01":
(vaihe 1) S T [q0] 0T A[q0] 01T BA[q0] 01BA[q0] 01B[q0A]
01[q0BA]
01[q0B0]
01[q00B]
01[q001]
(vaihe 2) 01[Xq11]
01[q2XY ] 01[Xq0Y ] 01[XY q3] 01[XY #q4] (vaihe 3)
01[XY #X0Y0] 01[XY X0Y0] 01[XX0Y0] 01[X0Y0] 01Y0] 01
3. (a) Merkkijono w21 saadaan muodostamalla luvun 21 binääriesitys 10101 ja poistamalla siitä ensimmäinen ykkönen. Merkkijono on siis 0101.
(b) Muodostetaan koodi kielen f0n1n j n 1g tunnistavalle koneelle
M = (fq0; q1; q2; q3; q4g; f0; 1g; f0; 1; X; Y; #g; ; q0; #; fq4g):
Koneen esitys ei ole vaaditun kaltainen, sillä tyhjä merkki # on aakkoston viimeinen merkki (pitäisi olla kolmas), tilojen numerointi alkaa nollasta (pitäisi alkaa yhdestä) ja hyväksyvä lopputila on q4(pitäisi olla q2). Huomioidaan nämä seikat suoraan koodauksen yhteydessä.
Tiloille, merkeille ja nauhapään siirroille saadaan seuraavat koodit:
q0 7! 0 q1 7! 000 q2 7! 0000 q3 7! 00000 q4 7! 00
0 7! 0 1 7! 00 X 7! 0000 Y 7! 00000
# 7! 000
L 7! 0 R 7! 00
Sen jälkeen koodataan siirtymät:
(q0; 0) = (q1; X; R) 7! 010100010000100
(q0; Y ) = (q3; Y; R) 7! 0100000100000100000100 (q1; 0) = (q1; 0; R) 7! 00010100010100
(q1; 1) = (q2; Y; L) 7! 0001001000010000010 (q1; Y ) = (q1; Y; R) 7! 0001000001000100000100
(q2; 0) = (q2; 0; L) 7! 000010100001010 (q2; X) = (q0; X; R) 7! 0000100001010000100
(q2; Y ) = (q2; Y; L) 7! 00001000001000010000010 (q3; Y ) = (q3; Y; R) 7! 00000100000100000100000100 (q3; #) = (q4; #; R) 7! 0000010001001000100
Koneelle M saadaan koodi luettelemalla siirtymien koodit mielivaltaisessa järjestyksessä merkkijonoilla 11 eroteltuina. Yksi mahdollinen koodi on esimerkiksi
010100010000100110100000100000100000100110001010001010011000100 100001000001011000100000100010000010011000010100001010110000100 001010000100110000100000100001000001011000001000001000001000001 00110000010001001000100
4. Jos v; w 2 , niin merkitään v < w jos merkkijono v on leksikograsessa järjestyksessä ennen merkkijonoa w. Olkoon wi aakkoston leksikograsessa järjestyksessä i:s merkkijono, toisin sanoen = f w1; w2; : : : g missä w1< w2< : : :.
(a) Oletuksen mukaan siis A = f f(w1); f(w2); : : : g ja f on laskettava. Tarkastellaan seuraavaa algoritmia, joka saa syötteenä merkkijonon x 2 :
1. i := 1;
2. jos f(wi) = x niin hyväksy;
3. i := i + 1 4. palaa kohtaan 2.
Jos x 2 A, niin oletuksen mukaan x = f(wi) jollain i, jolloin algoritmi hyväksyy. Muuten x 6= f(wi) kaikilla i, ja algoritmi jää ikuiseen silmukkaan.
Algoritmi voidaan toteuttaa esim. kolmenauhaisella Turingin koneella seuraavasti:
Nauha 1 sisältää syötteen x.
Nauha 2 on työnauha.
Nauha 3 sisältää käsittelyvuorossa olevan merkkijonon wi.
Olkoon Mf funktion f laskeva yksinauhainen Turingin kone, joka siis oletuksen mukaan on totaalinen. Kielen A tunnistavan koneen toiminta on seuraava:
0. (Alussa nauhat 2 ja 3 ovat tyhjiä.) 1. Simuloi konetta Mf nauhalla 2.
2. Kun Mf pysähtyi, vertaa nauhan 2 sisältöä nauhan 1 sisältöön.
Jos ne ovat samat, niin hyväksy.
3. Vaihda nauhan 3 ei-tyhjä osuus leksikograsessa järjestyksessä seuraavaan merkkijonoon.
4. Kopioi nauhan 3 sisältö nauhan 2 sisällöksi.
5. Palaa kohtaan 1.
(b) Nyt siis A = f f(w1); f(w2); : : : g, missä f(w1) < f(w2) < : : :. Siis jos x < f(wk) jollakin k, niin varmasti x 6= f(wi) kaikilla i > k, ja x 2 A jos ja vain jos x = f(wi) jollakin i < k.
1. i := 1;
2. jos f(wi) = x niin hyväksy;
3. jos f(wi) > x niin hylkää;
3. i := i + 1 4. palaa kohtaan 2.
Koska merkkijonot f(wi) muodostavat kasvavan jonon, algoritmi pysähtyy millä tahansa x. Edellä esitetyn perusteella algoritmi hyväksyy jos ja vain jos x 2 A, ja hylkää jos ja vain jos x 62 A.
(c) Oletetaan, että A on rekursiivinen ja ääretön. (Äärettömyysoletus oli virheellisesti jäänyt pois tehtävästä.) Olkoon A = f a1; a2; : : : g, missä a1< a2< : : :. Kun määritellään f(wi) = ai, niin selvästi A = f f(w) j w 2 g ja f on monotoninen. Funktio f argumentilla x voidaan laskea seuraavasti:
1. määritä k, jolla x = wk;
2. p := 0; % montako A:n alkiota on löytynyt 3. toista arvoilla i = 1; 2; : : ::
4. jos wi2 A niin p := p + 1;
5. jos p = k niin palauta wi.
Syötteellä wk algoritmi siis palauttaa sen merkkijonon w, joka on joukon A leksikogra- sessa järjestyksessä k:s alkio. Koska A on rekursiivinen, algoritmin jokainen yllä esitetty askel voidaan toteuttaa äärellisessä ajassa. Koska A on ääretön, laskuri p saavuttaa jossain vaiheessa arvon k, ja algoritmi pysähtyy. Se siis laskee totaalisen funktion, jolla on haluttu ominaisuus.
