• Ei tuloksia

581336 Laskennan teoria (kevät 2006) Harjoitus 2 (31.1.-3.2.)

N/A
N/A
Info
Lataa
Protected

Academic year: 2022

Jaa "581336 Laskennan teoria (kevät 2006) Harjoitus 2 (31.1.-3.2.)"

Copied!
1
0
0

Ladataan.... (näytä koko teksti nyt)

Lataa nyt ( 1 sivua )

Kokoteksti

(1)

581336 Laskennan teoria (kevät 2006) Harjoitus 2 (31.1.-3.2.)

1. Esitä Turingin kone, joka tunnistaa kielen

f w 2 f a; b gj w sisältää yhtä monta a- ja b-merkkiä g:

2. Esitä kummallekin seuraavista kielistä sen tunnistava kaksinauhainen Turingin kone. Laadi kone siten, että se tekee mahdollisimman vähän siirtymiä.

(a) f anbnj n 0 g

(b) f w : wTj w 2 f a; b gg missä wTon merkkijono w takaperin (aakkostona siis f a; b; : g) 3. Esitä epädeterministinen Turingin kone, joka hyväksyy tasan ne aakkoston f a; b g merkkijonot,

joissa jokin vähintään kolmen merkin mittainen osamerkkijono esiintyy ainakin kahdessa eri paikassa. Toisin sanoen koneen tulee tunnistaa kieli

f uxvxw j u; v; w; x 2 f a; b g; jxj 3 g:

4. Esitä Turingin kone, joka laskee osittaisen funktion f: N ! N, missä f(n) = n 1 kun n 1, ja f(0) ei ole määritelty.

Viittaukset

Lataa nyt ( PDF - 1 sivua - 37.63 KB )

LIITTYVÄT TIEDOSTOT

581336 Laskennan teoria (kevät 2006) Harjoitus 5, ratkaisuja

Palautus tapahtuu muuttamalla syötteenä saadun koneen M w tilojen numerointia niin, ettei tilaa numero 5 käytetä mihinkään, ja vaihtamalla kaikki siirtymät johonkin lopputilaan

581336 Laskennan teoria (kevät 2006) Harjoitus 6 (14.-17.3.)

Osoita, että ongelma Siirtääkö annettu Turingin kone annetulla syötteellä koskaan nauhapää- tään vasemmalle on ratkeava1. (Vihje: palautus (a)-kohdan ongelmasta.)

581336 Laskennan teoria (kevät 2006) Harjoitus 6, ratkaisuja

Tehdään taas vastaoletus, että proseduuri Minimoi(M) palauttaa tilamäärältään pienimmän Turingin koneen, joka hyväksyy saman kielen kuin M ja käyttää samaa

581336 Laskennan teoria (kevät 2006) Harjoitus 7, ratkaisuja

Koska algoritmi voi tuottaa minkä tahansa osajoukon A, se löytää myös tällaisen osajoukon, jos sellainen on olemassa.. Toisaalta algoritmi ei hyväksy syötettä, ellei se löydä

581336 Laskennan teoria (kevät 2006) Harjoitus 8 (28.-31.3.)

Kuvaa, minkä tyyppisiä arvoja tällainen palautus saa syötteenään ja millaisia palauttaa, ja mitä ehtoja sen pitää toteuttaa.. (c) Esitä varsinainen palautus ja osoita, että

581336 Laskennan teoria (kevät 2006) Harjoitus 8, ratkaisuja

Sanomme, että palautusfunktion syötteitä ovat muotoa hG; ki olevat merkkijonot, ja tulos- teita muotoa hG 1 ; G 2 i olevat merkkijonot... Polynomisen laskenta-ajan takaa se,

581336 Laskennan teoria (kevät 2006) Harjoitus 9 (4.-7.4.)

Voit merkitä teh- tävän tehdyksi, vaikka viimeinen vaihe

581336 Laskennan teoria (kevät 2006) Harjoitus 9, ratkaisuja

Kysymyksessä on pa- lautus solmupeiteongelmasta joukkopeiteongelmaan, sillä solmujoukko U on solmupeite jos ja vain jos joukkoon U kuuluu vähintään toinen pää jokaisesta