Rekursiooni ja keerukusteooria eksami konspekt (1)

  1 
Lõplikud automaadid ja regulaarsed keeled. 
DEF: Lõplik automaat on sellise arvuti mudel, millel puudub mälu (või seda on väga vähe). 
DEF: Automaadi M keeleks nimetatakse sõnede hulka A, mida M aktsepteerib. L(M)=A 
DEF: Keelt nimetatakse regulaarseks, kui seda aktsepteerib mingi  deterministlik lõplik automaat. 
Reg. keelest saab teha lõpliku arvu sõnesid. 
Tehted regulaarsete keeltega: 
A∪ ühend nt good, girl, boy, bad 
A◦ konkatenatsioon nt goodboy, 
goodgirl, badboy, badgirl 
A∗  sulund nt ε, good, bad, goodgood, badgood… 
  2 
Regulaarsete keelte omadusi. Regulaarsed avaldised . 
Teoreem : Regularsete keelte hulk on kinnine  ühendi suhtes. 
T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1 ja automaat N2 = 
(Q2,Σ,δ2,Q20,F2) keelt A2. Eeldame, et keeltel pole ühiseid olekuid. 
Ühendi A1 ∪ A2 aktsepteerib lõplik automaat N=(Q;Σ,δ,Q0,F), kus: 
•  ∪ Q1 ∪ Q2, kus q0 on uus olek; 
• Σ on sama, mis N1-l ja N2-l; 
• q0 on automaadi N lähteolek; 
• lõppolekute hulk F = F1 ∪F2; 
Teoreem : Regulaarsete keelte hulk on kinnine konkatenatsiooni suhtes.

T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1 ja automaat N2 = (Q2,Σ,δ2,Q20,F2) keele A2. 
Eeldame, et keeltel pole ühiseid olekuid. 
Keelt A1◦A2 aktsepteerib lõplik automaat N=(Q;Σ,δ,Q10,F2), mille 
konstrueerime järgmiselt: 
• Q = Q1 ∪Q2; 
• Σ on sama, mis N1-l ja N2-l; 
• N lähteolekute hulk on sama, mis automaadil N1; 
• N lõppolekute hulk on sama, mis automaadil N2; 
Teoreem: Regulaarsete keelte hulk on kinnine sulundi suhtes. 
T: Aktsepteerigu automaat N1 = (Q1,Σ,δ1,Q10,F1) keelt A1. 
Keele A1* aktsepteerib lõplik automaat N = (Q;Σ,δ,F1), mille konstrueerime järgmiselt: 
• , kus q0 on uus olek; 
• Σ on sama; 
• lähteolek on q0; 
• N lõ; 
• tühi sõna peab olema aktsepteeritav 
Regulaarsed avaldised on viis keelte defineerimiseks. 
Sõne R tähestikus Σ on regulaarne avaldis , kui ta on esitatav ühel neist kujudest: 
• a, kui a∈Σ; 
• ε; 
• ∅; 
• R1+R2, kui R1 ja R2 on regulaarsed avaldised;  
•  R1R2 , kui R1 ja R2 on regulaarsed avaldised;  
• R1∗, kui R1 on regulaarne avaldis. 
Regulaarse avaldisega R defineeritud keel L(R) on määratud järgmiste seostega: 
• L(R), kui R=a 
• L(R)=∅, kui R=∅ 
• L(R), kui R=ε 
• L(R)=L(R1)∪L(R2), kui R=R1+R2 (kahe keele ühend, kui R on kahe avaldise summa) 
• L(R)=L(R1)◦L(R2), kui R=R1R2 (kahe keele konkatenatsioon, kui R on kahe avaldise korrutis) 
• L(R)=(L(R1))∗, kui R=R1∗ (keele sulund, kui R on avaldise sulund)

DEF: Regulaarsed avaldised on võrdsed, kui nad defineerivad sama keele.  Tehete järjekord : *, ◦, ∪ 
 
  3 
Deterministlikud ja mittedeterministlikud lõplikud automaadid. 
deterministlik - igale olekule vastab täpselt 1 järgmine olek 
Deterministlik lõplik automaat on viisik : 
M = (Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), q0(lähteolek), F(lõppolekud)). 
δ : Q × Σ → Q (mingi olek + sümbol tähestikust = uus olek) 
Mittedeterministlik lõplik automaat on viisik:

