Johdatus laskettavuuteen [lecture notes] [PDF]

Zitiervorschau

JOHDATUS

LASKETTAVUUTEEN Vesa Halava ja Tero Harju Matematiikan laitos Turun yliopisto

Kevät 2007

1

Johdanto

Tällä kurssilla on tarkastella laskettaavuuden teorian perusteita, lähinnä erilaisia malleja koneille, jotka pystyvät suoriutumaan erilaisista algoritmisista tehtävistä. Näiden koneiden eli automaattien rakenne, erityisesti muistin koko, on ratkaisevaa niiden kyvylle ratkaista ongelmia. Laskettavuuden teoria puolestaan kartoittaa ongelmaa, mitkä tehtävät ovat periaatteessa algoritmisesti ratkaistavissa. Laskettavuuden teorian peruspilari on Turingin kone (automaatti sekin), joka on algoritmin käsitteen formaalinen vastike.

Aakkosto ja sanat Aakkosto

Σ on jokin äärellinen epätyhjä joukko symboleja eli kirjaimia. Jono w = a1 a2 . . . an näitä kirjaimia (ai ∈ Σ ) on aakkoston Σ sana. Merkitään kaikkien sanojen joukkoa Σ ∗ :llä, jossa on määritelty sanojen tulo (eli yhdistäminen, katenaatio), u · v = uv . Huomaa, että jokainen kirjain on myös sana. Sanan w = a1 a2 . . . an (ai ∈ Σ ) pituus on |w| = n. Erityisesti, tyhjä sana, jota merkitään symbolilla ε ja jossa ei ole yhtään kirjainta, kuuluu joukkoon Σ ∗ . Näin ollen |ε| = 0, ja kaikille sanoille w ∈ Σ ∗ on voimassa w · ε = w = ε · w.

Esim. 1.1 Ohjelmoitaessa esimerkiksi PASCAL-kielellä aakkostona on tavallinen kirjoitusaakkosto, jonka kirjaimina ovat A, B, . . . , a, b, . . . sekä (, ), [, ], . . . . Aakkoston suuruus on noin 80 symbolia. Mukana on myös sananväli, joka ei ole tyhjä sana! PASCAL-kääntäjä tulkitsee tietyt sanat `kirjaimiksi', joille se varaa muistipaikan osoitteet. Tällaisia ovat variaabelit (var mynumber : integer). Myös sellaiset sanat kuin begin, end, for, while, . . . kääntäjä tulkitsee kokonaisuuksiksi, joita se ei jaa pienemmiksi osasiksi. Kääntäjän aakkosto on huomattavasti laajempi kuin ohjelman kirjoittajan. Kun PASCAL-kääntäjä muokkaa ohjelman sopivaksi EXE-tiedostoksi, tavataan toisenlainen aakkosto, jossa esiintyvät symbolit ovat ASCII-merkkejä, joita on 256 kappaletta. (Tämä ASCII-aakkosto on kuitenkin vain koodattu versio EXE-tiedostosta. Jokainen ASCIImerkki on kahdenpituisen heksadesimaaliluvun koodaus, ja heksadesimaalilukujen aakkosto on 0, 1, . . . , 9, A, . . . , F , Todellisuudessa, kaiken kukkuraksi, koneen käyttämä aakkosto on binäärinen: `Ei,On'  `0,1'  ` , ∧'.) ⊓ ⊔ Esim. 1.2

Olkoon Σ = {a, b, c} aakkosto, jolloin u = aab ja v = acab ovat sanoja. Näille u · v = aabacab, |u| = 3, |v| = 4 ja |uv| = 7 = |u| + |v|. Myös u · ε · v = uv . Toisaalta aakkostossa ∆ = {♥1 , . . . , ♥13 , ♦1 , . . . , ♦13 , ♠1 , . . . , ♠13 , ♣1 , . . . , ♣13 }

mukavia sanoja ovat esimerkiksi ♥4 ♥4 ♠7 ♠7 ♠7 ja ♦1 ♣4 ♦3 ♥5 ♠2 . Olkoot u, v ∈ Σ ∗ kaksi sanaa. Tällöin v on sanan u joillain sanoilla u1 , u2 ∈ Σ ∗ . Lisäksi, edellä v on u:n

⊓ ⊔

osasana (tekijä),

jos u = u1 vu2

1 Johdanto • •

3

preksi (alkuosa, vasen tekijä),

jos u1 = ε. Tällöin merkitään v ≤ u. Jos v ≤ u ja v 6= u, voidaan merkintä v < u, ja tällöin v on u:n aito preksi. suksi (loppuosa, oikea tekijä), jos u2 = ε.

Sanan w = a1 a2 . . . an ∈ Σ ∗

peilikuva

on sana wR = an an−1 . . . a1 . Tällöin (uv)R = v R uR kaikille u, v ∈ Σ ∗ . Sanotaan, että w on palindromi, jos w = wR . • i:s potenssi on sana wi = ww . . . w}. Erityisesti, w0 = ε, ja wn wm = wn+m . Sanotaan, | {z •

että w on

i kpl

primitiivinen, jos

w = uk =⇒ u = w ja k = 1 ,

eli w ei ole minkään (muun) sanan potenssi. Tässä ehto k = 1 tulee käyttöön vain kun w = ε, sillä epätyhjille sanoille w 6= ε edeltävä ehto on yhtäpitävä ehdon w = uk =⇒ u = w kanssa.

Esim. 1.3

Olkoon Σ = {a, b} binäärinen aakkosto.

Sana v = abb on sanan w = abba preksi, eli v ≤ w (jopa v < w), ja v R = bba on sanan wR suksi. • Sana voidaan usein esittää lyhyemmässä muodossa käyttäen potensseja. Lisäksi sulkeita voidaan lisätä sanaan (paitsi jos ne ovat kirjaimia aakkostossa!), jotta sen rakenne tulisi helpommin näkyviin. Niinpä, esimerkiksi •

(ab)2 ba3 = ababbaaa • •

ja

abaaabaabb = (abaa)(abaa)(bb) = (abaa)2 b2 .

Sana w = abbababba on palindromi. Sana w = aaabaaaba on primitiivinen, mutta sana v = abaabaaba ei ole, sillä v = (aba)3 . ⊓ ⊔

Lause 1.1 Olkoot u, v, w ∈ Σ ∗ sanoja aakkostossa Σ . Tällöin (i) w = uv =⇒ |w| = |u| + |v| , (ii) |wk | = k · |w| . ⊔ Todistus. Harjoitus. ⊓

Esim. 1.4

On selvää, että |wR | = |w|, ja että kaikille sanoille w ja v , |wv| = |vw|. Niinpä ⊔ esimerkiksi |wvwR v 3 w| = 3 · |w| + 4 · |v|. ⊓

Lause 1.2 Olkoot u, v, w, z ∈ Σ ∗. Tällöin (i) uw = vw =⇒ u = v ja wu = wv =⇒ u = v , (ii) uw = vz =⇒ joko u ≤ v tai v ≤ u , (iii) uw = vz ja |u| = |v| =⇒ u = v, w = z . Todistus. Harjoitus. ⊓ ⊔

4

1 Johdanto

Esim. 1.5

Sanoja käytetään esimerkiksi seuraavasti.

Musta-valko kuva, joka koostuu n × n pikselistä, voidaan koodata binäärisanaksi w ∈ {0, 1}∗ , jonka pituus on n2 . Sanan w = a1 a2 . . . an2 kirjain ai on 1 vain jos vastaava pikseli on päällä (valkoinen). Koodauksen voi tietysti tehdä usealla eri tavalla. Ohessa n = 3, ja w = 001010110 kun kuva luetaan vasemmalta oikealle ja ylhäältä alas. Samoin tapahtumajonoja voidaan kuvata sanoin. Tällöin sanassa w = a1 a2 . . . an kirjain ai tarkoittaa, että hetkellä t = i on tapahtuman a = ai vuoro. Esimerkiksi sana w = 4216632 voi kertoa nopanheiton silmäluvut seitsemän peräkkäisen heiton jälkeen. Nopan aakkosto ⊔ on {1, 2, 3, 4, 5, 6}. ⊓

Kielet Kun Σ on aakkosto, ovat Σ ∗ :n osajoukot kieliä. Merkitään P (U ) = {L | L ⊆ U }, eli P (U ) on joukon U kaikkien osajoukkojen joukko. Näin ollen L on aakkoston Σ kieli, jos L ∈ P (Σ ∗ ).

Esim. 1.6

Kun Σ = {a, b}, niin joukot L = {ε, ab, aab, aaab, aaaab} ja K = {abn | n = 0, 1, . . . }

ovat kieliä aakkostossa Σ . Tässä K on ääretön kieli, jonka alkiot ovat kaikki tarkalleen muotoa abb . . . b olevat sanat (mukaanlukien sana a). ⊓ ⊔ Kullekin kielelle L määritellään

Kleenen sulkeumat,

L∗ = {u1 u2 . . . un | n ≥ 0, ui ∈ L}, L+ = {u1 u2 . . . un | n ≥ 1, ui ∈ L}.

Nämä poikkeavat toisistaan korkeintaan tyhjän sanan osalta. (Valittaessa määritelmässä n = 0, niin todetaan että välttämättä ε ∈ L∗ , mutta L+ sisältää tyhjän sanan vain jos ε ∈ L.) Edellä olevista kielistä L∗ ja L+ käytetään myös nimityksiä Kleenen tähti (tai iteraatiosulkeuma) ja Kleenen plus (tai katenaatiosulkeuma).

Esim. 1.7

Olkoon aakkostona Σ = {a, b}.

Kun L = {ab, bb} ⊆ {a, b}∗, niin L∗ = {ε, ab, bb, abab, abbb, bbab, ababab, . . .} ja L+ = L∗ \ {ε}. • Kun taas L = {a, aa}, niin L∗ = {an | n ≥ 0}, eli L∗ = {a}∗ . ⊓ ⊔ •

Joukko-opillisia operaatioita Kielille voidaan luonnollisesti määritellä kaikki joukko-opilliset operaatiot: K ∪L ∗

Σ \L

unioni, komplementti,

K ∩L L\K

leikkaus, erotus.

1 Johdanto Lisäksi määritellään kahden kielen L ja K

5

tulo niiden sanojen tulojen unionina:

KL = {uv | u ∈ K, v ∈ L} .

Erityisesti, L2 = LL, ja induktiivisesti edeten, Ln+1 = Ln L. Erikoistapauksena vielä, L0 = {ε}. Niinpä Ln = {u1 u2 . . . un | ui ∈ L} . Kirjoitetaan usein yksisanaiselle kielelle L = {w} lyhyemmin L = w tai L = (w).

Esim. 1.8

(i) Voidaan kirjoittaa {w}∗ = w∗ = (w)∗ . Huomaa kuitenkin, että esimerkiksi aba tarkoittaa kieltä ab(a∗ ) = {abai | i ≥ 0} eikä suinkaan kieltä (aba)∗ = {(aba)i | i ≥ 0}. (ii) {aba, ab} · {b, ab} = {abab, abaab, abb}. (iii) Olkoot L = {an bn | n ≥ 1} ja K = b∗ . Tällöin ∗

LK = {an bm | m ≥ n ≥ 1}

ja

KL = {bj an bn | j ≥ 0, n ≥ 1} .⊓ ⊔

Seuraavat tulokset ovat ilmeisiä tai harjoituksia.

Lause 1.3 Kaikille kielille (i) (ii) (iii) (iv)

L, K, M on voimassa

S

ja

L∗ = n≥0 Ln (LK)M = L(KM ) , L(K ∪ M ) = LK ∪ LM (L∗ )∗ = L∗ L∗ = L∗

ja ja

L+ =

S

n≥1

Ln ,

(K ∪ M )L = KL ∪ M L , L∅ = ∅ = ∅L .

Morsmit Olkoot Σ ja ∆ kaksi aakkostoa (mahdollisesti samat). Tällöin kuvaus h : Σ ∗ → ∆∗ on

morsmi, jos se toteuttaa seuraavan ehdon h(uv) = h(u)h(v)

kaikilla u, v ∈ Σ ∗ .

Morsmi tulee täysin määrättyä, kun tunnetaan miten se kuvaa kirjaimet, koskapa jos w = a1 a2 . . . an ∈ Σ ∗ , niin h(ε) = ε

ja h(w) = h(a1 )h(a2 ) . . . h(an ).

Lisäksi, mikäli on annettuna kuvaus h : Σ → ∆∗ , joka kuvaa jokaisen kirjaimen a ∈ Σ sanaksi h(a) ∈ ∆∗ , niin h laajenee yksikäsitteisesti morsmiksi h : Σ ∗ → ∆∗ edeltävän kaavan mukaisesti. Olkoot h : Σ ∗ → ∆∗ morsmi, ja L ⊆ Σ ∗ , K ⊆ ∆∗ kieliä. Kielen L mornen kuva ja kielen K käänteismornen kuva määritellään seuraavasti: h(L) = {h(u) | u ∈ L} , h

−1

(K) = {v | h(v) ∈ K} .

6

1 Johdanto

Esim. 1.9

sesti,

Morsmi h : {a, b, c}∗ → {a, b}∗ , joka tulee määrätyksi kirjainten kuvilla oheih(a) = aba, h(b) = ε, h(c) = bb,

toteuttaa seuraavat yhtäsuuruudet: h(ac) = ababb = h(abbbbbc). Kun L = {bbaba}, niin h−1 (L) = b∗ cb∗ ab∗ (= {bi cbj abk | i, j, k ≥ 0}) . ⊓ ⊔

Morsmi siirtää mukaellen sanan rakenteen kuvasanaan, ja kielen rakenteen kuvakieleen. Voidaan myös ajatella, että morsmi luo kirjaimille sisäisen rakenteen, tai että se tarkentaa sen objektin ominaisuuksia, jota kirjain esittää. Esimerkiksi hahmontunnistuksessa1 on annettuna sana eli hahmo p ∈ Σ ∗ , ja kysytään sisältääkö sana w ∈ ∆∗ hahmon p: onko olemassa w:n osasana u ja morsmi h : Σ ∗ → ∆∗ niin, että h(p) = u. Hahmontunnistuksen motivaatio on käytännön ongelmissa kuten kuvien (Röntgenkuvien, digitalisoitujen kuvien) selventämisessä ja pakkaamisessa, tai digitalisoidun puheen virheenkorjauksessa (jolloin epämääräistyneet sanat yritetään hahmottaa oikeiksi sanoiksi). Tunnetusti aivot suorittavat sekä visuaalista että verbaalista hahmontunnistusta. Erityisiä automaatteja ja kielioppeja käytetään hahmontunnistuksessa koodausteorian ja monien muiden matemaattisten työvälineiden ohella. Sanojen kombinatoriikka hahmontunnistuksessa kuuluu teorian perusteisiin, ja jo näissä perusteissa tavataan hyvin vaikeita ongelmia.

Esim. 1.10

Kun p = aa, niin w ∈ ∆∗ sisältää hahmon p tarkalleen silloin kun sillä on osasana, joka on neliö u2 . Esimerkiksi, w = abacacb sisältää hahmon p, koskapa w = ab · (ac)2 · b (ja siten h(a) = ac, h(b) = b, h(c) = c on vaaditunlainen morsmi). Toisaalta w = abacabca on neliövapaa, eli se ei sisällä hahmoa p. Helppona harjoituksena todetaan: Jos |∆| = 2, niin on vain äärellinen määrä sanoja, jotka välttävät hahmon p = a2 . Sensijaan, jos |∆| ≥ 3, niin on olemassa äärettömän monta neliövapaata sanaa w ∈ ∆∗ . Itseasiassa Thue konstruoi vuosisadan alussa äärettömän neliövapaan sanan ω = a1 a2 a3 . . . aakkostossa ∆ = {a, b, c}. Tätä varten määritellään Thue-Morse morsmi ehdoista h(a) = abc ,

h(b) = ac ,

h(c) = b .

Nyt sanat h(a), h2 (a), . . . , hi (a), . . . ovat neliövapaita: abc, abcacb, abcacbabcbac, . . . . (Har⊔ joitus: induktiolla.) ⊓

Konstruktioista Automaatteja koskeva ongelmanratkaisutilanne koostuu tavallisesti konstruktiosta ja to(vrt. ohjelma  sen oikeellisuuden todistaminen, geometrinen ratkaisu  sen todistus). Tietysti on hyvä olla myös ongelma. Ihannetapauksessa

distuksesta

(i) konstruktio-osassa etsitään ja esitetään ratkaisu, joka tällä kurssilla on yleensä algoritmi, automaatti, tai kielioppi, ja 1

pattern re ognition

1 Johdanto

7

(ii) todistusosassa osoitetaan pitävästi (käyttäen induktiota tai muita matemaattisia päättelysääntöjä), että konstruoitu ratkaisu on ongelman vaatima ratkaisu, eli että se toimii oikein. Usein on mahdollista (ja aina hyvin suotavaa), että ongelma palautetaan tuttuun ongelmaan ja sen tunnettuun ratkaisuun, jolloin konstruktio-osa saattaa jäädä pois ja todistusosa voi olla helppo. Ratkaisun oikeellisuuden tarkempi todistaminen vaatii monasti pitkän `teknisen' esityksen. Pahimmassa tapauksessa pitkä tekninen todistus ei anna ratkaisun toimivuudesta selkeää kuvaa. Niinpä (tällä kurssilla) ongelmanratkaisu koostuu yleensä konstruktiosta ja perusteluista: konstruktioon liitetään tarpeellisen yksityiskohtainen selvitys sen toimivuudesta.

2

Äärelliset automaatit

DFA Äärellinen automaatti koostuu syöttönauhasta, lukupäästä ja keskusmuistista. Keskusmuisti on äärellinen joukko sisäisiä tiloja. Automaatti toimii seuraavasti:

Alku: Automaatti on alkutilassa qA , ja lukee syöttönauhan ensimmäistä kirjainta vasemmalta lukien. • Askel: Automaatti siirtyy uuteen tilaan ja lukemaan seuraavaa kirjainta syöttönauhalta. Uusi tila riippuu vain luetusta kirjaimesta ja vanhasta tilasta. • Loppu: Kun annettu sana on kokonaan luettu, automaatti hyväksyy sen vain jos se on lopputilassa. •

...

✻

q0 q1 qk ✙ q2 gi ...

Formaalisemmin äärellinen (Q, Σ, δ, q0 , F ) , missä • • • • •

deterministinen automaatti eli DFA1

on viisikko A =

Q on äärellinen joukko tiloja, Σ on syöttöaakkosto, δ : Q × Σ → Q on transitiofunktio, q0 on alkutila, ja F on lopputilojen joukko.