M=(Q(olekud), Σ(tähestik), δ(üleminekufunktsioon), Q0(lähteolekud), F(lõppolekud)) 
δ : Q × Σε → P(Q) ükskõik mis tähe puhul või ka ilma sisendita (ε) läheb ühte Q kõigi alamhulkade hulgast.

(üleminekufunktsiooni asemel on hoopis relatsioon ) 
Olgu                     .  Siis hulga A alamhulkade hulk on järgmine:  
Teoreem: Iga mittedeterministik automaat N=(Q, Σ, δ, 
Q0, F), mis aktsepteerib keelt A, on teisendatav sama 
keelt aktsepteerivaks deterministlikuks lõplikuks 
automaadiks 

M = (Q’, Σ, δ′, Q0′, F′). 
Kui mittedeterministlikul on k olekut, siis talle vastaval 
deterministlikul võib olla kuni 2k olekut. 
T: eeldame, et N-is pole ε-üleminekuid.

 
  4 
Regulaarsete avaldiste ja lõplike automaatide samaväärsus. 
Teoreem: Regulaarse avaldisega defineeritud 
keel on aktsepteeritav (mittedeterministliku) 
lõpliku automaadiga. 

T: vastavalt avadlise struktuurile saame 
rekursiivselt teha automaadi: 
Teoreem: Lõpliku automaadi poolt aktsepteeritav keel on defineeritav 
regulaarse avaldisega. 
T: Olgu M = (Q,Σ,δ,Q1,F) lõplik automaat olekute hulgagahulga, mis viivad automaadi olekust qi olekusse qj vahepeal olekuid qk,...,qn läbimata. 
Hulk R0 ij  on lõplik ja seega esitatav regulaarse avaldisega. 
Oletame, et Rk ij on esitatav regulaarse avaldisega, siis on seda ka hulk Rk+1 ij = Rk ij ∪ Rk ik (Rk kk)* Rk kj     
Induktsioonireegli kohaselt on siis regulaarse avaldisega esitatav ka hulk Rij = Rn+1 ij, samuti ka 
L(M). 
  5 
Keele regulaarsuse tarvilik tingimus (pumpamise lemma ). 
Kui L on regulaarne keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p (sõnes on rohkem kui p 
tähte) on jaotatav kolmeks alamsõneks z = uvw, nii et |v| > 0 (keskmine osa pole tühi) ja uvjw ∈ L iga j 
= 0,1,2,... korral. 
T: Olgu L = L (M ), kus M = (Q , Σ, δ , Q0 , F ). 
Valime p = n. Siis sõne z = a1a2...an+1 aktsepteerimiseks peab automaat M tegema n+1 sammu. Järelikult 
vähemalt 1 olek peab korduma. Järelikult uw ∈ L(M), uvw ∈ L(M), uv2w ∈ L(M) jne. < pole regulaarne. Sellise keele jaoks on vaja mälu. 
  6 
Myhill-Nerode teoreem. 
DEF: Olgu keele L ⊆ Σ* (keel on kõigi sõnede hulga alamhulk) jaoks antud ekvivalentsiseos HL ⊆ Σ* × Σ* 
selline, et xHLy kehtib parajasti siis, kui iga z ∈ Σ* korral kehtib xz ∈ L   yz ∈ L (iga suvalise z lisamisel x ja y 
sappa, kuuluvad saadud xz ja yz mõlemad keelde L või ei kuulu mõlemad). 
Teoreem: Keel L on regulaarne parajasti siis, kui seose HL ekvivalentsiklasside hulk on lõplik. 
T: (tarvilikkus) Kui keel L on regulaarne, leidub teda aktsepteeriv lõplik automaat M = (Q , Σ, δ, q0, F). Olgu 
R0i ⊆ Σ* sõnede hulk, mis viib automaadi M lähteolekust q0 olekusse qi. Seose HL ekvivalentsiklass on 
lõplik ühend Cl = R0i1  ∪ R0i2 ∪ . . . ∪  R0il . 
(piisavus) Olgu HL ekvivalentsiklassid C0,…,Cm. Teeme lõ:

Valime algolekuks klassi C0, mis sisaldab  ε-d. Olgu lõppolek Ck ekvivalentsiklass, mis  ühtib keelega L ehk 
kui x ∈ Ck ja x ∈ L, siis kui y ∈ Ck   y ∈ L. Kui x ∈ Ci ja y ∈ Ci, st xz ∈ L yz ∈ L, siis kuuluvad sõned xa ja ya 
ka ühte klassi Cj. Tõepoolest: kui z = az′, siis xaz′ ∈ L   yaz′ ∈ L iga z′ ∈ Σ* korral. Lisame automaati 
sümboliga a märgendatud ülemineku Ci → Cj . Konstrueeritud automaat aktsepteerib keelt L ja on lõplik. 
Järelikult on keel L regulaarne. 
  7 
Fraasisturktuuri grammatikad ja keeled. 
vt punkt 15 
kui α-st saab β ühe tuletusega: vahetult tuletatav α   β 
    DEF: näiteks kui α = γNδ ja β =γφδ  ja grammatikas       
  leidub produktsioon N → φ. 
kui α-st saab β mitme järjest tuletussammuga: 
tuletatav α  + β 
kui α-st saab β k sammuga, kirjutatakse  α  k β; 
kui α = β või α  + β , kirjutatakse α  ∗ β 
    DEF: α  ∗ β, kui mingi k ∈ {0, 1, 2, . . .} korral α  k 
β. 
  8 
KV keeled. KV keelte ühesus. 
DEF: Kontekstivabaks grammatikaks (KV) nimetatakse nelikut G = (N,Σ,P,S), kus N on mitteterminaalide 
tähestik, Σ on terminaalide tähestik (neil pole ühisosa ), P ⊆ N×(N∪Σ)* on produktsioonide lõplik hulk, S on 
lähtesümbol (mitteterminaal).

DEF: KV grammatikaga G = (N,Σ,P,S) genereeritav keel on sõnede hulk L(G) (iga x, 
mis kuulub terminaalide tähestikku ja on produtseeritav lähtesümbolist). 
DEF: Sõnede hulk L on KV keel, kui leidub KV grammatika G, nii et L=L(G). 
DEF: KV-grammatika G on ühene, kui iga sõne x ∈ L(G) korral leidub ainult 1 tuletuspuu (1 vasaktuletus). 
DEF: KV-keel L on ühene, kui kui leidub ühene KV-grammatika G , nii et L = L(G). 
Teoreem: Olgu L1 ja L2 ühesed keeled. Kui L1 ∩ L2 = ∅, siis on keel L1 ∪ L2 samuti ühene. 

T: Oletame, et L1-l ja L2-l on ü on ühesed, <. < ∪ {ambncn | n,m > 0} on mitmene, sest saab mitu tuletuspuud teha. 
  9 
KV grammatika Chomsky normaalkuju . 
DEF: KV  gramaatika  G = (N,Σ,P,S) on Chomsky normaalkujul, kui tema produktsioonid on ühel kujudest: 
A→BC; A→a( terminaal ); S(lähtesümbol)→ε. 


Teoreem: Iga KV keel on genereeritav KV grammatikaga Chomsky normaalkujul. 
T: 1)lisame uue algsümboli S0 ja produktisooni S0 → S (nüüd ükski parem pool ei sisalda lähtesümbolit) 
2) kaotame kõik A → ε. Kui T → Aa ja  A → ε, siis kustutame A → ε ja lisame T → a (sama mis T → εa) 
3) kaotame kõik A → B. Kui T → A ja  A → a, siis asendame T → A kohe produktsiooniga T → a. 
4) sobitame muud reeglid, kasutades abi-mitteterminaale. Nt S→aTb muudame S→AC, lisame A→a, 
C→TB, B→b. 
  10  KV-keelte süntaksanalüüsi ülesanne. CKY- algoritm . 
Cocke-Kasami-Younge’i algoritmi abil saame teada, kas sõne kuulub KV keelde L. 
antud: KV grammatika Chomsky normaalkujul ja sõne w=w1…wn 
tulemus:  accept , kui w selle grammatikaga keelde. Else , reject. 
tehakse püramiidikujuline tabel, mille alumisse ritta pannakse etteantud sõne kõik osad ja igasse tabeli 
lahtrisse kuidas neid kombinatsioone saada. Produktsiooni X → a korral pannakse “a saamise lahtrisse” X.  
Esimeses reas vaadatakse, kuidas saada 1 täht, teises reas, kuidas saada 2 tähte jne

Nt kolme tähe w1w2w3 saamiseks on meil kaks võimalust: w1-w2w3, w1w2-w3