Transitiofunktio δ määrää A:n askeleet. Jos δ(q, a) = p, niin A ollessaan tilassa q lukemassa kirjainta a, siirtyy tilassa p lukemaan seuraavaa kirjainta. Automaatin A toimintaa kuvataan sen tilagraalla, missä on nuoli a

q −−→ p

tilasta toiseen jos ja vain jos δ(q, a) = p. Lisäksi, asetetaan nuoli johtamaan alkutilaan, ja johtamaan pois jokaisesta lopputilasta: −→ qA 1

deterministi nite automaton

q −→

(q ∈ F ) .

2 Äärelliset automaatit

9

Kun A on DFA, voidaan kirjoittaa myös A = (QA , ΣA , δA , qA , FA ) ,

jolloin koko viisikkoa ei tarvitse erikseen esitellä, koska indeksi kertoo mihin automaattiin komponentti kuuluu. Kuvaus δ = δA laajennetaan kuvaukseksi δ : Q × Σ ∗ → Q ehdoista δ(q, ε) = q ,

δ(q, wa) = δ(δ(q, w), a)

kaikille sanoille w ∈ Σ ∗ ja kaikille kirjaimille a ∈ Σ . Tällöin δ kertoo miten DFA A toimii syöttösanoilla, toisin sanoen, δ(q, w) on se tila, johon A päätyy lähtiessään lukemaan sanaa w tilassa q . a Jos w = a1 a2 . . . an ja δA (qi , ai ) = qi+1 kullakin i = 1, 2, . . . , n, eli qi −−i→ qi+1 , niin δ(q1 , w) = qn+1 . Tämä voidaan esittää myös graasesti: w

q1 −−→ qn+1 .

Sanotaan, että automaatin A lasku tilasta q1 tilaan qn+1 on jono yhteensopivia transitioita: a

a

a

n 2 1 → qn+1 . → . . . −−− → q2 −−− q1 −−−

Jos edellä q1 = qA on alkutila ja qn+1 ∈ F jokin lopputila, on lasku DFA:n A tunnistama eli hyväksymä kieli on

hyväksyvä.

∗ L(A) = {w ∈ ΣA | δA (qA , w) ∈ FA } .

Kieli L on säännöllinen eli tunnistuva2 , jos on olemassa DFA A, jolla L = L(A). Erityiε sesti, jos alkutila qA on myös lopputila qA ∈ F , niin tyhjä lasku qA −−→ qA on hyväksyvä, ja tässä tapauksessa ε ∈ L(G).

Esim. 2.1

Oheisen DFA:n A alkutila on q1 (= qA ) ja sillä on vain yksi lopputila, FA = {q4 }. b a b a Lasku P = q1 −−→ q3 −−→ q2 −−→ q2 −−→ q4 on hyväksyvä, ja siten abab ∈ L(A). Tässä esimerkissä on helpohkoa todeta, että L(A) = {aa} ∪ {aban b | n ≥ 0} ∪ {ban b | n ≥ 0}

eli lyhyemmin säännöllisenä ilmauksena L(A) = aa ∪ (ab ∪ b)a∗ b . Huomaa, että tila q5 on roskatila, johon jouduttaessa ei ole pääsyä lopputilaan. ⊓ ⊔ ✲ q1 a ❄ q3 2

regular, re ognizable

b

b a

✲ q2 a ✒ ❦ b

q5

✒ ❦ ❄ a, b ✲ q4✲

a, b

10

2 Äärelliset automaatit

FA eli yleistetty äärellinen automaatti Deterministisessä automaatissa A jokaiselle sanalle on tarkalleen yksi lasku alkutilasta lähtien. (Toki kaikki sanat eivät välttämättä johda lopputilaan). Tässä mielessä DFA on aina täydellinen. Jättämällä joitain transitioita pois (sellaiset jotka eivät koskaan voi johtaa lopputilaan) saadaan `epätäydellinen' eli osittainen DFA.

Esim. 2.2 Kun edeltävästä esimerkistä jätetään roskatila q5 ja sitä koskettavat transitiot pois, saadaan osittainen DFA, jonka toiminta on tarkalleen sama kuin alkuperäisen, eli se ⊔ hyväksyy saman kielen. ⊓ Epädeterministisyys sallii vaihtoehtoja niin, että sanalle voi olla useita erilaisia laskuja, joista joku tai jotkut ovat hyväksyviä. Yleistetty äärellinen automaatti eli FA on viisikko A = (Q, Σ, σ, I, F ), joka eroaa DFA:n määrittelystä sikäli, että I on alkutilojen joukko ja σ on äärellinen moniarvoinen kuvaus, σ : Q × Σ ∗ → P (Q) . Edellä `äärellinen' tarkoittaa, että σ on määritelty (eli σ(q, w) 6= ∅) vain äärellisen monelle parille (q, w). Tässä σ = σA on transitiorelaatio ja p ∈ σ(q, w) on A:n transitio. Kutakin FA:ta vastaa myös tilagraa, missä transitio p ∈ σ(q, w) esitetään nuolena w

q −−→ p .

Esim. 2.3

Oheisella FA:lla on kaksi lopputilaa q1 ja q4 . Ainut alkutila q1 on siis myös lopputila. Tämä automaatti hyväksyy sanan w = aabbb käyttäen polkua b b ab a ⊔ q1 −−→ q3 −−→ q1 −−→ q2 −−→ q4 . ⊓

✲ q1✻

b

✲ q2

✣ a

ab q3

❦

ba

b

✢ a

❄ ✲ q4✲

FA:ssa voi siis olla useita alkutiloja, ja transitiorelaatio σ voi lukea sanoja (ei vain kirjaimia) ja kuvata saman sanan w samassa tilassa useampaan eri tilaan. Tämä yleistys ε sallii myös tapauksen, jossa luetaan tyhjä sana siirryttäessä tilasta toiseen: q −−→ p. FA A:n hyväksymä kieli on ∗ L(A) = {w ∈ ΣA | on jokin hyväksyvä lasku sanalle w}

eli w ∈ L(G) jos ja vain jos on olemassa jono transitioita (i = 0, 1, . . . , n) qi+1 ∈ σA (wi , qi )

(w = w0 w1 . . . wn )

alkutilasta q0 ∈ IA lopputilaan qn+1 ∈ FA . FA A = (Q, Σ, σ, I, F ) on epädeterministinen äärellinen jokainen transitio p ∈ σ(q, w) lukee yhden kirjaimen, eli w ∈ Σ .

automaatti eli NFA, jos

2 Äärelliset automaatit

NFA

7→

11

DFA

Osoitetaan, että NFA ei ole tunnistamiskykyisempi kuin DFA, eli epädeterministisyys ei kasvata hyväksyttyjen kielten perhettä. Todistus tapahtuu osajoukkokonstruktiolla, missä uuden deterministisen automaatin tilat ovat annetun epädeterministisen automaatin tilojen kaikki osajoukot. Todetaan ensin, että jokaisen FA:n A transitiorelaatio σA yleistyy kaikille sanoille w ∈ ∗ ΣA ehdosta p ∈ σA (q, w)

jos ∃qi+1 ∈ σA (qi , wi ) (kaikille i = 1, 2, . . . n) : q = q1 , p = qn+1 , w = w1 w2 . . . wn

eli jos on olemassa jokin sanan w lukeva lasku tilasta q tilaan p: wn−1

w

w

w

n 2 1 → p. → . . . −−−−−→ qn −−− → q2 −−− q −−−

Lause 2.1 Jokaiselle NFA:lle

A on konstruoitavissa DFA B siten, että L(A) = L(B), eli jokainen NFA hyväksyy säännöllisen kielen.

Todistus. Olkoon A = (Q, Σ, σ, I, F ) NFA. Sen transitiorelaatio σ voidaan laajentaa funktioksi tilojen osajoukoille σP : P (Q) × Σ → P (Q) määrittelemällä σ P (U, a) =