Nelja tähe w1w2w3w4 saamiseks on meil 3 võimalust: w1-w2w3w4, w1w2-w3w4, w1w2w3-w4. 
1) iga w=ε kohta vaata, kui S→ε on reegel, siis accept. Else, reject. 
2) iga A kohta vaata, kui A→wi on reegel, siis pane A tabelisse kohale (i,i) 
3) vaadatakse, kuidas saada kõigi tähtede kombinatsioonid. 
4) kui tabelis kõige kõrgemale (1,n) on tekkinud S, siis accept. Else, reject. 
w1w2w3w4w5w6
w1w2w3w4-w5
w2w3w4w5-w6
w1w2w3-w4
w2w3w4-w5
w3w4w5-w6
w1w2-w3
w2w3-w4
w3w4-w5
w4w5-w6
w1-w2
w2-w3
w3-w4
w4-w5
w5-w6
kuidas saab w1?
w2
w3
w4
w5
w6
w1
w2
w3
w4
w5
w6
  11   Pinuautomaadid . KV grammatikat realiseeriv pinuautomaat. 
Pinuautomaat on lõplik automaat koos magasinmäluga. Magasini saab laadida sümboleid, see on lõpmatu  
DEF: Lõplik pinuautomaat on struktuur M = (Q, Σ( sisendid ), Γ( magasin ), δ, Q0, F) 
δ :Q×Σε×Γε →P(Q×Γε) (hetkeolek x sisend x magasinist loetu = olek x magasini pandu 
Automaat aktsepteerib sõne, kui ta alustab lähteolekust ja tühja magasiniga ning jõuab aktsept . olekusse. 
a,b → c (sisend, magasinist loetu = magasini pandu) ε - sisendist v magasinist ei loeta v ei kirjutata sinna 
Teoreem: Iga KV keel on aktsepteeritav mingi magasinmäluga automaadi abil.  vt üleval . 
Lõpliku magasinmäluga automaadi poolt aktsepteeritav keel on kontekstivaba. KV keelte hulk ongi see 
hulk keeli, mida pinuautomaadid aktsepteerivad. 
  12  Ühe olekuga pinuautomaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus . 
Teoreem: Iga pinuautomaadi M jaoks leidub ühe olekuga M′, nii et nad aktsepteerivad samu keeli. 
T: teeme palindroome (aiassadassaia) aktsepteeriva automaadi, kogu olekute loogika on asendatud 
magasini panemise ja sealt võtmise loogikaga. 
Teoreem: Ühe olekuga pinuautomaadi M jaoks leidub KV grammatika G, nii et L(M)=L(G). 
DEF: KV grammatika on Greibachi normaalkujul, kui tema produktsioonid on kujul A→aA1A2…An või 
A→a (muu on tühi sõne) või kujul S → ε, kui keelde L (G) peab kuuluma ka tühi sõne. 
Iga KV grammatika on teisendatav Greibachi normaalkujule. T: 1) grammatika peab olema Chomsky nk-l. 

2) mitteterminaalid nimetatakse ümber A1-ks, A2-ks jne. 3) produktsioonid asendatakse kujule aA1A2A3… 
Regulaarsete keelte hulk on KV keelte pärisosahulk. Vaatame kasvõi pumpamise lemmasid: uvjw on lihtsalt 
uvjwxjy erijuht ehk uvjwjxjy= u(vwx)jy. 
  13  Taandatud KV grammatikad. 
Iga KV keele jaoks leidub teda genereeriv taandatud KV grammatika: 
1) ε-vaba (puuduvad tühja parema poolega produktsioonid, v.a S → ε, kui ε kuulub sellesse keelde) 
2) ei sisalda kasutuid sümboleid ehk mitteterminale, millest ei saa tuletada terminaalseid sõnesid; 
3) ei sisalda saavutamatuid sümboleid (mis nkn ei teki ühegi produktsiooni käigus kunagi); 
4) tsüklivaba ehk ühegi mitteterminaali ei saa temast endast tuletada. 
1. ja 4. tingimuse täitmiseks piisav, kui eemaldada ε-d ja ahelproduktsioonid. Eemaldada tuleb ka 
sümbolid , milleni nkn kunagi ei jõuta. Ja tuleb vaadata, et S  * wXy  * wxy (lõpuks aint terminaalid). 
  14  KV-keelte tarvilikkuse tingimus. 
Teoreem: Kui L on KV keel, siis leidub konstant p, nii et iga sõne z ∈ L, |z| > p korral saab selle jaotada 

z = uvwxy, kus |vx| > 0 (olemas on nii v kui x), |vwx|