[

σ(q, a)

q∈U

eli kokoamalla yhteen kaikki ne tilat joihin päästään tiloista q ∈ U lukemalla kirjain a. Graasesti tämä ilmaistaan seuraavasti: a

U −−→ V ,

a

missä V = {p | q −−→ p, jollain q ∈ U } .

Olkoon B = (P (Q), Σ, σ P , qB , FB ), missä qB = I

ja FB = {U | U ∩ F 6= ∅} .

Nyt B on DFA, sillä σ P on funktio. Mitä ilmeisemmin transitiofunktio σ P laajenee kaikille sanoille w seuraavasti: [ σ P (U, w) = σ(q, w) q∈U

eli

w

U −−→ V ,

w

missä V = {p | q −−→ p, jollain q ∈ U } .

Lisäksi w ∈ L(B) ⇐⇒ ⇐⇒ ⇐⇒

Tämä todistaa väitteen. ⊓ ⊔

σ P (qB , w) = V ∈ FB ∃q ∈ I, p ∈ FA : p ∈ σ(q, w) w ∈ L(A) .

12

2 Äärelliset automaatit

Esim. 2.4

Olkoon A vasemmanpuoleinen NFA. Siitä konstruoituva DFA on oikealla, missä esimerkiksi q12 tarkoittaa tilaa {q1 , q2 }.

a

b

✢ ✲ q1✻

a

❑ b

a

✲ q2 ✸

q3 ✢

✰ ✲ q✻ 1 ⑥

a

a, b

s ✲ ✲ q12 a ❦ ❃ ✣ ■ a b a q13✲ a a

b

b

b q3 ✰

a

b

s ❄ ∅ ❦ a

✢ q23 ✸ b

q2

b

✲q123✲ ✣ b

Tässä DFA:ssa on tiloja, joihin ei koskaan päästä alkutilasta. Kun nämä tilat (q3 , q2 ja q13 ) poistetaan saadaan (täydellinen) DFA, joka tunnistaa saman kielen. DFA sisältää roskatilan ∅, ja kun sekin poistetaan, saadaan osittainen DFA, joka hyväksyy saman kielen kuin alkuperäinen NFA. Lopulta on päästy suhteellisen pieneen deterministiseen automaattiin. ⊓ ⊔ ✲ q1✻

a

b

Esim. 2.5

✲ q12✲ a ✒ ✣ ❦

a

s ✛q123✛

a

b ✢ q23

b

Olkoon L = L(A) säännöllinen kieli, missä A on DFA. Osoitetaan, että HL = {u | uu ∈ L}

on myös säännöllinen. Tämän näyttämiseksi riittää konstruoida NFA B , joka hyväksyy kielen HL . Nyt u ∈ HL jos ja vain jos A:lla on hyväksyvä lasku u

u

qA −−→ s −−→ q ,

missä q ∈ FA ja s ∈ QA . Automaatin (NFA) B tilat olkoot QB = QA × QA × QA .

Näin ollen jokainen B :n tila on muotoa (q, s, p).

2 Äärelliset automaatit

13

B :n alkutilat ovat IB = {(qA , s, s) | s ∈ QA } . u

u

Tässä (qA , s, s) on `arvaus', että A:ssa on laskut qA −−→ s ja s −−→ q jollekin A:n lopputilalle q . B :n transitiot tarkistavat, että `arvaukset' tehdään oikein: a

(q1 , s, p1 ) −−→ (q2 , s, p2 )

q2 ∈ δA (q1 , a) ja p2 ∈ δA (p1 , a) .

⇐⇒

Näin B simuloi A:ta kahteen kertaan samanaikaisesti: `oikealla' syötöllä u ja `kuvitellulla' jatko-osalla u. B :n lopputilat tarkistavat loput `arvausten' oikeellisuudesta: FB = {(s, s, q) | s ∈ QA , q ∈ FA } .

Lopputilan (s, s, q) kaksi ensimmäistä komponenttia (s, s) tarkistavat, että alkuperäisen u arvauksen (qA , s, s) toinen osa (eli s) oli tehty oikein, eli että qA −−→ s. Kolmas komponentti u q tarkistaa, että A siirtyy todella tilasta s lopputilaan luettuaan sanan u, eli s −−→ q ∈ FA . ⊓ ⊔

FA

7→

NFA (7→ DFA)

Osoitetaan sitten, että FA ei ole tunnistuskykyisempi kuin DFA. Tähän riittää näyttää, että jokaiselle FA:lle on konstruoitavissa ekvivalentti NFA (joka hyväksyy saman kielen).

Lemma 2.1. Jokaiselle FA:lle A on olemassa FA B , jolla on vain yksi alkutila ja jolle on voimassa L(A) = L(B).

Todistus. Olkoon q uusi tila, joka valitaan uuden automaatin alkutilaksi. Sitten asetetaan ε transitiot q −−→ p kullekin vanhan automaatin alkutilalle p. On selvää, että hyväksytty kieli ⊔ ei tästä miksikään muutu. ⊓

Lause 2.2 Jokainen yleistetty äärellinen automaatti hyväksyy säännöllisen kielen. Todistus. Olkoon A = (Q, Σ, σ, {qA }, F ) FA, jolla on vain yksi alkutila. Yritetään poistaa siitä kaikki epäkelvot transitiot

ε

(1) q −−→ p w

(2) q −−→ p

(p 6= q) , (|w| > 1) .

Jokainen tyypin (2) transitio, missä w = a1 a2 . . . an (n > 1), korvataan transitioilla: a

a

a

n 2 1 → p, → q2 , . . . , qn−1 −−− → q1 , q1 −−− q −−−

missä tilat qi ovat uusia, qi ∈ / Q, ja vain tälle poistettavalle transitiolle tarkoitettuja. Näin päästään eroon pitkistä transitioista: a

a

a

n 2 1 → p. → . . . −−− → q1 −−− q −−−

Edeltävän nojalla voidaan olettaa, että A:ssa ei ole pitkiä transitioita. Olkoon B NFA, jolla on samat tilat kuin A:lla, ja jonka alkutilojen joukkona on

14

2 Äärelliset automaatit ε

IB = {p | qA −−→ p} ,

lopputilojen joukkona F , ja transitioina a

p ∈ σB (q, a) ⇐⇒ A:lla on lasku q −−→ p .

Tällöin L(B) = L(A). Tämän näyttämiseksi olkoon w = a1 a2 . . . an . Ensinnäkin, jos w ∈ L(B), on B :llä lasku an a2 a1 → qn+1 , → . . . −−− → q2 −−− q1 −−− (2.1) missä q1 ∈ IB ja qn+1 ∈ F . Tällöin A:lla on laskut a

ε

1 −− → q2 , qA −−→ q1 −

a

a

(2.2)

n 2 → qn+1 , → q3 , . . . , qn −−− q2 −−−

ja siten se hyväksyy sanan w. Näin ollen L(B) ⊆ L(A). Toisaalta, jos w ∈ L(A), on A:lla laskut kuten (2.2):ssa, ja siten B :llä on lasku kuten (2.1):ssä. Siten myös L(A) ⊆ L(B), ja yhtäsuuruus seuraa. Käsittely palauttaa FA:n NFA:ksi, ja NFA voidaan palauttaa DFA:ksi Lauseen 2.1 mu⊔ kaisesti. Tästä väite seuraakin. ⊓

Esim. 2.6

Olkoon A oheisen kuvan vasemmanpuoleinen FA. Tarkastelemalla todetaan, että IB = {q1 , q2 , q3 }, eli kaikki muut paitsi q4 ovat B :n alkutiloja. B :n ainukaisena lopputilana ⊔ on q4 . Edeltävän todistuksen NFA on oheisena. ⊓

ε

q2

✲ q3

✻

✲ q1

✲ q3 a, b ✣

▼ a

ε

✲ q2

b ❦

b ❘ ❄ s q4✲

b b ✲ q1

❦

b

✢ a, b s ◆q ✲ 4

b

b

Siis DFA:n yleistykset (FA:t) eivät kasvata automaattiluokan hyväksymää kieliperhettä, ja niinpä, epädeterministisyys ei ole deterministisyyttä ilmaisuvoimaisempi tässä automaattien luokassa. Toki, FA on `tehokkaampi' kuin DFA siinä mielessä, että kielen hyväksyminen DFA:lla saattaa pahimmassa tapauksessa vaatia automaatilta eksponentiaalisesti enemmän tiloja. (Siis jos FA:lla A on n tilaa, niin sitä simuloivalla DFA:lla voi olla jopa 2n tilaa).

Esim. 2.7

Katsotaan vielä, miten DFA piirtää vapaa-aikanaan aakkoston {u, r, ℓ} sanoja. Tulkitaan u = ylös, r = oikealle ja ℓ = vasemmalle yksikköjanan verran (esim. 10 pikseliä). Oheisena on Fibona

in automaatti, joka piirtää polkuja tasoon. Tämän automaatin hyväksymien pituutta n olevien sanojen lukumäärä on n:s Fibona

in luku f (n), eli luku joka saadaan rekursiivisesti yhtälöstä f (n) = f (n − 1) + f (n − 2) kun alkuarvoina ovat f (0) = 1 ja f (1) = 2.

s u ✲ q1 ❄❦

ℓ r

s

q2 u ❄❦

2 Äärelliset automaatit

15

Näitä DFA:n taipumuksia voidaan kehittää lisäämällä esimerkiksi turtle-käskyjä, jotka sisältävät paitsi viivan suuntia, myös muita piirtämiseen liittyviä käskyjä  `('= nosta kynä, `)' = laske kynä, • = piirrä piste. Tällöin käskystä •urd•(uuℓ)•d automaatti piirtää laaman kuvan (missä d = alas). Yleistettynä ja iteratiivisesti automaatit pystyvät piirtämään fraktaalisia kuvioita.  Hieman monipuolisemmin (mukaanlukien fraktaaliset kuviot) voidaan piirtää Lindenmayerin ⊔ systeemien avulla, jotka saadaan iteratiivisesti morsmeja käyttäen. ⊓

Sulkeumia Tässä kappaleessa säännöllisten kielten perheen sulkeuma ominaisuuksia. Todistukset esitetään demonstraatioissa.

Lause 2.3 Säännöllisten kielten perhe on suljettu operaatioihin: ∪, ∩, r. Todistus. Harjoitus. ⊓ ⊔

Lause 2.4 Säännöllisten kielten perhe on suljettu komplementtiin nähden. Lause 2.5 Säännöllisten kielten perhe on suljettu operaatioihin: ·, + , ∗. Todistus. Harjoitus. ⊓ ⊔

Lause 2.6 Säännöllisten kielten perhe on suljettu morsiin ja käänteismorsiin kuviin. ⊔ Todistus. Harjoitus. ⊓

Rationaalisuus ja Kleenen lause Määritellään (aakkoston Σ ) säännölliset eli rationaaliset na, joka toteuttaa seuraavat sulkeumaehdot: • • •

ilmaisut3 pienimpänä joukko-

∅, ε ja a ovat rationaalisia ilmaisuja kaikilla a ∈ Σ , jos R1 ja R2 ovat rationaalisia ilmaisuja, samoin ovat (R1 ∪ R2 ) ja (R1 · R2 ), jos R on rationaalinen ilmaisu, samoin on (R)∗ .

Kaikissa rationaalisissa ilmaisuissa esiintyy vain sanoja, tuloja, tähtiä ja unioneita sekä hyvin muodostettuja sulkupareja. Erityisesti, joukkosulkeita ja leikkauksia ei esiinny. Rationaalisista ilmaisuista voi jättää sulkeita pois, jos monimielisyyttä ei synny, jolloin operaatioiden sitovuusjärjestys korvaa sulkeiden tarpeen. Kieli L ⊆ Σ ∗ on rationaalinen, jos sitä esittää rationaalinen ilmaisu. Niinpä, rationaalisten kielten perhe on pienin kieliperhe, joka sisältää äärelliset kielet, ja on suljettu operaatioihin ·, ∪ ja ∗ nähden. Seuraava Kleenen lause on automaattien teoria yksi tärkeimmistä tuloksista.

Lause 2.7

L ⊆ Σ ∗ on säännöllinen jos ja vain jos se on rationaalinen.

Todistus. Sivuutetaan. ⊓ ⊔ 3

regular, rational expression

16

2 Äärelliset automaatit

Pumppauslemma Kleenen lauseen nojalla voidaan päätellä, että tietyt kielet eivät ole säännöllisiä. Nimittäin, jos L on ääretön säännöllinen kieli, niin sillä on säännöllinen ilmaisu, jossa esiintyy ainakin yksi tähti. Tämä seuraa siitä, että muut rationaaliset operaatiot ∪ , · eivät pysty tuottamaan äärellisistä kielistä äärettömiä.

Esim. 2.8

Edellisen huomion avulla voidaan osoittaa, että kieli L = {an bn | n ≥ 1} ei ole säännöllinen, sillä ∗ joko sekoittaisi a:n ja b:n järjestyksen tai lisäisi liiallisesti jompaa kumpaa kirjainta. ⊓ ⊔ Seuraavat säännöllisten kielten pumppauslemmat parantavat oleellisesti edeltävää tulosta. Riittää todistaa jälkimmäinen voimakkaampi tulos.

Lause 2.8 Jokaiselle säännölliselle kielelle L on olemassa vakio n, jolle: jos w ∈ L, |w| ≥ n, niin w voidaan jakaa tekijöihin w = xyz siten, että y 6= ε ja xy ∗ z ⊆ L. Lause 2.9 Jokaiselle säännölliselle kielelle L on olemassa vakio n, jolle: jos w = w1 uw2 ∈ L, missä |u| ≥ n, niin osasanalla u on tekijöihinjako u = xyz siten, että 1 ≤ |y| ≤ n ja w1 xy ∗ zw2 ⊆ L .

Erityisesti n:ksi käy L:n hyväksyvän DFA:n (tai NFA:n) tilojen lukumäärä. Todistus. Olkoon A n-tilainen DFA, joka hyväksyy kielen L. Olkoon u = a1 a2 . . . an jokin

sanan w ∈ L = L(A) pituutta n oleva osasana, w = w1 uw2 ∈ L(A). Tällöin A:ssa on hyväksyvä lasku sanalle w: w

w

u

2 1 →p → q1 −−→ qn+1 −−− qA −−−

missä keskimmäinen osalasku a

a

a

n 2 1 → qn+1 → . . . −−− → q2 −−− q1 −−−

sisältää n + 1 kappaletta tiloja. Siten tässä osalaskussa on vähintään kaksi samaa tilaa, sanokaamme qi = qj (i < j ). Valitaan y = ai . . . aj−1 , jolloin edellä on osalasku y

qi −−→ qj .

Kun u = xyz , niin

w x

y

zw

2 → p. qA −−−1−→ qi −−→ qj −−−−

Koska tässä qi = qj , niin keskimmäistä osalaskua y :lle voidaan toistaa miten monta kertaa tahansa tai jättää se kokonaan käyttämättä, ja näin saatavat laskut ovat edelleen hyväksyviä. Saadaan lauseen väite: w1 xy t zw2 ∈ L(A) kaikilla t ≥ 0. y qA

w1 x ✲ qi = qj

zw2

✲ p

Yleisemmin, jos edellä |u| ≥ n, niin sillä on osasana, jonka pituus on tarkalleen n, ja edeltävä päättely todistaa väitteen myös tällaisille pidemmille osasanoille u. ⊓ ⊔

2 Äärelliset automaatit

17

Esim. 2.9

Kieli L = {an bn | n ≥ 0} ei ole säännöllinen. Tämän toteamiseksi tehdään vastaoletus, että olisi olemassa L:n hyväksyvä DFA A, jolla on n tilaa. Nyt sana w = an bn ∈ L, ja siten pumppauslemman nojalla osasanalla an on osasana y = at (t ≥ 1) siten, että w = xyz ja xz ∈ L (missä y on pumpattu tyhjiin, xz = xy 0 z ). Mutta koska xy on sanan w preksi, niin x = ar (r ≥ 0) ja z = as bn (s ≥ 0), jolloin xz = ar+s bn ∈ L implikoi ⊔ että r + s = n, eli t = 0, mikä on ristiriita. ⊓

Esim. 2.10

n

Kieli L = {a2 | n ≥ 1} ei ole säännöllinen. Tehdään jälleen vastaoletus, että on n-tilainen DFA A, jolla L = L(A). Pumppauslemman nojalla, kun k = 2n (varmasti 2n tarpeeksi suuri), niin a2 = xyz ja xy i z ∈ L kaikilla i ≥ 0. Edellä y = aj (j > 0) ja t |y| ≤ n, eli j ≤ n. Lisäksi, xz = a2 jollain (t < 2n). Mutta |xz| = 2t = 22n − j ja siten 2t (22n−t − 1) = j ≤ n, mistä seuraa, että 2t ≤ n. Lopulta 22n = 2t + j ≤ 2n, eli 22n−1 ≤ n, mikä on mahdotonta. ⊓ ⊔

Esim. 2.11

Yksisanainen kieli L = {a1 a2 . . . an } on säännöllinen, ja sen hyväksyvä DFA A sisältää välttämättä ainakin n + 1 tilaa, sillä muutoin pumppauslemma tuottaisi iteraation ⊔ sanan keskelle ja siten ylimääräisiä sanoja kieleen L(A). ⊓ Seuraavassa on esimerkki miten kielen epäsäännöllisyys voidaan palauttaa jo tunnetun kielen epäsäännöllisyyteen. Merkintä |w|a tarkoittaa kirjaimen a lukumäärää sanassa w.

Esim. 2.12

Kieli L = {w ∈ {a, b}∗ | |w|a = |w|b } ei ole säännöllinen. Mikäli L olisi säännöllinen, niin samoin olisi kieli L ∩ a∗ b∗ = {an bn | n ≥ 0}, sillä säännölliset kielet ovat suljettuja leikkaukseen. Tämä on ristiriita ensimmäisen esimerkin kanssa. ⊓ ⊔

Esim. 2.13

Kieli

L = a∗ {an bn | n ≥ 0}b∗

on säännöllinen, vaikka siinä esiintyykin keskellä epäsäännöllinen kieli. Nimittäin L = a∗ b∗ . ⊓ ⊔

Esim. 2.14

Kieli L ⊆ Σ ∗ voi toteuttaa pumppauslemman vaateet olematta säännöllinen. Todetaan tämä vain Lauseen 2.8 tapauksessa. Tarkastellaan kieltä L = {ap bp | p alkuluku } ∪ {ak bm | k 6= m} ,

joka ei ole säännöllinen (kuten on osoitettavissa). Tällöin on olemassa n (nimittäin n = 4) siten, että kaikilla w ∈ L, |w| ≥ n, on tekijöihinjako w = xyz (y 6= ε) jolle xy ∗ z ⊆ L. Kun w = ap bp ∈ L (p on alkuluku), niin yhtä a:ta voidaan vapaasti pumpata, ja saadut sanat ap−1 bp ja ap+i bp (i ≥ 0) ovat edelleen kielessä L, eli ap−1 a∗ bp ⊆ L. Kun w = ak bm , k 6= m, niin joko k > m tai m > k . Oletetaan, että k > m (tapaus m > k on samanlainen). Jos k > m + 1, niin yhtä a:ta voidaan jälleen pumpata vapaasti: ak−1 bm , ak+i bm ∈ L, eli ak−1 a∗ bm ⊆ L. Jos taas k = m + 1, niin pumpataan kahta a:ta: ak−2 bm , ak+2i bm ∈ L, eli ak−2 (a2 )∗ bm ⊆ L. ⊓ ⊔

Algoritmisia ongelmia Pumppauslemmaa voidaan soveltaa myös ratkeavuusongelmiin. Seuraava lause osoittaa, että säännöllisten kielten tyhjyys- ja äärellisyysprobleemat ovat algoritmisesti ratkeavia.

18

2 Äärelliset automaatit

Lause 2.10 Olkoon A n-tilainen DFA (tai NFA). Tällöin L(A) 6= ∅ ⇐⇒ ∃w ∈ L(A) : |w| < n , |L(A)| = ∞ ⇐⇒ ∃w ∈ L(A) : n ≤ |w| < 2n .

Todistus. Ensimmäinen väite on triviaali oikealta vasemmalle. Olkoon sitten w ∈ L(A) lyhin

L(A):n sana. Jos |w| ≥ n, niin pumppauslemman nojalla w = xyz joillekin sanoille x, y, z , missä y 6= ε, ja xy ∗ z ⊆ L(A). Erityisesti xz ∈ L(A), mutta sana xz on lyhyempi kuin w. Tämä ristiriita todistaa ensimmäisen yhtäpitävyyden. ⊔ Toinen väitteistä jää harjoitukseksi. ⊓

Myös säännöllisten kielten ekvivalenssiprobleema on algoritmisesti ratkeava: On algoritmi, joka syötöillä A ja B päättää, ovatko automaatit A ja B ekvivalentit, eli onko L(A) = L(B). Itseasiassa, L(A) = L(B) ⇐⇒ (L(A) r L(B)) ∪ (L(B) r L(A)) = ∅

ja näin tämä ongelma palautuu tyhjyysprobleemaan, sillä oikeanpuolella oleva symmetrinen erotus on säännöllinen kieli, koska se on saatu säännöllisistä kielistä käyttäen erotusta ja unionia. Ekvivalenssiprobleemalle on sievempikin ratkaisu:

Lause 2.11 Olkoot A ja B kaksi DFA:ta (NFA:ta). Tällöin L(A) = L(B) ⇐⇒ ∀w , |w| < |QA | + |QB | : w ∈ L(A) joss w ∈ L(B) .

Todistus. Sivuutetaan. ⊓ ⊔

DFA:n minimointi Lausetta 2.10 voidaan käyttää hyväksi minimoitaessa äärellistä automaattia. Tällä tarkoitetaan, että automaatille etsitään ekvivalentti automaatti, jossa on mahdollisimman vähän tiloja. Yksikäsitteisen minimaalisen DFA:n olemassaolo annetulle säännölliselle kielelle on hyvin voimakas ja käytännöllinen tulos. Sitä sovelletaan yhdessä epädeterminististen automaattien kanssa, koska FA on usein helpommin löydettävissä kuin DFA. Tällöin konstruktioketju on seuraava: Ongelma 7→ FA 7→ NFA 7→ DFA 7→ Minimaalinen DFA , missä viimeinen automaatti on optimaalinen ratkaisu. Olkoon A DFA. Sanotaan, että A:n tila q on saavutettavissa, jos on olemassa ainakin yksi sana w ∈ Σ ∗ niin, että δ(qA , w) = q . Selvästikin, jos A:n tila q ei ole saavutettavissa, niin q ja sitä koskettavat transitiot voidaan poistaa vaikuttamatta hyväksyttyyn kieleen ja A:n täydellisyyteen. Jäljempänä voidaan olettaa, että jokainen A:n tila on saavutettavissa. Seuraavassa oletetaan, että A = (Q, Σ, δ, qA, F ) on täydellinen DFA, ja että jokainen sen tila on saavutettavissa. Määritellään kullekin tilalle q ∈ Q, Lq = {w | δ(q, w) ∈ F }

eli Lq = L(Aq ), missä Aq = (Q, Σ, δ, q, F ) on DFA, jonka alkutilana q on. Sanotaan, että kaksi tilaa p ja q ovat ekvivalentit, mikäli Lp = Lq , ja tällöin merkitään myös p ∼ q .

2 Äärelliset automaatit

Lemma 2.2.

p ∼ q ⇐⇒ δ(p, a) ∼ δ(q, a)

19

kaikilla a ∈ Σ ∪ {ε} , ja siten

p ∼ q ⇐⇒ δ(p, w) ∼ δ(q, w)

(∀w ∈ Σ ∗ ) .

Todistus. Muistetaan, että δ(p, au) = δ(δ(p, a), u) ja δ(q, au) = δ(δ(q, a), u) kaikille a ∈ Σ ∪ {ε} ja u ∈ Σ ∗ . Ensimmäinen väite seuraa näin ollen relaation ∼ määritelmästä. Toinen väite seuraa induktiolla ensimmäisestä. ⊓ ⊔

Sanotaan, että DFA A on

redusoitu, jos sen kaikille tiloille p ja q on p ≁ q.

Lause 2.12 Jokaiselle täydelliselle DFA:lle A on olemassa redusoitu DFA Amin , joka on ekvivalentti A:n kanssa. Todistus. Oletetaan, että A ei ole redusoitu, ja siten sillä on kaksi ekvivalenttia tilaa, p ∼ q . Konstruoidaan uusi automaatti B seuraavasti: (1) Korvataan jokainen transitio δA (q, a) = q ′ transitiolla δB (q, a) = δA (p, a). a

q

✲ q′

q a ❥ ′ p ✯

p

a

✲ p′

p

a

Näin saatu automaatti B on edelleen täydellinen DFA, ja se on selvästi ekvivalentti A:n kanssa, koska p ∼ q . Seuraavaksi konstruoidaan automaatti C : (2) Samaistetaan tilat p ja q uudeksi tilaksi {p, q} niin, että kaikilla a ∈ Σ : kun r 6= p, q , niin δC (r, a) = {p, q} jos δB (r, a) ∈ {p, q} , δC ({p, q}, a) = δA (p, a) jos δB (p, a) ∈ / {p, q} , δC ({p, q}, a) = {p, q} jos δB (p, a) ∈ {p, q} ,

ja muutoin δC (r, a) = δB (r, a). s

a

✲ q

s a ❥p, q c ✯ ❦

c r

b

❄ ✲ p c ❦

r

b

Näin saatu C on täydellinen DFA, ja edelleen ekvivalentti A:n kanssa, sillä p ∼ q . Lisäksi C :ssä on nyt yksi tila vähemmän kuin A:ssa, koska p ja q on samaistettu yhdeksi tilaksi. Toistamalla tätä prosessia niin kauan kuin ekvivalentteja tiloja löytyy, päädytään redusoituun automaattiin Amin , joka on ekvivalentti alkuperäisen A:n kanssa. ⊓ ⊔

20

2 Äärelliset automaatit

Seuraavassa lauseessa `yksikäsitteisyys' tarkoittaa, että automaatti Amin on yksikäsitteinen lukuunottamatta tilojen uudelleennimeämistä.

Lause 2.13 Redusoitu DFA Amin on yksikäsitteinen. Erityisesti, jokaisella säännöllisellä kielellä on yksikäsitteinen redusoitu DFA. Todistus. Tehdään vastaoletus, että on olemassa kaksi ekvivalenttia redusoitua DFA:ta, sanokaamme A ja B . Voidaan olettaa, että QA ∩ QB = ∅. Laajennetaan relaatio ∼ tiloille QA ∪ QB luonnollisella tavalla: p ∼ q ⇐⇒ Lp = Lq . Jos p ∼ q , niin p ∈ QA ja q ∈ QB (tai symmetrisesti, p ∈ QB ja q ∈ QA ), koskapa A ja B ovat oletuksen mukaan redusoituja. Nyt, oletuksen mukaan L(A) = L(B), joten qA ∼ qB . Tarkalleen kuten Lemmassa 2.2, jos p ∈ QA ja q ∈ QB , niin p ∼ q ⇐⇒ δA (p, w) ∼ δB (q, w)

kaikille sanoille w.

Väite: ∀p ∈ QA ∃!q ∈ QB :

p ∼ q.

Kun p ∈ QA , niin on olemassa w siten, että δA (qA , w) = p ja koska L(A) = L(B), niin näillä kielillä on tarkalleen samat preksit ja siten on olemassa q ∈ QB , jolla δB (qB , w) = q . Nyt p ∼ q edeltävän kaavan nojalla. Lisäksi tämä q on yksikäsitteinen, sillä p ∼ q ′ implikoi, että q ∼ q ′ , ja koska B on redusoitu, niin q ′ = q . Näin edeltävä väite on todistettu. Täten automaattien A ja B tilat ovat bijektiivisessä vastaavuudessa, ja jos δA (p, a) = p′ ja p ∼ q , niin δB (q, a) = q ′ , missä siis p′ ∼ q ′ . Mutta tämä tarkoittaa, että A ja B ovat samat automaatit (tilojen nimeämisiä lukuunottamatta). ⊓ ⊔

Esim. 2.15 Edeltävä koskee vain determinististä automaattia.

Epädeterminististä automaatti ei ole aina minimoitavissa. Esimerkiksi kielelle L = {ab, ac, ba, bc, ca, cb} voidaan ⊔ konstruoida kaksi `minimaalista' NFA:ta, joissa on yhtä monta (5) tilaa. ⊓

DFA:ta Amin kutsutaan vastedes (hyväksytyn) kielen Edeltävän nojalla

minimaaliseksi

automaatiksi.

Lause 2.14 Jokaisella säännöllisellä kielellä on yksikäsitteinen minimaalinen automaatti. DFA:ssa kaikki roskatilat ovat ekvivalentteja keskenään, joten minimaalisessa automaatissa Amin on korkeintaan yksi roskatila. Seuraavaa apulausetta tarvitaan ekvivalenttien tilojen etsimisessä. Samaa tulosta käytetään perustyökaluna kun etsitään annetun automaatin Kleenen lauseen mukainen rationaalinen ilmaisu, ts. kun haluataan selvittää annetun automaatin tunnistama kieli.

Lemma 2.3. Olkoot

K ⊆ Σ + ja L ⊆ Σ ∗ säännöllisiä. Tällöin yhtälöllä X = XK ∪ L on yksikäsitteinen ratkaisu X = LK ∗ .

Todistus. Sivuutetaan.

2 Äärelliset automaatit

21

Esim. 2.16 Minimoidaan vasemmanpuoleinen oheinen DFA A. Ensin on löydettävä ekvivalentteja tiloja. Todetaan, että L1 = aL3 ∪ bL2 = L2 , joten 1 ∼ 2. a

5

✲ 6

✣ b

b

✢ ✛3 ✠ ✛ ■ ✣ a

b

a

✢

✣ b

b 2 b ❦ ✻ b

a

a

5

b

a

a

4

❦

✲ 6

❦

b

a

✢ ✛3 ✠ ✣ ■ a

b

a

✢

✲ 1 ✛

a

4

✲ 12 ✛ b ❦

Kun nämä kaksi tilaa samaistetaan, niin tuloksena on oikeanpuoleinen automaatti. Tässä L12 = aL3 ∪ bL12 ja L6 = aL3 ∪ bL6 . Yhtälöllä X = KX ∪ L on yksikäsitteinen ratkaisu (Lemma 2.3), joten L12 = L6 ja siten 12 ∼ 6. Näiden tilojen samaistus tuottaa alla vasemmalla olevan automaatin. Nyt, L4 = aL126 ∪ bL3 = L5 , joten 5 ∼ 4. Samaistettaessa nämä saadaan viimeinen automaatti. 5 ✣ a

b

b

✢ ✛3 ✛ ✣ a

b

a a

❘ ✛ 126 b ✒ ❦

45 ✣ a, b

b

✢ ✛3 ✛

a

a

❘ ✛ 126 b ❦

✢ 4

Tämä onkin minimaalinen, sillä L3 6= L45 ja L3 6= L126 , koska ε ∈ L3 , ja L45 6= L126 , koska b ∈ L45 r L126 . Alkuperäisen automaatin kieli on minimaalisen automaatin hyväksymä kieli, L(A) = b∗ a((a ∪ b)(b ∪ ab∗ a))∗ . ⊓ ⊔

3

Pinoautomaatti

CF-kielet Kielioppi G = (V, Σ, P, S) on

CF-kielioppi, jos sen kaikki produktiot ovat muotoa A −→ α ,

(A ∈ N, α ∈ V ∗ ) .

Kieli L on CF-kieli, jos sen generoi jonkin CF-kielioppi. Kullakin sanalla w ∈ L(G) on aina vasen johto, missä jokaisella produktioaskeleella x =⇒ y korvataan ensimmäinen (eli vasemmanpuoleisin) nonterminaali: x = wAz =⇒ wαz = y ,

missä A −→ α on produktio, w terminaalisana (mahdollisesti w = ε) ja z ∈ V ∗ . Kieliopin G = (V, Σ, P, S) sanotaan olevan Chomskyn normaalimuodossa, jos sen produktiot ovat muotoa A −→ BC ,

A −→ a ,

S −→ ε

(A, B, C ∈ N, a ∈ Σ)

ja lisäksi, jos S −→ ε on produktio, niin S ei esiinny minkään produktion oikealla puolella.

Theorem 3.1. Jokaisen CF-kielen generoi Chomskyn normaalimuotoa oleva CF-kielioppi. Todistus. Sivuutetaan.

PDA Tarkastellaan seuraavaksi automaatteja, jotka hyväksyvät CF-kielet. Tällainen automaatti saadaan FA:sta liittämällä siihen erityinen työnauha, eli pinomuisti, jota automaatti lukee periaatteella `viimeisenä sisään, ensimmäisenä ulos'. Pinoautomaatti eli PDA1 koostuu seuraavista komponenteista: P = (Q, Σ, Γ, σ, ZP , qP , F ) ,

missä • • •

Q, Σ, qP ja F ovat kuten äärellisessä automaatissa, ja Γ on pinoaakkosto, σ on äärellinen transitiorelaatio, σ : Q × (Σ ∪ {ε}) × Γ → P (Q × Γ ∗ ) ,

missä (p, z) ∈ σ(q, a, Z) on

transitio, joka kirjoitetaan myös muodoissa

(q, a, Z, p, z) 1

push-down automaton

eli

a

(q, Z) −−→ (p, z) ,

3 Pinoautomaatti •

ZP on

23

pinon alkukirjain. ✲

TILAT ❄

P I N O

SYÖTTÖ a

Transitio (q, Z) −−→ (p, z) tulkitaan niin, että PDA lukee syötön a (joka on joko tyhjä sana ε tai kirjain aakkostosta Σ ) tilassa q pinon päällimmäisen kirjaimen ollessa Z ∈ Γ , ja sitten automaatti siirtyy tilaan p ja korvaa pinon päällimmäisen kirjaimen sanalla z . Jos edellä z = ε, niin pinon päällimmäinen kirjain pyyhkiytyy pois, ja PDA lukee pinosta seuraavaa kirjainta. Huomaa, että transitiorelaatio σ voidaan ajatella joukon Q × (Σ ∪ {ε}) × Γ × Q × Γ ∗

osajoukkona, kun transitiot kirjoitetaan muodossa (q, a, Z, p, z). Pinoautomaatin P konguraatio (tilannekuvaus) on kolmikko (q, v, α) ∈ Q × Σ ∗ × Γ ∗ ,

missä q on tila, v on lukematta oleva syöttö ja α on pinon sisältö siten, että sen ensimmäinen kirjain on pinon päällä. Konguraatio (q, aw, Zα) johtaa suoraan konguraatioon (p, w, zα), jos (p, z) ∈ σP (q, a, Z) on transitio. Tällöin merkitään (q, aw, Zα) ⊢ (p, w, zα)

ja jos γ1 , . . . , γn on jono konguraatioita siten, että γi ⊢ γi+1 (i = 1, 2, . . . , n − 1), niin kirjoitetaan γ1 ⊢∗ γn , ja sanotaan, että konguraatio γ1 johtaa konguraatioon γn . Konguraatio (qP , w, ZP ) on alkukonguraatio. PDA P hyväksyy kielen L(P ) = {w ∈ Σ ∗ | (qP , w, ZP ) ⊢∗ (q, ε, ε), q ∈ F }.

Hyväksyminen tapahtuu siis lopputilassa pinon ollessa tyhjillään, eli kokonaan hävitettynä.

Esim. 3.1

CF-kielen L = {an bn | n ≥ 1} hyväksyy PDA, jonka transitiot ovat a

(qP , ZP ) −−→ (qa , aZP ) , b

(qa , a) −−→ (qb , ε) ,

a

(qa , a) −−→ (qa , aa) , ε

(qb , ZP ) −−→ (h, ε) ,

missä h on lopputila. Tässä esimerkiksi, (qP , aabb, ZP ) ⊢ (qa , abb, aZP ) ⊢ (qa , bb, aaZP ) ⊢ (qb , b, aZP ) ⊓ ⊔

⊢ (qb , ε, ZP )

⊢ (h, ε, ε) .

24

3 Pinoautomaatti

Sanotaan, että PDA P on tilaton, jos sillä on vain yksi tila. Tässä tapauksessa P ei pysty tarkistamaan mitään ominaisuutta tilojensa avulla, sillä kaikki transitiot ovat muotoa a (q, Z) −−→ (q, z), missä Q = {q}, qP = q , F = {q}. Koska tilojen vaihdoilla ei ole merkitystä a tilattomassa PDA:ssa, voidaan sen transitiot esittää sievemmässä muodossa: Z −−→ z .

Lause 3.1 Kullekin CF-kielelle

L on tilaton PDA P , joka hyväksyy sen.

Todistus. Olkoon G = (V, Σ, P, S) Chomskyn normaalimuotoa oleva CF-kielioppi. Määritellään tilaton PDA P niin, että ZP = S , Γ = N (= V \ Σ) ja transitiot ovat seuraavat: ε

jos A −→ BC ∈ P

a

jos A −→ a ∈ P .

(q, A) −−→ (q, BC) (q, A) −−→ (q, ε)

Väitetään, että L(P ) = L(G). Pinoautomaatin konstruktion ideana on, että P simuloi G:n vasempia johtoja, S =⇒∗ w. Koska G on Chomskyn normaalimuotoa, niin sen vasemmat johdot ovat kaikki muotoa S =⇒∗ vx , missä v ∈ Σ ∗ on terminaalisana, ja x ∈ N ∗ koostuu vain nonterminaaleista. PDA P simuloi G:tä pitämällä nonterminaalisanan x pinossaan.

Väite: S =⇒∗ vx on G:n vasen johto jos ja vain jos (q, v, S) ⊢∗ (q, ε, x) on P :n johto. Tämä väite voidaan todistaa molempiin suuntiin suoraviivaisella induktiolla (harjoitus). Erityisesti, S =⇒∗ w on G:n vasen johto sanalle w ∈ Σ ∗ jos ja vain jos (q, w, S) ⊢∗ (q, ε, ε) on P :n hyväksyvä johto. Tämä osoittaa, että L(P ) = L(G). ⊓ ⊔

Lause 3.2 Kullekin tilattomalle PDA:lle P kieli

L(P ) on CF-kieli.

Todistus. Olkoon P :n syöttöaakkostona Σ ja pinoaakkostona Γ . Tässä voidaan olettaa, että Σ ∩ Γ = ∅. Määritellään CF-kielioppi G, jonka nonterminaalit ovat N = Γ ja jonka produktiot ovat Z −→ az

jos

a

(q, Z) −−→ (q, z) P :ssä, a ∈ Σ ∪ {ε}.

Kun S = ZP on G:n alkukirjain, niin L(G) = L(P ). Tämä todetaan helposti tarkastelemalla ⊔ vasempia johtoja. ⊓ Edellisistä lauseista seuraa, että

Lause 3.3 Kieli on CF-kieli tarkalleen silloin kun sen hyväksyy tilaton PDA. Tiedetään, että tilattomat PDA:t hyväksyvät tarkalleen CF-kielet. Entä useampi tilaiset PDA:t? Seuraava lause osoittaa, että tilojen lukumäärä ei (epädeterministisissä) pinoautomaateissa vaikuta hyväksyttäviin kieliin, nimittäin,

Lause 3.4 Kieli on CF-kieli tarkalleen silloin kun on olemassa PDA, joka hyväksyy sen. Todistus. Todistus sivuutetaan tässä. Lause voidaan todistaa kahdella tapaa, konstruoimalla jokaiselle PDA:lle P CF-kielioppi, joka generoi kielen L(P ). Toinen tapa, käyttäen CF-kielten sulkeuma ominaisuuksia, on selkeämpi. ⊓ ⊔

3 Pinoautomaatti

25

Saadaan seuraava seuraus, jonka suora todistus jätetään harjoitustehtäväksi.

Seuraus 3.5 Jokaiselle PDA:lle on olemassa tilaton PDA, joka hyväksyy tarkalleen saman

kielen.

Edeltävien tulosten nojalla jokainen PDA:n hyväksymä kieli voidaan hyväksyä tilattomalla PDA:lla. Tämä on yllättävää, sillä tilaton PDA ei esimerkiksi pysty tarkistamaan, onko pinon kaksi päällimmäistä kirjainta samat  asia, joka ei tuota useampitilaiselle PDA:lle minkäänlaista päänvaivaa. Tämänkaltaisten ehtojen täyttämiseksi tilattoman PDA:n on ennakoitava ja muunneltava tilanne hyvissä ajoin  esimerkiksi käyttämällä pinossa kirjaimia (a, b), jotka ovat alkuperäisten kirjainten pareja, jolloin pinon sisältö voi olla vaikkapa (a, b)(b, c)(c, b)(b, a). Jos on osoitettava, että jokin kieli L on CF-kieli, niin on mukavinta suunnitella sille CF-kielioppi tai useampitilainen PDA. Tilattoman PDA:n rakentaminen on useimmiten hankalaa (paitsi jos kielelle on jo suunniteltu kielioppi). Toisaalta, CF-kielten ominaisuuksia ratkottaessa tilaton PDA on ymmärrettävästi mukava vaihtoehto, koska se on yksinkertainen laite.

CF-kielten ominaisuuksia Seuraavaksi tarkastellaan CF-kielten sulkeumaominaisuuksia. Todistukseissa käytetään pinoautomaatteja, mutta ne voidaan kirjoittaa myös käyttäen kielioppeja.

Lause 3.6 CF-kielten perhe on suljettu seuraaviin operaatioihin: ∪, ·, ∗ ja +. Todistus. Todistetaan väite unionin ja tulon osalta, loput kaksi väitettä jätetään harjoitukseksi. Olkoot P1 = (Q1 , Σ, Γ1 , σ1 , ZP1 , q1 , Q1 ) ja P2 = (Q2 , Σ, Γ2 , σ2 , ZP2 , q2 , Q2 ) kaksi tilatonta PDA:t, Q1 = {q1 } ja Q2 = {q2 }. Osoitetaan, että 1) L(P1 ) ∪ L(P2 ) on CF-kieli: Konstruoidaan PDA P = (Q1 ∪ Q2 ∪ {qP }, Σ, Γ1 ∪ Γ2 ∪ {ZP }, σ, ZP , qP , {q1 , q2 }), missä ε

ε

σ = σ1 ∪ σ2 ∪ {(qP , ZP ) −−→ (q1 , ZP1 ), (qP , ZP ) −−→ (q2 , ZP2 )}.

Selvästi w ∈ L(P ) jos ja vain jos (qP , w, ZP ) ⊢ (qi , w, ZPi ) ⊢∗ (qi , ε, ε)

jollekin i = 1, 2, ts. jos ja vain jos w ∈ L(P1 ) ∪ L(P2 ). 2) L(P1 )L(P2 ) on CF-kieli: Konstruoidaan PDA P = (Q1 ∪ Q2 ∪ {qP }, Σ, Γ1 ∪ Γ2 ∪ {X}, σ, X, qP , {q2 }), missä on siis uusi alkutila qP ja uusi pinokirjain X ja transitiot ovat ε

ε

σ = σ1 ∪ σ2 ∪ {(qP , X) −−→ (q1 , ZP1 X), (q1 , X) −−→ (q2 , ZP2 )}.

Selvästi, w ∈ L(P ) jos ja vain jos w = uv (qP , w, X) ⊢ (q1 , w, ZP1 X) ⊢∗ (q1 , v, X) ⊢ (q2 , v, ZP2 ) ⊢∗ (q2 , ε, ε)

eli w ∈ L(P1 )L(P2 ).

⊓ ⊔

26

3 Pinoautomaatti

On kuitenkin huomattava, että CF-kielten perhe ei ole suljettu leikkaukseen, eikä komplementtiin. CF-kielten perheelle voidaan leikkauksen suhteen osoittaa kuitenkin seuraava käyttökelpoinen sulkeuma ominaisuus.

Lause 3.7 CF-kielet ovat suljettuja säännöllisellä kielellä leikkaamiseen: jos L on CF-kieli ja R on säännöllinen kieli, niin L ∩ R on CF-kieli. Todistus. Olkoon P = ({q1 }, Σ, Γ, σ, ZP , q1 , {q1 }) tilaton PDA joka hyväksyy CF-kielen L(= L(P )) ja A = (Q, Σ, δ, qA, F ) DFA kielelle R = L(A). (Voidaan rajoituksetta olettaa, että L ja R ovat samassa aakkostossa Σ ). Määritellään PDA P ′ = ({q1 }×Q, Σ, Γ, σ′ , ZP , (q1 , qA ), {q1 }×F ), jossa transitiorelaatio σ ′ muodostuu seuraavasti, a

jos (q1 , a, Z, q1 , z) ∈ σ ja δ(q, a) = p,

ε

jos (q1 , ε, Z, q1 , z) ∈ σ,

((q1 , q), Z) −−→ ((q1 , p), z) ((q1 , q), Z) −−→ ((q1 , q), z)

Siis P ′ tarkistaa saman aikaisesti, kuuluuko syöte w kieleen L = L(P ) ja L(A) = R. Nimittäin, w ∈ L(P ′ ) jos ja vain jos ((q1 , qA ), w, ZP ) ⊢∗ ((q1 , p), ε, ε),

missä δ(qA , w) = p ∈ F ja (q1 , w, ZP ) ⊢∗P (q1 , ε, ε). Siis L(P ′ ) = L(P ) ∩ L(A). ⊓ ⊔

Lause 3.8 CF-kielten perhe on suljettu morsiin kuviinsa. Todistus. Harjoitus.

Lause 3.9 CF-kielten perhe on suljettu käänteismorsmiin. Todistus. Olkoot L = L(P ) CF-kieli, missä P on tilaton PDA, ja h morsmi. Osoitetaan, että myös h−1 (L) = {w | h(w) ∈ L} on CF-kieli. Ajatuksena on `lue w, kuvittele h(w)'. Määritellään uusi useampitilainen PDA M seuraavasti. M :n tilat ovat kaikki sanojen h(a) suksit yhdessä alkutilan q = qM kanssa (q on P :n ainut tila): QM = {q} ∪ {u | u on h(a):n suksi , a ∈ Σ}.

Myös tyhjä sana ε ∈ QM . Automaatin M ainut lopputila on q , ja sen transitiot ovat a

kaikille a, Z ,

ε

jos (q, Z) −−→P (q, z) ,

(q, Z) −−→M (h(a), Z) (bu, Z) −−→M (u, z)

b

ε

(ε, Z) −−→M (q, Z) .

Ensimmäisessä transitiossa siirrytään (luettavien kirjaimien välillä) P :n tilasta M :n tilaan h(a), toisen rivin transitiossa simuloidaan P :tä ikäänkuin syöttönä olisi h(a), ja kolmannen rivin transitiossa siirrytään takaisin P :n tilaan, koska koko sana h(a) on luettu sisäisten tilojen avulla. Eli (q, h(a)h(v), γ) ⊢∗P (q, h(v), γ ′ ) ⇐⇒ (q, av, γ) ⊢∗M (q, v, γ ′ ) ,

mistä seuraa, että M hyväksyy kielen h−1 (L). ⊓ ⊔

3 Pinoautomaatti

27

Olkoon ∆ = Γ ∪ Γ aakkosto, missä Γ = {a1 , . . . , an }

ja

Γ = {a1 , . . . , an }

ovat kaksi erillistä aakkostoa, jotka vastaavat sulkupareja (vasemmat ja oikeat sulkeet pareittain: a1  a1 , a2  a2 , . . . ). Yleisesti, Dy k-kieli D∆ määritellään niiden sanojen joukoksi, jotka ovat hyvin muodostettuja sulkulausekkeita.

Esim. 3.2

Esimerkiksi, a1 a2 a2 a1 a1 a1 ∈ D∆ . Normaalissa käytössä, missä a1 on (, a1 on ), a2 on [, ja b2 on ], jolloin edeltävä sana voidaan kirjoittaa muodossa ( [ ] ( ) ). Toisaalta, a1 a1 a2 a1 a1 a2 ∈ / D∆ . ⊓ ⊔

Lemma 3.1. Olkoon ∆ kuten edellä. (i) Tällöin w ∈ D∆ jos ja vain jos w redusoituu tyhjäksi sanaksi ε käyttämällä sääntöjä: ai ai 7→ ε (i = 1, 2, . . . , n). (ii) D∆ on CF-kieli. ⊔ Todistus. Harjoitus. ⊓ Lause 3.10 Jokaiselle CF-kielelle L on olemassa Dy k-kieli D, säännöllinen kieli R ja morsmi h niin, että L = h(D ∩ R).

Sivuutetaan tämän tuloksen todistus. Siinä tarvittavat konstruktiot ovat seuraavat. Olkoon L = L(G) ⊆ Σ ∗ CF-kieli, missä G on Chomskyn normaalimuotoa ja sen produktiot ovat r1 , . . . , rk . Olkoon ∆ = Σ ∪ Σ ∪ {(, ), [, ]}, missä Σ = {a | a ∈ Σ} on Σ :n kirjaimia vastaavat `oikeanpuoleiset sulkeet'. Valitaan D = D∆ , ja määritellään morsmi h ehdoista h(a) = a ,

kun a ∈ Σ, ja

h(x) = ε muulloin.

Säännöllinen kieli R määritellään kielenä R = L(G′ ), jonka alkukirjain on S (= G:n alkukirjain), ja jonka produktiot ovat jos A −→G a, missä a ∈ Σ ,

A −→ aa i

B −→ [ ( [C ′

i

A −→ aa ]) ]D

jos ri = B −→G CD , jos A −→G a , ri = B −→G CD, missä a ∈ Σ .

Deterministinen PDA PDA on deterministinen pinoautomaatti eli DPDA, jos sen transitiot toteuttavat ehdot: (p1 , u1 ), (p2 , u2 ) ∈ σ(q, a, Z)

=⇒

p1 = p2

ja u1 = u2

ja jos a = ε, niin (p1 , u1 ) ∈ σ(q, ε, Z) on ainoa transitio tilalle q ja pinokirjaimelle Z . DPDA P hyväksyy kielen L(P ) = {w | (qP , w, ZP ) ⊢∗ (q, ε, z), q ∈ FP }

missä siis ei vaadita tyhjää pinoa laskun lopussa. Kieli L(P ) on deterministinen CF-kieli.

Huomio: DPDA on määrittelynsä mukaisesti monitilainen, eikä sille voida esittää ekvivalenttia tilatonta determinististä pinoautomaattia. Tilattomuus on siis vain epädeterministisen pinoautomaatin yksinkertaistus.

28

3 Pinoautomaatti

Esim. 3.3

L = {wdwR | w ∈ {a, b}∗} on deterministinen CF-kieli, mutta L = {wwR | w ∈ {a, b} } ei ole. (Ensimmäinen väite on helposti todennettavissa, jälkimmäinen vaikeammin). ⊓ ⊔ ∗

Deterministiset CF-kielet eivät ole suljettuja leikkaukseen nähden. Sama esimerkki sopii näille kuin yleisille CF-kielillekin: kielet L1 = a∗ {bn cn | n ≥ 0} ja L1 = {an bn | n ≥ 0}c∗ ovat deterministisiä, mutta niiden leikkaus ei ole edes CF-kieli.

Ratkeavuuskysymyksiä Seuraavat probleemat ovat algoritmisesti ratkeavia CF-kielille: annettuna CF-kielioppi G, onko (1) (2) (3)

w ∈ L(G), kun w on annettuna; L(G) = ∅; |L(G)| = ∞.

Todettakoon, että CF-kielten ekvivalenssiprobleema, L(G1 ) = L(G2 ), on algoritmisesti ratkeamaton. Deterministisille CF-kielille ekvivalenssiprobleema oli yksi formaalisten kielten vanhimpia ongelmia, jolle löydettiin vastaus vasta 1997: ongelma on ratkeava. Probleema, onko annettu CF-kieli rakenteellisesti moniselitteinen, on myös ratkeamaton. CF-kieli L on rakenteellisesti moniselitteinen (inherently ambiquous), jos jokainen kielioppi G, jolla L = L(G), G on moniselitteinen eli ainakin yhdellä sanalla w ∈ L(G) on vähintään kaksi eri johtopuuta. Tämä ratkeamattomuustulos vaikeuttaa erityisesti kääntäjien suunnittelua, koska näissä on oleellista, että käännettävälle kielelle on löydettävissä kielioppi, jossa kielen rakenne tulee yksiselitteisesti näkyviin johtopuissa. Kääntäjiin palataan lyhyehkösti seuraavassa kappaleessa.

Esim. 3.4

Kieli

L = {ak bm cn | k = m tai m = n}

on rakenteellisesti moniselitteinen CF-kieli. (Todistus sivuutetaan). ⊓ ⊔

4

Turingin koneet

TM Turingin kone on yleinen laskettavuuden malli, joka kykenee suoriutumaan kaikista algoritmisesti laskettavissa olevista tehtävistä! Turingin koneella M on äärellinen keskusmuisti (sisäiset tilat) ja potentiaalisesti ääretön nauha (ajatellaan, että nauha on molempiin suuntiin ääretön), jolta se voi lukea ja jolle se voi kirjoittaa. Lisäksi Turingin kone voi siirtyä nauhallaan sekä oikealle että vasemmalle, eli se on 2-suuntainen. Nauha, joka on samalla syöttö- ja työnauha, on ruudutettu, ja jokaisessa ruudussa voi olla kirjain tai sitten ruutu on tyhjä.

...

|

|

|

|. . .

✻

TILAT

Turingin kone eli TM1 on M = (Q, Σ, Γ, δ, qM , F ), missä Q on äärellinen joukko tiloja, Σ on syöttöaakkosto, ja Γ on työaakkosto, jolle Σ ⊆ Γ , δ : Q × Γ → Q × Γ × {L, R, S} on transitiofunktio, qM on alkutila, ja F on lopputilojen joukko. Työaakkostoon Γ kuuluu aina tyhjän ruudun symboli #, ja kaikki syöttökirjaimet. Formaalisesti

• • • •

Edellä L tarkoittaa siirtymistä vasemmalle, R oikealle ja S pysymistä paikallaan. Turingin kone voi käyttää laskiessaan hyväksi apukirjaimia, eli työaakkoston kirjaimia b ∈ ∆ \ Σ. TM M on deterministinen, eli sen transitiot muodostavat (osittaisen) kuvauksen  jottei roskatilaa tarvitse tuottaa, sallitaan osittaisuus. Jos δ(q, a) ei ole määritelty tilalle q ja symbolille a, niin kone lukkiutuu eikä suostu sanomaan syötöstä mitään. M :n transitio a/bX

δ(q, a) = (p, b, X) eli q −−−−→ p

eli (q, a, p, b, X) ∈ δ

tulkitaan: jos M on tilassa q lukemassa ruutua, jossa on a (mahdollisesti a = #, mutta a 6= ε), niin M siirtyy tilaan p ja • • 1

kirjoittaa ruutuun kirjaimen b (mahdollisesti b = a tai b = #), siirtyy vasemmalla (oikealla) olevaan ruutuun, jos X = L (X = R), tai

Turing ma hine

30 •

4 Turingin koneet pysyy paikallaan, jos X = S .

Turingin koneen M konguraatio on sana uqav , missä q on tila, nauhan sisältö on . . . ##uav## . . . ja luku/kirjoituspää on a:n kohdalla, ja uav on nauhan sen osan sisältö, joka sisältää luettavan ruudun ja kaikki epätyhjät ruudut. ...# | u | a | v | # | # |...

✻ q

Syöttösana w ∈ Σ ∗ kirjoitetaan nauhalle, jolloin

alkukonguraatio syötölle w on

γM = qM w .

Niinpä mikäli syöttönä on tyhjä sana w = ε, on alkukonguraatio qM #. Konguraatio γ1 johtaa suoraan toiseen konguraatioon γ2 , γ1 ⊢ γ2 , jos (R): δ(q, a) = (p, b, R) ja γ1 = uqav ja γ2 = ubpv (v 6= ε), tai γ1 = uqa ja γ2 = ubp#, (L): δ(q, a) = (p, b, L) ja γ1 = ucqav , γ2 = upcbv (uc 6= ε) tai γ1 = qav , γ2 = p#bv , (S ): δ(q, a) = (p, b, S) ja γ1 = uqav , γ2 = upbv . Kohdassa (R) jälkimmäinen johtoaskel voidaan ajatella uuden ruudun luomisena nauhan oikeaan reunaan. Vastaavasti kohdan (L) jälkimmäinen johtoaskel `luo uuden ruudun' vasemmalle. Lisäksi konguraatio γ johtaa konguraatioon γ ′ , γ ⊢∗ γ ′ , jos on olemassa äärellinen jono konguraatioita γ = γ1 ⊢ γ2 ⊢ · · · ⊢ γn = γ ′ .

Esim. 4.1

Olkoot TM M :n transitiot δ(qM , a) = (q1 , a, R) ,

δ(q1 , a) = (q2 , #, S) ,

δ(q2 , #) = (q1 , #, R) ,

δ(q1 , #) = (h, #, S) ,

missä h on ainut lopputila. Graasesti M voidaan piirtää oheisesti: qM

a/aR

✲ q1

#/#S ✲ h

✻ #/#R

a/#S

❄ q2

Tässä Σ = {a} ja Γ = {a, #}. Esimerkiksi qM aa ⊢ aq1 a ⊢ aq2 # ⊢ a#q1 # ⊢ a#h#, ja ⊔ näin ollen M pyyhkii sanasta aa yhden a:n pois: qM aa ⊢∗ a#h# . ⊓

4 Turingin koneet TM M

31

hyväksyy sanan w ∈ Σ ∗ , jos se päätyy joskus lopputilaan: qM w ⊢∗ xhy ,

joillekin x, y ∈ Γ ∗ ja h ∈ F . Sovitaan myös, että jos M päätyy lopputilaan, niin se pysähtyy. Turingin kone voi pysähtyä myös silloin, kun sillä ei ole transitioita käytössä  tällöin se lukkiutuu. Esimerkiksi, jos M on lukemassa symbolia a tilassa q , ja koneella ei ole transitiota parille (q, a), niin se lukkiutuu (eikä hyväksy syöttöä). Sanotaan, että M tunnistaa eli hyväksyy kielen: L(M ) = {w ∈ Σ ∗ | M hyväksyy sanan w} .

Esim. 4.2

Olkoon TM M :n transitiot

δ(qM , a) = (qM , a, R) ,

δ(qM , #) = (qM , #, R) ,

δ(qM , b) = (h, #, S) ,

missä h on jälleen pysähtymistila (ainut lopputila), Σ = {a, b} ja Γ = Σ ∪ {#}. Tällöin qM aa ⊢ aqM a ⊢ aaqM # ⊢ aa#qM # . . . , eli M jatkaa oikealle loputtomiin, eikä koskaan pääse lopputilaan. Toisaalta, jos syöttösana w ∈ Σ ∗ sisältää yhdenkin b:n, niin M pysähtyy tilassa h luettuaan tämän symbolin. Näin ollen L(M ) = Σ ∗ bΣ ∗ . ⊓ ⊔ Sanotaan, että kieli L on Turing-tunnistuva eli on olemassa TM M , jolla L = L(M ).

Esim. 4.3 syy sen:

rekursiivisesti numeroituva,

jos

Kieli L = {an bn cn | n ≥ 1} on Turing-tunnistuva, sillä seuraava TM M hyväk-

a/eS

x/xR

siirry oikealle (x ∈ {a, d, e})

b/dS

x/xR

siirry oikealle (x ∈ {b, d})

c/dS

x/xL

siirry vas. (x ∈ {a, b, c, d})

qM −−−−→ qa muuta ens. a e:ksi qa − −−−− → qa qa −−−−→ qb muuta ens. b d:ksi qb − −−−− → qb qb −−−−→ q2 muuta ens. c d:ksi q2 −−−−→ q2 e/eR

q2 −−−−→ qM kunnes e löytyy d/dR

qM −−−−→ q3 kaikki a:t luettu?

e/eR

qM −−−−→ qM siirry askel oikealle d/dR

q3 −−−−→ q3

tarkistetaan

#/#R

⊓ ⊔

q3 −−−−−→ h ja hyväksytään.

Tehtäviä TM:lle Seuravaksi esitetään joitain yleisluontoisia (perus)tehtäviä, joista Turingin koneet suoriutuvat. Näissä ei lähdetä alkukonguraatiosta liikkeelle, vaan tietynlaisesta konguraatiosta, josta halutaan uudenlainen konguraatio. Ajatuksena on, että näitä (`rutiineja') yhdistelemällä voidaan määritellä Turingin koneita, jotka suoriutuvat monimutkaisemmista tehtävistä (ja joiden käyttäytymistä kuvaillaan yksinkertaisempien TM:ien avulla).

32

4 Turingin koneet

Lause 4.1 Kullekin seuraavalle tehtävälle on olemassa TM, joka suoriutuu niistä. • • • • • •

La : Lue lähimpänä vasemalla oleva a; wauqv ⊢∗ wpauv , missä u ei sisällä kirjainta a. Ra : Lue lähimpänä oikealla oleva a; wquav ⊢∗ wupav , missä u ei sisällä kirjainta a. TR : Sanan siirto oikealle; uqv ⊢∗ up#v . TL : Sanan siirto vasemmalle; uq#v ⊢∗ upv . C : Kopiointi; uqv ⊢∗ upvv . ( up1 v jos u = v , E : Yhtäsuuruuden tarkistus: vqu ⊢∗ up2 v jos u 6= v .

Todistus. Katsotaan TR ; muut ovat harjoituksia. Tässä tapauksessa transitiot ovat a/#R

b/aR

#/aS

q −−−−−→ qa , qa −−−−→ qb , qa −−−−−→ q1 a/aL

q1 −−−−→ q1 ,

#/#L

q1 −−−−−→ p

kaikille kirjaimille a ja b. ⊓ ⊔ Edeltävät tehtävät voidaan hieman yleistää:

Lause 4.2 Kullekin seuraavalle tehtävälle on olemassa TM, joka suoriutuu niistä. Oletetaan, että symbolit @, [, ] eivät esiinny sanoissa u, ui.

(i) (ii) (iii) (iv)

Sanan merkintä: w@uqv ⊢∗ w[u]pv. Kopiointi tiettyyn paikkaan: wq[u0 ]u@v ⊢∗ wp[u0 ]u@u0 v. Korvaaminen tietyssä paikassa: wq[u0 ]u[u1 ]v ⊢∗ wp[u0 ]u[u0 ]v. Yhtäsuuruuden tarkistus tietyssä paikassa: ( wp1 [u0 ]u[u1 ]v wq[u0 ]u[u1 ]v ⊢ wp2 [u0 ]u[u1 ]v ∗

jos u0 = u1 , jos u0 = 6 u1 .

(v) Yhtäsuuruuden etsiminen:   w[u0 ][u1 ] . . . [p1 ui ] . . . [uk ]v

wq[u0 ][u1 ][u2 ] . . . [uk ]v ⊢∗

 

wp2 [u0 ][u1 ][u2 ] . . . [uk ]v

ensimmäiselle i ≥ 1 , jolla u0 = ui jos olemassa , jos u0 6= ui kaikilla i ≥ 1 .

Todistus. Katsotaan näistäkin vain (i); muut ovat harjoituksia. Ensinnä TR : w@uqv ⊢∗ w@up0 #v . Muut transitiot ovat #/ ]L

p0 −−−−−→ p1 ,

a/aL

p1 −−−−→ p1 ,

@/[R

p1 −−−−→ p2 ,

a/aR

p2 −−−−→ p2 ,

]/ ]R

p2 −−−−→ p

kaikille a 6= @. ⊓ ⊔

Esim. 4.4

Etsitään edellisten tehtävien avulla Turingin kone, joka tarkistaa onko sana u sanan v preksi: halutaan siis johto uqv ⊢∗ uhv

jos v = uv2 .

4 Turingin koneet

33

Oletetaan, että [ ja ] ovat uusia kirjaimia. Seuraavassa on esitetty tiivistelmä siitä kuinka TM urakasta selviää. L 4.2(i) : TR :

uqv ⊢∗ [u]p1 v , ⊢∗ [u]p2 #v ,

#/[S

p2 −−−−→ p2 :

⊢∗ [u][p2 v ,

R# :

⊢∗ [u][vp3 # ,

#/ ]S

•

p3 −−−−−→ p4 :

⊢∗ [u][vp4 ] ,

L[ , L[ :

⊢∗ p[u][v] .

TM käsittelee systemaattisesti konguraatiot p[u][v1 ]v2 (aluksi v2 = ε), ja tarkistaa, onko u = v1 (L 4.2(iv)). Jos on, niin TM pyyhkii kirjaimet [ ja ] pois (mihin se tarvitsee rutiineja R[ , R] , ja TL ), ja päätyy lopulta haluttuun konguraatioon. Jos taas u 6= v1 , niin TM siirtää viimeistä ] vasemmalle: jos v1 = v1′ a, niin p[u][v1 ]v2 ⊢∗ [u][v1′ aq1 ]v2 ⊢ [u][v1′ q2 a]v2 ⊢ [u][v1′ ]qa ]v2 ⊢ [u][v1′ ]q3 av2 ⊢∗ p[u][v1′ ]av2 .

•

Tässä esimerkissä, TM pysähtyy vain jos u on v :n preksi. ⊓ ⊔

Turing-laskettavat funktiot Olkoot Σ ⊆ Γ ja ∆ ⊆ Γ kaksi aakkostoa, jotka eivät sisällä symbolia #. Tällöin Turingin kone M laskee n-paikkaisen funktion f : (Σ ∗ )n → Γ ∗ ,

jos kaikille vektoreille (u1 , u2 , . . . , un ) ∈ (Σ ∗ )n on voimassa qM u1 #u2 # . . . #un ⊢∗ f (u1 , u2 , . . . , un )h# ,

missä h on lopputila. Edelleen, funktio f on Turing-laskettavissa, jos on olemassa Turingin kone, joka laskee sen.

34

4 Turingin koneet

Esim. 4.5

Seuraava TM M laskee funktion f : Σ → Σ , f (w) = w ,

missä w = a1 a2 . . . ak , kun w = a1 a2 . . . ak . Eli M kääntää sanan kirjain kerrallaan viivatuksi kirjaimeksi. M :n transitiot ovat (a ∈ Σ ): a/aR

qM −−−−→ qM ,

#/#S

qM −−−−−→ h .

⊓ ⊔

Numeeriseen laskemiseen käytetään yleensä unaarista esitystä, missä lukua n ∈ N vastaa sana I n , missä I on tähän tarkoitukseen varattu symboli. TM M laskee (numeerisen) funktion f : Nn → N, jos se laskee vastaavan sanafunktion I f : (I ∗ )n → I ∗ , joka on määritelty ehdosta f I (I k1 , . . . , I kn ) = I f (k1 ,...,kn ) .

Esim. 4.6 Funktio f (n, m) = n + m tulee lasketuksi Turingin koneella, joka etsii ensin sanan keskellä olevan merkin #, korvaa sen merkillä I ja palaa sitten sanan loppuun ja pyyhkii viimeisen merkin I pois. Tarvittavat transitiot ovat siis I/IR

qM −−−−→ qM ,

#/IS

qM −−−−−→ q1 ,

I/IR

q1 −−−−→ q1 ,

#/#L

q1 −−−−−→ q2 ,

I/#R

q2 −−−−−→ h .

⊓ ⊔

Esim. 4.7 Busy Beaver.

Tarkastellaan Turingin koneita, joiden syöttöaakkostona on Σ = {1} (yksi symboli), ja työaakkostona Γ = {#, 1}. Rajoitetaan tilat (n + 1):n alkion joukkoon Qn = {q0 , . . . , qn−1 } ∪ {h} (missä q0 = qM on alkutila ja h on ainut lopputila), a/bX

jolloin tällaisia Turingin koneita on vain äärellisen määrä (sillä erilaisia transitioita q −−−−→ p on vain 12 · n(n + 1) kappaletta). Ongelmana on etsiä sellainen TM (eli busy beaver), joka tyhjällä syötöllä (alkukonguraatio q0 #) kirjoittaa mahdollisimman monta ykköstä nauhalleen pysähtyen hyväksyvässä tilassa. Merkitään bb(M ) = ykkösten lukumäärä, kun TM M pysähtyy. Ongelman ratkaisu tunnetaan, kun n ≤ 4. Kun n = 2, on ratkaisu seuraava: #/1R

q0 −−−−−→ q1 1/1L

q0 −−−−→ q1

#/1L

q1 −−−−−→ q0 1/1L

q1 −−−−→ h

n bb(M ) 1 1 2 4 3 6 4 13

Kun n = 5 on paras tunnettu ratkaisu bb(M ) = 4098. ⊓ ⊔

Esitetään vielä yksi tapa, miten Turingin konetta voidaan käyttää hyväksi tehtävien algoritmisessa ratkaisemisessa. Otetaan käyttöön kaksi erikoissymbolia: ⊕ ja ⊖. Olkoon Σ aakkosto, joka ei sillä symbolia #. Kielen L ⊆ Σ ∗ karakteristinen funktio on χL : Σ ∗ → {⊕, ⊖} ,

4 Turingin koneet χL (w) =

Kieli L on Turing-ratkeava eli Turing-laskettavissa.



35

⊕ jos w ∈ L , ⊖ jos w ∈ / L.

rekursiivinen,

jos sen karakteristinen funktio χL on

Lause 4.3 Jokainen Turing-ratkeava kieli on Turing-tunnistuva. Todistus. Karakteristisen funktion laskeva Turingin kone M muutetaan hyväksyväksi koneeksi M ′ seuraavasti: jos M tulostaa symbolin ⊕, niin M ′ siirtyy hyväksyvään tilaan h; jos taas M tulostaa symbolin ⊖, niin M ′ siirtyy roskatilaan h′ , johon se jää pysyvästi hyväksymättä sanaa. ⊓ ⊔

Turingin koneen yleistyksiä Esitellään alla joitain yleistyksiä Turingin koneelle. Kaikille näille on voimassa

Lause 4.4 Kielet, jotka ovat tunnistettavissa yleistyksellä YTM, ovat tunnistettavissa Turingin koneella. Moninauhainen TM. Tällaisella Turingin koneella on n (n ≥ 1) kappaletta työnauhoja, joille se voi kirjoittaa ja joilta se voi lukea samanaikaisesti. q

# a # a # a # b

a

✎

a

❫ b #

❄ b

b # #

c # # # #

Niinpä n-nauhaisen TM:n M transitiofunktio on kuvaus δ : Q × Γ n → Q × (Γ × {L, R, S})n ,

eli jokainen transitio on muotoa δ(q, a1 , a2 , . . . , an ) =(p, b1 , X1 , b2 , X2 , . . . , bn , Xn )

missä q, p ∈ Q, ai , bi ∈ Γ, Xi ∈ Γ ∪ {L, R, S} , mikä tarkoittaa, että M lukiessaan tilassa q nauhalta i kirjaimen ai (i = 1, 2, . . . , n) M vaihtaa tilan p:ksi ja suorittaa i:nnellä nauhalla operaation bi Xi kuten tavallinen TM. M :n alkukonguraatio on (qM , w, #, . . . , #), eli syöttö kirjoitetaan ensimmäiselle nauhalle muiden nauhojen ollessa tyhjillään.

Esim. 4.8

Oheinen 2-nauhainen TM hyväksyy kielen L = {an bn cn | n ≥ 1}.

36

4 Turingin koneet δ(qM , x, #) = (qM , x, R, x, R) (x 6= #) (kopio 1. nauha nauhalle 2) δ(qM , #, #) = (q1 , #, L, #L) (siirry askel vasemmalle) δ(q1 , c, c) = (q1 , c, L, c, S) (1. nauha vasemmalle) δ(q1 , b, c) = (q2 , b, S, c, S) (aloita vertailu: b  c) δ(q2 , b, c) = (q2 , b, L, c, L) (siirtyen vasemmalle) δ(q2 , a, b) = (q3 , a, S, b, S) (vertailu onnistui) δ(q3 , a, b) = (q3 , a, L, b, L) (vertailu: a  b) δ(q4 , #, a) = (h, #, S, a, S) (vertailu onnistui) ⊓ ⊔

Tavallinen TM simuloi moninauhaista Turingin konetta esimerkiksi niin, että se kirjoittaa omalle nauhalleen kaikki moninauhaisen koneen nauhojen sisällöt perätysten ja pitää sitten kirjaa jokaisen nauhan luku/kirjoituspään sijainnista. Yksinauhainen simuloiva TM joutuu kirjanpidon ohessa myös laajentamaan työnauhaansa lisäämällä tyhjiä ruutuja tarvittaviin paikkoihin, mikä tarkoittaa, että se siirtää sanan loppuosan yhden ruudun oikealle: uqav ⊢∗ uq#av . Epädeterministinen TM eli NTM. Tällaisella Turingin koneella on vaihtoehtoja, mitä transitioita se käyttää, eli epädeterministinen TM pystyy `arvaamaan'. Epädeterministisen TM:n transitiot muodostavat moniarvoisen kuvauksen, σ : Q × Γ → P (Q × Γ × {R, L, S}) .

Transitio on tällöin muotoa (p, b, X) ∈ σ(q, a), ja pari (q, a) ei määrää sitä yksikäsitteisesti. NTM hyväksyy sanan, jos jokin lasku tälle sanalle päätyy sen lopputilaan.

Esim. 4.9

Olkoon L = {an b | n on parillinen } ∪ {an c | n on pariton} .

Oheinen NTM hyväksyy kielen L arvaamalla alussa onko n parillinen vai pariton, ja se tarkistaa että arvaus on tehty oikein: a/aR

(arvaa että n on parillinen)

qM −−−−→ q1 a/aR

(arvaa että n on pariton)

qM −−−−→ p1 a/aR

a/aR

q1 −−−−→ q2 , q2 −−−−→ q1 (tarkista arvaus parilliselle) b/bS

(oikein)

q2 −−−−→ h a/aR

a/aR

p1 −−−−→ p2 , p2 −−−−→ p1 (tarkista arvaus parittomalle) c/cS

p1 −−−−→ h

(oikein)

Esimerkiksi lasku qM aaac ⊢ aq1 aac ⊢ aaq2 ac ⊢ aaaq1 c lukkiutuu, sillä arvaus oli tehty

väärin. Oikea lasku on qM aaac ⊢ ap1 aac ⊢ aap2 ac ⊢ aaap1 c ⊢ aaahc. ⊓ ⊔

Äärellisten automaattien yhteydessä esitelty osajoukkokonstruktio ei sovellu epädeterministisen TM:n simuloimiseksi deterministisellä Turingin koneella. Kuitenkin epädeterminististä Turingin konetta voidaan simuloida deterministisellä simuloimalla NTM:n kaikkia laskuja systemaattisesti tietty askelmäärä kerrallaan  ja pitämällä tarkasti kirjaa mitkä valinnat on tehty ja tarkistettu. Epädeterministinen moninauhainen TM. Tällä Turingin koneella on n nauhaa (n ≥ 1) ja se toimii epädeterministisesti.

4 Turingin koneet

37

Usein kielen tunnistettavuus on helpompaa yleistetyllä Turingin koneella. Monien kielten hyväksyminen yleistetyllä TM:llä pienentää tarvittavien transitioiden lukumäärää huomattavasti verrattuna deterministiseen TM:ään (esim. L = {w | w = wR }).

Kieliopit Kieliopit generoivat kieliä siinä missä automaatit tunnistavat niitä.

Lause 4.5 Kieli L on generoitavissa kieliopilla tarkalleen silloin kun se on tunnistettavissa Turingin koneella.

Todistus. NTM:n transitiot ja kieliopin produktiot ovat simuloitavissa toinen toisillaan, mutta käänteisessä järjestyksessä. Osoitetaan vain kuinka kielioppi G generoi annetun Turingin koneen M hyväksymän kielen. Alkukirjain generoi ensin tarkistussymbolit alkuun ja loppuun, ja sitten se generoi  puhtaasti arvaamalla  Turingin koneen mahdollisen loppukonguraation: S −→ XAY A −→ bA | Ab | h

kaikilla koneen M työaakkoston kirjaimilla b, mukaanluettuna # (jota se voi käyttää yllinkyllin, jotta Turing koneen käyttämä työtila tulee kokonaan käyttöön). Nyt kielioppi on generoinut sanan XuhvY , joillain u ja v , ja se ryhtyy simuloimaan koneen M käskyjä käänteisessä järjestyksessä. Kielioppi G käyttää nonterminaaleina kaikki M :n työsymbolit, jotka eivät ole syöttökirjaimia, ja kaikki M :n tilat. Kaikille c: a/bS

cpb −→ cqa

jos q −−−−→ p ,

cbp −→ cqa

jos q −−−−→ p ,

pcb −→ cqa

jos q −−−−→ p .

a/bR a/bL

Jos kielioppi päätyy nonterminaaliin qM (joka on koneen alkutila), se tarkistaa, että generoitu sana muistuttaa koneen M alkukonguraatiota: #qM −→ qM XqM −→ Z

(alussa saa olla #) , (muttei muita kirjaimia) ,

Za −→ aZ

a ∈ ΣM ( syöttökirjaimia) ,

Z −→ T T # −→ T

(pitäisi olla lopussa) , (lopussa saa olla #) ,

T Y −→ ε

(muttei muita kirjaimia) ,

Vastaavasti Turingin kone simuloi generoivaa kielioppia. Koneen ongelmana on vain työtilan kasvattaminen; sehän ei ole kielioppien ongelma. Sivuutetaan tämän yksityiskohdat. ⊓ ⊔

38

4 Turingin koneet

Esim. 4.10

Kielen

L = {an bn cn | n ≥ 0}

generoi seuraava kielioppi: S −→ ε X −→ ε Y b −→ bY bZ −→ Zb

S −→ aXbc aXb −→ aabbY Y c −→ Zcc aZ −→ aX

⊓ ⊔

Esim. 4.11

Kielen L = {ww | w ∈ {a, b}∗ } generoi seuraava kielioppi: S −→ ε | aXAY | bXBY Aa −→ aA AY −→ ZaY | Ka

Ab −→ bA

Ba −→ aB BY −→ ZbY | Kb

Bb −→ bB

aZ −→ Za XZ −→ aXA | bXB

bZ −→ Zb

aK −→ Ka XK −→ ε .

bK −→ Kb ⊓ ⊔

5

Ratkeamattomuus

Universaalinen Turingin kone Jokainen tarkasteltu TM on suorittanut spesisen tehtävän, ja on siten vastannut lähinnä tietokoneen ohjelmaa. Seuraavaksi esiteltävä universaalinen Turingin kone on tietokoneen malli, jolle syötetään TM M (ohjelma) ja sana w (tehtävä), ja joka simuloi konetta M syötöllä w. Näin ollen universaalisen Turingin koneen syöttö on muotoa M : n esitys − M : n syötön esitys .

Edellä tarvitaan esitykset eli koodaukset, sillä universaalinen TM on Turingin kone ja siten sen aakkostot ovat kiinteät ja välttämättä äärelliset. Voidaan olettaa, että kaikkien Turingin koneiden tilajoukot ja syöttökirjaimet ovat äärettömien joukkojen Qω = {q1 , q2 , . . . }

ja Σω = {a1 , a2 , . . . }

osajoukkoja, eli QM ⊆ Qω ja ΣM ⊆ Σω . Huomaa, että ai = # jollain i. Oletetaan myös (rajoituksetta), että Turingin koneella on vain yksi lopputila h = qi jollakin i. Seuraavissa koodauksissa luvut n ∈ N ajatellaan unaarisesti, ja jokainen tila qi ∈ Qω ja jokainen kirjain ai ∈ Σω koodataan seuraavasti: ja

qi 7→ Qi

ai 7→ Ai .

Olkoon Υ = {[, ], Q, A, I, L, R, S} aakkosto, johon Turingin koneet koodataan. Olkoon M = (Q, Σ, Γ, δ, q0 , {h}) TM. Tällöin riittää koodata M :n transitiot δ , koska nämä määräävät Turingin koneen täysin. (Voidaan oletetaan, että jokaisen koneen alkutilana on q1 .) Kukin transitio δM (qi , aj ) = (qr , as , x) eli e = (qi , aj , qr , as , X) (missä X = R, L tai S ) koodataan sanaksi c(e) = IQi IAj IQr IAs IX . Turingin koneen M koodaus on tällöin c(M ) = [[c(e0 )][c(e1 )] . . . [c(em )]] ,

missä e0 , e1 , . . . , em ovat kaikki M :n transitiot.

Huomio: Edeltävä aakkosto Υ on valittu melko suureksi havainnollisuuden takia. Yhtä hyvin aakkosto voitaisiin rajoittaa binääriseksi {0, 1}. Koodataan kaikki symbolit joukoista Qω , Σω ja {L, R, S} unaariseen aakkostoon {0} seuraavasti: λ(L) = 0 , λ(qi ) = 02i+2

λ(R) = 02

λ(S) = 03 ,

ja λ(ai ) = 02i+3

∀i ≥ 1 .

40

5 Ratkeamattomuus

Tällöin, λ(x) = λ(y) jos ja vain jos x = y . Lisäksi kukin 0n on yhden symbolin x koodaus, 0n = λ(x). Transitiot ja Turingin koneet koodataan sitten käyttäen välimerkkinä symbolia 1. Syöttösana w ∈ Σω∗ koodataan sanaksi c(w) = [IAi1 ][IAi2 ] . . . [IAik ] ,

kun w = ai1 ai2 . . . aik .

Huomaa jälleen, että # on myös koodattu, eli se ei esiinny sanassa c(w).

Lause 5.1 On olemassa Turingin kone U , joka hyväksyy sanan c(M )c(w) tarkalleen silloin, kun Turingin kone M hyväksyy sanan w.

Edeltävän lauseen U on täin seuraavasti. • •

Sen syöttö on c(M )c(w), missä M on TM ja w on sana, U käy läpi sanaa c(w) ja pitäen kirjaa tiloista (koodauksessa c(M ) ja kohdasta, missä syöttökirjain on (käyttäen merkkiä #), [. . .

•

. . . ][ ]

[#Ar ][IAn ]

...

...

[]

[ #Qj IAr IQd IAp IY ]

. . . ][ ]

...

[#Ar ][IAn ]

...

[]

...

[]

U toteuttaa tämän transition, esimerkiksi, kun Y = R, [. . .

•

[ IQk IAm #Qj IAt IX ]

U etsii (systemaattisesti koodauksen alusta lähtien) sen transition (koodauksen), jossa on sama tila ja oikean syöttökirjaimen koodaus, [. . .

•

universaalinen TM (aakkostossa Υ ), ja se toimii pääpiirteit-

[ IQj IAr #Qd IAs IY ]

. . . ][ ]

...

[IAs ][#An ]

Kun (jos) M hyväksyy, niin U hyväksyy.

Huomio: Itseasiassa on olemassa universaalinen TM, jolla on vain 2 tilaa! Tai 7 tilaa ja 4 työaakkoston kirjainta. Näin ollen on universaalinen U , jolla on vain 28 transitiota! Ratkeavuus Muistetaan, että kieli L on (Turing-)ratkeava, jos on olemassa TM, joka laskee sen karakteristisen funktion, eli vastaa `kyllä' (⊕), jos sana w on kielessä, ja vastaa `ei' (⊖), jos sana w ei ole kielessä. Kieli L on ratkeamaton, jos se ei ole ratkeava. Toisaalta L on (Turing-)tunnistuva, jos on olemassa TM M , joka pysähtyy hyväksyvästi kaikilla w ∈ L. Tässä, jos w ∈ / L, niin M ei välttämättä pysähdy millään tavoin (ja varmasti ei hyväksyvässä tilassa). Tunnistuvuus ja ratkeavuus ovat siis eriluontoisia ongelmia.

Lause 5.2 Ratkeavan kielen komplementti on ratkeava. Todistus. Olkoon M karakteristisen funktion χL laskeva TM. Tällöin M ′ laskee kielen L

komplementin karakteristisen funktion: M ′ simuloi konetta M , kunnes M tulostaa symbolin ⊕ (tai ⊖), jolloin M ′ muuttaa ⊕ 7→ ⊖ (⊖ 7→ ⊕). ⊓ ⊔

5 Ratkeamattomuus

41

Ratkeavien ja tunnistuvien kielten monet sulkeumaominaisuudet seuraavat kopioinnista: on TM C , joka kopioi syötön w muotoon w@w, eli qC w ⊢∗ qw@w.

Lause 5.3 Kieli tunnistuva.

L on ratkeava tarkalleen silloin, kun se ja sen komplementti Σ ∗ r L on

Todistus. Ensinnäkin, jos L on ratkeava, niin sen komplementti on ratkeava (edellisen lauseen mukaan), ja siten tunnistuva. Toiseen suuntaan todistettaessa oletetaan, että L:n tunnistaa TM M ja sen komplementin tunnistaa TM M ′ . Konstruoidaan TM N siten, että se ensin kopioi syötön qN w ⊢∗ qw@w

ja sitten simuloi vuorotellen transitio kerrallaan koneita M ja M ′ nauhan alkuosalla ja loppuosalla, vastaavasti. (Jos M :n simulointiin tarvitaan lisää tilaa, niin N siirtää loppuosaa oikealle tarvittavan määrän.) Jos M hyväksyy sanan w, niin N :n lasku päättyy syötön alkuosalla, ja N hyväksyy sanan w. Jos taas M ′ hyväksyy sanan w, niin N :n lasku päättyy syötön loppuosalle, ja tällöin N hylkää syöttösanan w. Näin ollen N aina pysähtyy, ja laskee L:n karakteristisen funktion. ⊓ ⊔ Samaan tapaan voidaan todistaa

Lause 5.4 Turing-tunnistuvat ja Turing-ratkeavat kielet ovat suljettuja unioniin, leikkaukseen, tuloon, Kleenen sulkeumiin nähden, morsiin kuviin ja käänteismorsiin kuviin. Todistus. Harjoitus. ⊓ ⊔ Seuraavaksi osoitetaan, että on olemassa tunnistuvia kieliä, jotka eivät ole ratkeavia. Todistus perustuu diagonalisointimenetelmään, jota kuvaa seuraava esimerkki.

Esim. 5.1

Olkoot F = {fi | i = 1, 2, . . . } perhe kuvauksia, fi : N → N. Tällöin kuvaus f ∈ / F, missä f on määritelty diagonalisoimalla: f (i) = fi (i) + 1 kaikilla i. Jos f ∈ F, niin f = fk jollain k ja siten f (k) = fk (k) + 1 = f (k) + 1, mikä on ristiriita. ⊓ ⊔ Seuraavat kaksi tulosta todistuvat yhdessä.

Lause 5.5 On olemassa tunnistuva kieli, joka on ratkeamaton. Lause 5.6 Tunnistuvat kielet eivät ole suljettuja komplementtiin nähden. Todistus. Tarkastellaan universaalisen Turingin koneen yhteydessä määriteltyä koodausta c. Olkoon

K0 = {c(M )c(w) | w ∈ L(M )} . K0 on tunnistuva kieli. Sen hyväksyy universaalinen Turingin kone, jota muunnetaan ensin niin, että U ′ ei pysähdy millään syötöllä, joka ei ole oikea koodaus, eli U ′ ensin tarkistaa, että syöttö on muotoa c(M )c(w). Tämä on helppo tehtävä, sillä muodon tarkistamisesta suoriutuu sopiva DFA A. Olkoon Kd = {c(M ) | c(M ) ∈ L(M )}

42

5 Ratkeamattomuus

diagonaalikieli. Siis, Kd :n sanat ovat sellaisten koneiden M

koodaukset, joka hyväksyvät oman koodauksensa. Tällöin Kd on tunnistuva kieli, sillä sen hyväksyy TM N , joka ensin muokkaa alkutilanteen qN w muotoon qwc(w). (Tässä oletetaan, että Υ ⊆ Σω .) Tämän jälkeen M ′ simuloi universaalista Turingin konetta U . Toisaalta Kd ei ole ratkeava, sillä muutoin sen komplementti Kd′ = {w | w = c(M ) =⇒ w ∈ / L(M )}

olisi ratkeava, mutta Kd′ ei ole edes tunnistuva: jos Kd′ = L(M ”), niin c(M ”) ∈ Kd′ ⇐⇒ c(M ”) ∈ / L(M ”) = Kd′ ,

mikä on ristiriita. Kd on vaadittu kieli, joka on tunnistuva, muttei ratkeava. ⊓ ⊔

Lause 5.7

K0 on tunnistuva kieli, joka on ratkeamaton.

Todistus. Tehdään vastaoletus, että on TM M0 , joka laskee kielen K0 karakteristisen funk-

tion. Olkoon C TM, joka tarkistaa, että sana w on Turingin koneen koodaus (eli w = c(M ′ ) jollain M ′ ), ja kopioi sen sitten: qC w ⊢∗ qM0 ww. Nyt TM M1 , joka ensin simuloi konetta C ja sitten konetta M0 , laskee kielen Kd karakteristisen funktion: ( ( ⊕ jos c(M )c(M ) ∈ K , ⊕ jos c(M ) ∈ Kd , 0 qC c(M ) ⊢∗ qM0 c(M )c(M ) ⊢∗ = ⊖ jos c(M )c(M ) ∈ ⊖ jos c(M ) ∈ / K0 , / Kd , ja tämä on ristiriita edeltävän tuloksen kanssa. ⊓ ⊔

Olkoon P jokin ominaisuus. Tällöin P (X) on voimassa, jos X toteuttaa ehdon P eli sillä on ominaisuus P . Probleema `onko P (X), kun X on annettuna', on ratkeava, jos kieli LP = {X | P (X) on voimassa}

on ratkeava. Turingin koneiden pysähtymisprobleema on: annettuna TM M ja sana w, pysähtyykö M syötöllä w? Eli, onko w ∈ L(M ), annetuille M ja w? Osoitetaan, että pysähtymisprobleema on ratkeamaton, eli ei ole olemassa Turingin konetta, joka vastaa ⊕ tai ⊖ sen mukaan onko w kielessä M vai ei.

Lause 5.8 Turingin koneiden pysähtymisprobleema on ratkeamaton. Todistus. Tiedetään, että kieli K0 = {c(M )c(w) | w ∈ L(M )} on ratkeamaton. Pysähtymisprobleema palautuu tähän, kun koodataan M ja w ensin, jolloin syöttö M, w muuntuu muotoon c(M )c(w), ja siten w ∈ L(M )

⇐⇒

c(M )c(w) ∈ K0 .

(Koodaus c voidaan aina tehdä Turingin koneella.) Näin ollen pysähtymisprobleeman ratkaisu tuottaisi ratkaisumenetelmän myös kielelle K0 . ⊓ ⊔

Lause 5.9 On olemassa TM

M∗ , jolle probleema `pysähtyykö M∗ annetulla syötöllä w?' (eli, onko w ∈ L(M∗ )) on ratkeamaton.

5 Ratkeamattomuus

43

Todistus. Olkoon M∗ TM, jolla L(M∗ ) = K0 . Tällöin u ∈ L(M )

⇐⇒

c(M )c(u) ∈ K0 = L(M∗ ) ,

ja siten on palauduttu pysähtymisprobleemaan (w = c(M )c(u)). ⊓ ⊔

Lause 5.10 Seuraavat probleemat ovat ratkeamattomia. (i) (ii) (iii) (iv)

Annettuna M , onko ε ∈ L(M ). (Pysähtyykö TM tyhjällä nauhalla). Annettuna M , onko L(M ) = ∅. (Pysähtyykö TM millään syötöllä). Annettuna M , onko L(M ) = Σ ∗ . (Pysähtyykö TM kaikilla syötöillä). Annettuina M1 , M2 , onko L(M1 ) = L(M2 ). (Hyväksyvätkö TM:t tarkalleen samat sanat).

Todistus. Todistetaan kohta (i) palauttamalla se pysähtymisprobleemaan; muut kohdat jäävät harjoituksiksi. Kun M on TM ja w on sana, niin konstruoidaan uusi TM Mw′ , joka ensin kirjoittaa w:n, siirtyy sitten alkuun, ja lopulta simuloi konetta M syötön ollessa tuo w. Tällöin ε ∈ L(Mw′ ) ⇐⇒ w ∈ L(M ) , missä oikean puoleinen probleema w ∈ L(M ) on pysähtymisprobleema, ja siis ratkeamaton. Myös vasemman puoleinen probleema ε ∈ L(M ) on tällöin ratkeamaton. ⊓ ⊔

Postin vastaavuusongelma Siirrytään tarkastelemaan nyt eräitä formaalisten kielten ratkeamattomia ongelmia. Perusprobleema on Postin vastaavuusprobleema eli PCP1 : annettuina kaksi morsmia h, g : Σ ∗ → ∆∗ , onko olemassa sanaa w ∈ Σ + , jolla h(w) = g(w)? Jos h(w) = g(w), niin w on PCP:n tapauksen (h, g) ratkaisu. Tietysti, h(ε) = g(ε), mutta tyhjä sana ε on triviaali ratkaisu, joka poissuljetaan.

Esim. 5.2

Olkoot h ja g määriteltyjä ehdoista: h(a) = aaab ,

h(b) = a

ja g(a) = a ,

g(b) = baaa .

Tällöin tapauksella (h, g) on ratkaisu w = a3 b3 kuten laskemalla todetaan. ⊓ ⊔

Esim. 5.3

Kun h(a) = aaab ,

h(b) = aa

ja g(a) = a ,

g(b) = baa ,

niin tapauksella (h, g) ei ole ratkaisua (harjoitus). ⊓ ⊔ Yksittäisissä tapauksissa voidaan usein päätellä, kuten edellä, onko PCP:n tapauksella ratkaisua vai ei, mutta yleisesti PCP on ratkeamaton probleema. Tämä voidaan todistaa palauttamalla se Turingin koneiden pysähtymisprobleemaan. Ajatuksena on tällöin generoida kahdella morsmilla, h ja g , annetun TM:n laskuja, konguraatiojonoja γ1 γ2 . . . tyhjälle syötölle siten, että toinen morsmeista generoi jonoa askeleen edellä toista, eli h(x1 . . . xk ) = γ1 γ2 . . . γk ja g(x1 . . . xk ) = γ1 γ2 . . . γk−1 , ja jos joskus konguraatio γn osoittautuu pysäyttäväksi, niin tasataan h:n ja g :n kuvat samaksi sanaksi, h(x1 . . . xn ) = γ1 γ2 . . . γn = g(x1 . . . xn ). 1

Post orresponden e problem

44

5 Ratkeamattomuus

Modioidussa PCP:ssä on annettuna kaksi morsmia h, g ja kirjaimet [ ja ], sekä kysytään onko olemassa w, jolle h([w]) = g([w]), missä w ei sisällä kirjaimia [ ja ]. Seuraavaa todistusta varten muokataan Turingin koneiden pysähtymisprobleema kieliopeille. Tämän lauseen todistus on suoraviivainen, kun tiedetään, että kieliopit pystyvät generoimaan Turingin koneiden hyväksymät kielet, ja kuuluuko ε kieleen, on yhtäpitävää sen kanssa, että Turingin kone pysähtyy tyhjällä nauhalla (eli kun se käynnistyy konguraatiossa qM #). Lause 5.11 On ratkeamatonta generoiko annettu kielioppi tyhjän sanan. Lause 5.12 Modioitu PCP on ratkeamaton. Todistus. Osoitetaan, että annetulle kieliopille G voidaan konstruoida kaksi morsmia h ja g siten, että ε ∈ L(G) jos ja vain jos parilla (h, g) on epätriviaali ratkaisu. Olkoon G kielioppi, jonka produktiot ovat P = {p1 , p2 , . . . , pm } ,

missä pi = ui → vi ,

ja p1 = S → v1 on ainut transitio, joka sisältää alkukirjaimen S (näin voidaan tehdä; muutoin tuotetaan uusi keinotekoinen alkukirjain). Ajatellaan produktioiden joukko P myös aakkostona. Olkoot ∆ = P ∪ V aakkosto, missä V = N ∪ Σ on kieliopin koko aakkosto. Olkoot [, ] ja ⊲ uusia kirjaimia. Määritellään h(a) = a , h(pi ) = vi , h([) = [S⊲ , h(]) = ] ,

g(a) = a , kun a ∈ V ∪ {⊲} , g(pi ) = ui , kun i = 1, 2, . . . , m , g([) = [ , g(]) = ⊲] .

Oletetaan, että G generoi tyhjän sanan, sanokaamme seuraavasti S = w1 −→ w2 −→ . . . −→ wn = ε ,

missä wi = wi1 usi wi2

ja

wi+1 = wi1 vsi wi2

(i = 1, 2, . . . , n − 1)

eli käytetty produktio on psi . Merkitään kullekin i: xi = wi1 psi wi2 ,

jolloin x1 = p1 , ja todetaan, että h(xi ) = wi1 vsi wi2 = wi+1 ,

g(xi ) = wi1 usi wi2 = wi ,

kun i = 1, . . . , n − 1, ja siten h(xi ) = g(xi+1 ) .

Kaikenkaikkiaan sanalle x = x1 ⊲ x2 ⊲ . . . ⊲ xn−1 saadaan

5 Ratkeamattomuus

45

h([x]) = [S ⊲ h(x1 ) ⊲ h(x2 ) ⊲ . . . ⊲ h(xn−1 )] = [S ⊲ w2 ⊲ w3 ⊲ . . . ⊲ wn ] = [S ⊲ g(x2 ) ⊲ g(x3 ) ⊲ . . . ⊲ g(xn )] = [g(x1 ) ⊲ g(x2 ) ⊲ . . . ⊲] = g([x]) ,

ja siten modioidun PCP:n parilla (h, g) on ratkaisu [x]. Toisinpäin tulee osoittaa, että modioidun PCP:n ratkaisu h([x]) = g([x]) tuottaa generoinnin G:lle. Olkoon [x] = [x1 ⊲ x2 ⊲ . . . ⊲ xn−1 ], missä xi ei sisällä kirjaimia [, ] ja ⊲. Koskapa h([) = [S⊲ = g([)S⊲, tulee ratkaisun alkaa [p1 ⊲, ja siten x1 = p1 . Samoin ratkaisun tulee loppua ⊲p], missä p = u −→ ε on terminoiva. Nyt h([x1 ⊲) = [S ⊲ v1 ⊲

ja

g([x1 ⊲) = [S⊲ ,

mistä päätellään, että g(x2 ) = v1 = h(x1 ). Induktiivisesti edeten saadaan, että kukin xi sisältää tarkalleen yhden produktiokirjaimen pi ∈ P, ja että g(xi ) = h(xi−1 ) kaikille i = 2, . . . , n − 1. Morsmien h ja g määrittelyistä (ja `tarkasteluista') seuraa, että h(xi−1 ) −→ ⊔ h(xi ) (i = 2, 3, . . . , n), missä xn = p, jolla h(p) = ε. Väite seuraa tästä. ⊓

Lause 5.13 PCP on ratkeamaton. Todistus. Olkoot (h, g) modioidun PCP:n tapaus, [, ] erikoismerkit, ja d ja e uusia kirjaimia. Määritellään morsmit h′ ja g ′ seuraavasti h′ ([) = dda1 d · dak d , g ′ ([) = ddb1 d · · · dbℓ , h′ (]) = a1 d · dak de , g ′ (]) = db1 d · · · dbℓ de ,

jos jos jos jos

h([) = a1 · · · ak g([) = b1 · · · bk h(]) = a1 · · · ak g(]) = b1 · · · bk

, , , .

ja kaikille kirjaimille a, h′ (a) = a1 da2 d . . . an d jos h(a) = a1 a2 . . . an g ′ (a) = dc1 dc2 d . . . dcm jos g(a) = c1 c2 . . . cm .

Konstruktiossa d toimii ns. epäsynkronoivana kirjaimena. Todetaan, että PCP:n tapauksella (h′ , g ′ ) on ratkaisu h′ (w) = g ′ (w) jos ja vain jos h(w) = g(w), w = [u1 ][u2 ] · · · [ut ], missä ui ∈ (Σ \ {[, ]})∗ ja h([ui ]) = g([ui ]) kaikilla i = 1, . . . , t. Nimittäin, vain kirjaimen [ kuvat voivat olla toistensa preksejä ja kirjaimen ] kuvat toistensa sukseja. Lisäksi, jos [u]v on ratkaisu, niin samoin on [u]; kun taas [u[v ei voi olla ratkaisu, jos u ei sisällä merkkiä ]. ⊓ ⊔

Ratkeamattomia probleemoja kielille PCP on varsin yksinkertainen ratkeamaton probleema, ja niinpä siihen voidaan palauttaa hyvin monia muita ongelmia.

Lause 5.14 CF-kielten leikkauksen tyhjyysprobleema, L(G1 )∩L(G2 ) =?∅, on ratkeamaton.

46

5 Ratkeamattomuus

Todistus. Olkoon (h, g) PCP:n tapaus, missä h, g : Σ ∗ → ∆∗ ovat morsmeja. Määritellään CF-kieliopit Gf , f = h, g , produktioidensa avulla:

PGf = {S → aAf (a)R | a ∈ Σ} ∪ {A → aAf (a)R | a ∈ Σ} ∪ {A → c} ,

missä c on uusi terminaali ja A nonterminaali (ja wR on w:n peilikuva). Tällöin L(Gf ) = {wcf (w)R | w ∈ Σ + } ,

jolloin

L(Gh ) ∩ L(Gg ) = {wcu | h(w) = uR = g(u)}

ja siten leikkaus on tyhjä tarkalleen silloin kun PCP:n tapauksella (h, g) on ratkaisu. Näin ollen PCP:n ratkeamattomuudesta seuraa CF-kielten leikkauksen tyhjyysprobleeman rat⊔ keamattomuus. ⊓ Vastaavasti voidaan osoittaa myös

Lause 5.15 Seuraavat CF-kielten probleemat ovat ratkeamattomia. (1) Ekvivalenssiprobleema: L(G1 ) =?L(G2 ). (2) Universaalisuusprobleema: L(G) =?Σ ∗ . (3) Monimielisyysprobleema: onko G monimielinen? Äärellisiä automaatteja koskevat probleemat ovat säännöllisesti ratkeavia. Poikkeuksena mainittakoon kuitenkin

Lause 5.16 Seuraava probleema on ratkeamaton äärellisille automaateille: annettuna FA:t A ja B , onko näillä aina yhtä pitkät hyväksyvät laskut kaikille sanoille.

PCP ja matriisiprobleemat Olkoot M1 , . . . , Mk 3 × 3-kokonaislukumatriiseja (siis Mi ∈ Z3×3 ). Joukkoa M = {Mi1 · · · Min | n ≥ 1, 1 ≤ ij ≤ k ∀j}

kutsutaan matriisien Mi generoimaksi joukoksi (puoliryhmäksi). M sisältää siis kaikki matriisien Mi muodostamat tulomatriisit. Merkitään matriisin M alkiota ij Mij :llä. Oletetaan, siis, että Mij ∈ Z. Seuraavaa probleemaa kutsutaan nolla oikeassa yläkulmassa -probleemaksi

Probl. 5.1 Annettuna matriisit M1 , . . . , Mk , onko olemassa matriisia M , joka kuuluu annettujen matriien generoimaan joukkoon ja M1n = 0. Olkoon Γ = {a1 , a2 , ..., an } aakkosto ja määritellään funktio σ : Γ ∗ → N σ(ai1 ai2 ...aik ) =

k X

ij nk−j and σ(ε) = 0.

j=1

Sanat ajatellaan siis n-arisiksi luvuiksi ja σ antaa niiden luku arvon kymmenjärjestelmässä. Saadaan siis helposti, että σ on injektiivinen, eli jos σ(u) = σ(v), niin välttämättä u = v . Lisäksi sanoille u, v ∈ Γ ∗ σ(uv) = σ(v) + n|v| σ(u).

5 Ratkeamattomuus

Esim. 5.4

47

Olkoon Γ = {a1 , a2 , a3 }, siis n = 3. Nyt esimerkiksi σ(a1 a1 a3 a2 ) = 1 · 34−1 + 1 · 34−2 + 3 · 34−3 + 2 · 34−4 = 47.

⊓ ⊔

Olkoon n = 2, eli Γ = {a1 , a2 }, ja määritellään kuvaus γ : Γ ∗ × Γ ∗ → Z3×3 by   1 σ(v) σ(u) − σ(v) γ(u, v) = 0 2|v| 2|u| − 2|v|  . 0 0 2|u|

Myös γ on injektiivinen, koska σ on injektiivinen, ja lisäksi sanoille u1 , u2 , v1 , v2 ∈ Γ ∗ , γ(u1 , v1 )γ(u2 , v2 )    1 σ(v1 ) σ(u1 ) − σ(v1 ) 1 σ(v2 ) σ(u2 ) − σ(v2 ) = 0 2|v1 | 2|u1 | − 2|v1 |  0 2|v2 | 2|u2 | − 2|v2 |  0 0 2|u1 | 0 0 2|u2 |   1 σ(v2 ) + σ(v1 )2|v1 | σ(u2 ) − σ(v2 ) + σ(v1 )(2|u2 | − 2|v2 | )   +2|u2 | (σ(u1 ) − σ(v1 ))  = |v1 | |v2 | |v1 | |u2 | |v2 | |u2 | |u1 | |v1 |  0 2 2 2 (2 − 2 ) + 2 (2 −2 ) 0 0 2|u1 | 2|u2 |   1 σ(v1 v2 ) σ(u1 u2 ) − σ(v1 v2 ) = 0 2|v1 v2 | 2|u1 u2 | − 2|v1 v2 |  = γ(u1 u2 , v1 v2 ). 0 0 2|u1 u2 |

Saatiin siis, että

γ(u1 , v1 )γ(u2 , v2 ) = γ(u1 u2 , v1 v2 ).

Lause 5.17 Probleema 5.1 on ratkeamaton 3 × 3-matriiseille. Todistus. Olkoon (h, g) PCP:n tapaus, h, g : Σ ∗ → Γ ∗ . Määritellään matriisit Ma =

γ(h(a), g(a)) kaikille a ∈ Σ . Nyt yllä olevan yhtälön mukaan mukaan matriisille M = Ma1 Ma2 · · · Mam = γ(h(a1 ) · · · h(am ), g(a1 ) · · · g(am )), ja siis M13 = 0

jos ja vain jos σ(h(a1 )h(a2 )...h(am )) = σ(g(a1 )g(a2 )...g(am )),

eli σ(h(w)) = σ(g(w)), missä w = a1 a2 . . . am . Koska σ on injektiivinen, saadaan, että M13 = 0 joss h(w) = g(w), ja väite seuraa PCP:n ratkeamattomuudesta.

Seuraus 5.18 Jos n ≥ 3, niin on ratkeamatonta, onko annettujen n × n kokonaisluku matriisien generoimassa joukossa matriisia M , jolle M1n = 0. Huom. Nolla oikeassa yläkulmassa -ongelman ratkeavuus on avoin 2 × 2-matriiseille. Seuraavaksi tarkastellaan

yhteisen alkion -probleemaa.

Seuraavaksi tarkastellan ongelmaa, jossa kysytään onko kahdessa matriisien generoimassa joukossa samaa matriisia.

48

5 Ratkeamattomuus

Probl. 5.2 Annettuna matriisit M1 , · · · Mk ja N1 , . . . , Nℓ . Onko olemassa matriisia X joka kuuluu sekä matriien Mi että matriisien Nj generoimaan joukkoon. Määritellään seuraavaksi kuvaus γ1 : Σ ∗ × Σ ∗ → Z3×3 , missä  |u|  n 0 σ(u) γ1 (u, v) =  0 n|v| σ(v)  . 0 0 1

Selvästi myös kuvaukselle γ1 on voimassa, että

γ1 (u1 , v1 )γ1 (u2 , v2 ) = γ1 (u1 u2 , v1 v2 ).

Lause 5.19 Probleema 5.2 on ratkematon 3 × 3-matriiseille. Todistus. Olkoon (h, g) PCP: tapaus, missä h, g : Σ ∗ → ∆∗ . Voidaan olettaa, että ∆ ⊆ Σ . Määritellään nyt matriisit Ha = γ1 (a, h(a)) ja Ga = γ1 (a, g(a)) kaikille a ∈ Σ . Nyt, koska σ on injektiivinen,

Ha1 · · · Hak = γ1 (a1 . . . ak , h(a1 ) . . . h(ak )) = γ1 (b1 . . . bt , g(b1 ) . . . g(bt )) = Gb1 · · · Gbt

jos ja vain jos

a1 . . . ak = b1 . . . bt ja h(a1 ) . . . h(ak ) = g(b1 ) . . . g(bt ).

Väite seuraa taas PCP:n ratkeamattomuudesta.

Huom. Edellisessä todistuksessa k = t, vaikka sitä ei oletettu probleemassa 5.2. Seuraus 5.20 Probleema 5.2 on ratkeamaton n × n-matriiseille, kun n ≥ 3. Huom. Myös yhteisen alkion probleema on avoin 2 × 2-matriiseille.

Seuraavaksi tarkasteellan lyhyesti muita tunnettuja matriisiprobleemoja.

Probl. 5.3 (Skolemin ongelma) Annettuna n× n-matriisi M . Onko olemassa lukua k ≥ 1, jolle (M k )1n = 0.

Skolemin ongelmassa kysytään, siis nollaa oikeassa yläkulmassa yhdelle matriisille. Skolemin ongelman ratkeavuus on avoin kun n ≥ 6. Tapauksets n ≤ 5 ovat ratkeava.

Probl. 5.4 (Mortality) Annettuna n × n-matriisit M1 , . . . , Mk . Kuuluuko nollamatriisi matriisien Mi generoimaan joukkoon. Mortality-probleema on ratkeamaton kun n ≥ 3. Tapauksen n = 3 todistuksessa käytetään kuvausta γ1 , tai oikeammin sen transpoosia. Tapaus n = 2 on jälleen avoin.

5 Ratkeamattomuus

49

Ratkeamattomuuden ja ratkeavuuden rajalla Ratkeamattomuuden ja ratkeavuuden välistä rajaa voidaan tutkia muuntamalla (helpottamalla) tunnettua ratkeamatonta ongelmaa. Esimerkiksi matriisiprobleemia käsiteltäessä jaoimme tapauksia dimension mukaan. Useimmissa tapauksissa raja on yhden ja kolmen välissä (tapaus kaksi kun oli avoin). Otetaan esimerkiksi PCP. Tiedetään, että PCP on yleisessä muodossaan ratkeamaton. Tällöin mahdollisia syötteitä ovat kaikki morsmi parit h, g : Σ → ∆, missä Σ ja ∆ ovat mitä tahansa äärellisiä aakkostoja (käytännössä voidaan olettaa, että ∆ ⊆ Σ ⊆ {a1 , a2 , . . . }). Itseasiassa, voidaan aina olettaa, että ∆ = {a1 , a2 }. Tarkastellaan nyt aakkoston Σ kokoa.

Lause 5.21 PCP on ratkeava, kun |Σ| ≤ 2. Todistus. Kun |Σ| = 1, todistus on triviaali. Tapaus |Σ| = 2 on vähän hankalampi. Toisaalta

Lause 5.22 PCP on ratkeamaton, kun |Σ| ≥ 7. Kun aakkoston koko on n, 3 ≤ n ≤ 6, ratkeavuus kysymys on avoin. Näin ollen ratkeamattomuuden ja ratkeavuuden raja on aakkoston kokoa tarkasteltaessa kolmen ja kuuden välissä. Nyt PCP:n ratkeamattomuus raja antaa rajoja edellisen pykälän matriisiprobleemille, tarkemmin matriisien lukumäärille. Esim. lauseen 2 todistuksessa määriteltiin matriisit γ(h(a), g(a)) kaikkille a ∈ Σ . Nyt, koska PCP on ratkeamaton 7:lle kirjaimelle, saadaan, että nolla oikeassa yläkulmassa -probleema on ratkeamaton 7:lle 3 × 3-matriisille. Samalla tavalla lauseen yhteisen alkion -probleema on ratkeamaton, kun matriisi joukot ovat seitsemän matriisin generoimia, eli kun yhteensä 14 3 × 3-matriisia on annettu. Mortality-probleema on ratkeamaton 7:lle matriisille. Toisaalta tiedetään, että mortality ongelma on ratkeamaton kahdelle n × n-matriisille, kun n ≥ 24.

Chur hin teesi Turingin koneet ratkaisevat monenlaisia ongelmia, joista esimerkkeinä olleet ovat sangen vaatimattomia. Seuraava yleisesti luotettu teesi osoittaa Turingin koneiden voiman. Chur hin teesi. Turingin kone on intuitiivisen algoritmin käsitteen formaalinen vastike, eli jokainen algoritmisesti suoritettava tehtävä voidaan suorittaa Turingin koneella.

Erikoisesti, teesi väittää, että jokainen (numeerinen tai sana-) funktio, joka voidaan laskea efektiivisesti (esim. tietokoneohjelman avulla - tai millä muulla tavalla tahansa), voidaan laskea Turingin koneella. Näin muodoin, Chur hin teesin mukaan universaalinen Turingin kone on `ideaalinen tietokone', joka pystyy laskemaan kaikki algoritmisesti laskettavissa olevat tehtävät. Lisäksi teesistä seuraa, että esimerkiksi PCP:tä ei voida algoritmisesti ratkaista millään tavalla! Chur hin teesi ei ole todistettavissa oleva matemaattinen tulos. (Se voidaan toki kumota vastaesimerkin avulla, jos sellainen on olemassa.) Chur hin teesin tueksi on esitetty monenlaisia perusteita.

50 •

•

• • •

5 Ratkeamattomuus Ei ole löydetty tehtävää, joka olisi intuitiivisesti laskettavissa, mutta ei Turingin koneen avulla. Tämä pitää sisällään myös sen, että nykyiset (konkreettiset ja abstraktiset) ohjelmointikielet on simuloitavissa Turingin koneella. Kaikki esitetyt laskettavuuden formaaliset mallit johtavat samaan (tai joskus pienempään) laskettavien funktioiden ja tunnistettavien kielten perheeseen kuin Turingin koneet. Turingin koneiden sulkeumaominaisuudet ovat voimakkaat. Turingin koneiden yleistykset eivät lisää niiden kapasiteettia. Turingin koneen käsite on lähtöisin algoritmin käsitteen analyysistä.

6

Laskennollinen kompleksisuus

Monet laskettavissa olevat ongelmat ovat käytännöllisesti vaikeita (jopa `mahdottomia'), koska ne vaativat tietokoneelta liikaa aikaa ja/tai muistia. Laskennollinen kompleksisuus tutkii ongelmien vaikeutta ajan- ja tilankäytön suhteen. Jäljempänä käsitellään vain ajankäyttöä. Olkoot M TM ja γ1 ⊢ γ2 ⊢ · · · ⊢ γk sen hyväksyvä lasku syöttösanalle w. Tällöin TM (w) = k on M :n käyttämä aika syötöllä w. Sanotaan, että M toimii ajassa f : N → N, jos TM (w) ≤ f (⊲w⊲) kaikilla w ∈ L(M ) . Tässä funktio f on kielen L(M ):n aikakompleksisuus. Turingin koneen hyväksymän kielen aikakompleksisuutta voidaan aina pienentää sopivilla koodauksilla.

Lause 6.1 (Lineaarinen kiihdytys) Olkoot ǫ > 0 annettu reaaliluku ja M TM, joka toimii ajassa f . Tällöin on olemassa TM M ′ , jolla L(M ′ ) = L(M ) ja joka toimii ajassa

f ′ (n) = max{n, ǫ · f (n)}.

Lineaarisen kiihdytyksen takia kielten kompleksisuutta mitataan `ordolausekkeilla': kun f, g : N → N, niin f = O(g), jos on olemassa vakio c > 0 ja luku n0 ∈ N, joilla f (n) ≤ c·g(n) aina kun n ≥ n0 .

Esim. 6.1

n ≥ 4). ⊓ ⊔

2n2 + n + 11 = O(n2 ), sillä 2n2 + n + 11 ≤ 3n2 , kun n ≥ 4 (n + 11 ≤ n2 , kun

Merkitään DT IM E(f ) = {L | on TM M : L(M ) = L ja M toimii ajassa O(f )} .

Kielen L hyväksyminen on polynomiaalista (= `käytännöllistä'), jos jollain k ≥ 1 on L ∈ DT IM E(nk ), ja eksponentiaalista, jos L ∈ DT IM E(cn ) jollain c > 1. Jos L ei ole polynomiaalisesti hyväksyttävissä, kasvaa aikakompleksisuus hyvin nopeasti syöttösanan pituuden mukana, ja hyväksyvä TM (kuten myös hyväksyvä tietokoneohjelma) vaatii pidemmillä syötöillä liian paljon aikaa. Olkoon [ P= DT IM E(nk ) k≥1

polynomiaalisesti hyväksyttävien kielten perhe.

Vastaavat kompleksisuusmäärittelyt voidaan tehdä myös epädeterministisille Turingin koneille: N T IM E(f ) = {L | on NTM M : L(M ) = L ja M toimii ajassa O(f )} ,

52

6 Laskennollinen kompleksisuus NP =

[

N T IM E(nk ) .

k≥1

Yksi suurimmista avoimista probleemoista on, onko P = NP. Perhe NP sisältää lukuisia käytännössä tarvittavia kieliä, joista ei tiedetä ovatko ne P:ssä vai eivät. Toisaalta, jos L ∈ NP, mutta L ∈ / P, niin L:n hyväksyminen ei ole käytännöllistä. NP:ssä on kieliä, jotka ovat NP-täydellisiä, mikä tarkoittaa (erityisesti), että jos tällainen kieli L on polynomiaalisesti hyväksyttävissä, niin NP = P.

Esim. 6.2 Kauppamatkustaja. Syöttö: DFA A.

Päätettävä: onko olemassa sana w siten, että ⊲w⊲ = A:n tilojen lukumäärä ja A vierailee kaikissa tiloissaan hyväksyessään w:n? Tässä tilat q ∈ QA voidaan ajatella kaupungeiksi, ja kysytään voiko kauppamatkustaja suunnitella reittinsä niin, että hän vierailee jokaisessa kaupungissa tarkalleen kerran, ja sitten palaa kotiinsa, kun hän noudattaa A:n antamia reittejä. Tämä probleema on NPtäydellinen. ⊓ ⊔

Esim. 6.3 Selkäreppu. Syöttö: luvut n1 , n2 , . . . , nk

ja luku c. Päätettävä: onko olemassa erilliset indeksit i1 , . . . , it niin, että c=

t X

nij ?

j=1

Tässä c = selkärepun koko, ja ni = tarvikkeen numero i koko. Kysytään voidaanko reppu pakata täyteen. Myös tämä probleema on NP-täydellinen. ⊓ ⊔

Chaitin-Kolmogorovin kompleksisuus: satunnaisjonot Satunnaisluvut ja -jonot ovat hyödyllisiä useissa sovellutuksissa, joissa testataan ohjelmien luotettavuutta. Niinpä, jos testiluku (tai -jono) on jollain tavalla säännöllinen, on mahdollista, että se tuottaa oikean tuloksen pelkästään säännöllisyytensä takia. Mikä sitten on satunnainen jono? Satunnaisjonot ovat useimmiten sangen pitkiä, ja niiden tuottamiseksi tarvitaan siksi tietokoneita. Tietokoneet eivät kuitenkaan toimi satunnaisesti. 1960-luvulla Chaitin ja Kolmogorov esittivät toisistaan riippumatta sanan w satunnaisuuden määrittelyksi pienimmän ohjelma (tai Turingin koneen) koon, joka pystyy sen generoimaan. Niinpä, mitä pitempi ohjelma tarvitaan w:lle sen satunnaisempi se on. Esimerkiksi sana w = babaabaabaabaabb ei ole kovin satunnainen, sillä w = b(aba)4 abb voidaan konstruoida pienehköllä ohjelmalla (jolla on keskellä WHILE-luuppi 1  4). Sanan w = a1 a2 . . . an Chaitin-Kolmogorov kompleksisuus on oleellisesti korkeintaan n, sillä se voidaan generoida äärellisellä automaatilla, jossa on n + 1 tilaa, tai, mikä on sama asia, ohjelmalla: • • •

begin write a1 a2 . . . an ; end

Toisaalta osoittautuu, että varsinaisia epäsatunnaisia sanoja on suhteellisesti ottaen hyvin vähän.

6 Laskennollinen kompleksisuus

Kirjallisuutta Berstel: Transdu tions and Context-free Languages (1979). Eilenberg: Automata, Languages, and Ma hines, Vol. A (1974). Garey, Johnson: Computers and Intra tability: A Guide to the Theory of NP- ompleteness (1979). Harrison: Introdu tion to Formal Language Theory (1978). Hop roft, Ullman: Introdu tion to Automata Theory (1979). Lallement: Semigroups and Combinatorial Appli ations (1979). Lewis, Papadimitrou: Elements of the Theory of Computation (1981). Lothaire: Combinatori s on Words (1983). Salomaa: Formal Languages (1973). Salomaa: Jewels of Formal Language Theory (1981). Wood: Theory of Computation (1987).

53