Kordamisküsimuste vastused
Eero Ringmäe
Hulkade spetsifitseerimine, tehted hulkadega, hulgateooria paradoksid.
Hulk:
Korteezh – järjestatud lõplik hulk.
Hulk – mingi arv elemente, mille vahel on leitav seos –
klassifitseeritud elementide kogum.
Hulk – samalaadsete objektide järjestamata kogum.
Hulga esitamine:<<
Tühihulk on iga hulga osahulk .
Iga hulk on iseenda osahulk.
Hulga boleaan – kõigi osahulkade hulk.<. Boleaani võimsus |2H| = 2|H|
Tühja hulga boleaani võimsus on 1.
Tehted:
Hulkade võrdsus = A on B osahulk AND B on A osahulk.
Ekvivalentsiseose definitsioon ((A => B) && (B => A)) –
hulgas sisaldavad samu elemente.
Hulga osahulk – võib võrduda hulgaga .
Hulga pärisosahulk – ei või võrduda.
Hulkade ühend –
Hulkade lõige e ü<
Hulga A täiend A*
A x B hulkade ristkorrutis e otsekorrutis e Descartes '
korrutis<
Paradoksid:
Russelli ehk habemeajaja paradoks (hulga esitamine predikaadi abil):
P(X) = true, kui argumendina esitatud hulk pole iseenda elemendiks .
P(X) = false , kui argumendina esitet hulk on iseenda elemendiks.
Kontrollime hulka<
Eeldades, et Y kuuluks hulka Y, saame P(Y) = false => Y ei kuulu
hulka Y
Eeldades, et Y ei kuulu hulka Y, saame P(Y) = true => Y kuulub Y
Paradokside elimineerimine hulkade hierarhia ja klassifitseerimisega.
Relatsioonid. Ekvivalentsi- ja järjestusseosed.
Relatsioon ehk
seos hulkade A ja B vahel on alamhulk A x
B-le.
Seos hulgal A on alamhulk A x A-le.
Pöördrelatsioon R-1
on relatsiooni täiend.
aRb -> Elemendid a ja b on seoses R
Refleksiivsus - iga a korral aRa (a on iseendaga seoses)
Sümmeetria – iga a korral aRb => bRa (kõik seosed on
vastastikused)
Transitiivsus – iga a korral aRb && bRc => aRc
(põhimõtteliselt järjestusseos)
Ekvivalentsiseoseks nimetatakse seost, mis on refleksiivne,
sümmeetriline ja transitiivne .
Elemendiga a (A element) ekvivalentsete elementide
hulka nimetatakse a ekvivalentsiklassiks
(hulgal A).
Elemendiga a ekvivalentsete elementide hulka
tähistatakse [a]ekvivalentsiseos .
Teoreem 1:
Ekvivalentsiseos R hulgal A. Iga elemendipaari a ja b korral kehtib
seos [a] = [b] või [a] ühisosa [b] on tühihulk.
Tõestus:
Kuna R on sümmeetriline ja transitiivne, näitame, et kui aRb ja suvaline element [a]-st on z, siis sümmeetria tõttu bRa ja aRz –
transitiivsuse järgi bRz ehk siis z kuulub [b].
Siit nähtub, et [b] on alamhulgaks [a]-le.
Analoogselt tõestame, et [a] on alamhulgaks [b]-le.
Kui not(aRb), eeldame vastuväiteliselt, et eksisteerib y, mis kuulub
korraga nii [a] kui [b]. – ehk aRy ja bRy. Sümmeetria tõttu yRb,
millest transitiivuse alusel aRb, mis on vasutolus esialgse väitega.
Voila!
Relatsiooni aste:
R on seos hulgal A. R aste Rk on (aR1b = aRb;
aR2b, kui aRcRb)
aRkb (k>1) on selline relatsioonide järjestus, et (kui
c kuulub A) aRc = cRk-1b.
Suhete ahel. Tee pikkus elementide vahel graafis.
Relatsiooni transitiivne sulund:
R on seos hulgal A. R transitiivne sulund on seos R+
hulgal A nii, et aR+b kehtib parajasti siis, kui
eksisteerib i >= 1 nii, et aRib.
Transitiivne sulund on R-le lisatud vähima paaride arvuga seos, mis
on transitiivne.
Relatsiooni refleksiivne transitiivne sulund:
R on seos hulgal A. R refleksiivne transitiivne sulund on seos R*,
mille korral:
- iga a puhul aR*a
- aR*b kehtib, kui kehtib aR+b
- R* sisaldab parajasti nii palju elemente, kui eelmised tingimused ette näevad
R* on seos, mis on saadud R-le minimaalse arvu paaride
lisamisel nii, et saaksime refleksiivse ja transitiivse seose.
Järjestusseosed:
- osalise järjestuse seos (kõigile saab leida ülem- ja alamelemendid, kuid kõik pole järjestusse seatud):
- transitiivne
- irrefkeksiivne
(näiteks alamhulgaks olemise seos kõigi osahulkade hulgal)
- refleksiivne osaline järjestus (seos R)
- määrab lineaarse järjestuse – kehtib kas aRb, bRa või a = b
Hulgal A on määratud järjestusseos – tähistuseks (A, R)
Näiteks (N, b=c.
Tähistus: M: A -> B
Asjaolu, et (a,b) kuulub M, tähistatakse M(a) = b.
Kujutuse M: A -> B
Liigid:
- osaline kujutus -> Dom(M) on A pärisosahulk (osadele A elementidele on vastavus seatud)
- täielik kujutus -> Dom(M) = A (kõigile A elementidele on vastavus seatud)
- pealekujutus e sürjektsioon -> Dom(M) = A ja Ran(M) = b (osalevad kõik mõlema hulga elemendid)
- üks-üheseks kujutuseks e injektsiooniks kui iga A elemendipaari a,a' ning iga B elemendi b korral kehtib seos:
(f(a) = b AND f(a') = b) => a = a'
(igale elemendile vastavuses
vid üks kindel element)
- bijektsiooniks -> kui kujutus on samaaegselt sürjektsioon ja injektsioon
Idee poolest on kujutus teatud tüüpi vastavus hulgast A hulka B.
Hulgad A ja B on võrdvõimsad,
kui leidub bijektiivne vastavus (M:A
B) nende vahel (ehk siis kõik elemendid mõlemast hulgast on
haaratud ja igaühele vastab vaid 1 kindel element).
Lõpmatut hulka nimetatakse loenduvaks, kui see on võrdvõimas
naturaalarvude hulgaga.
|H| on hulga võimsus
ehk lõpliku hulga korral elementide arv
hulgas. Lõpmatu hulga võimsus leitakse, seades tema elemendid
bijektiivsesse vastavusse (üks-ühesesse) mõne tuntud võimsusega
hulga (näiteks naturaalarvude hulga) elementidega.
Graafid . Puude esitused. Programmide esitamine puuna
Mittejärjestatud ja mitteorienteeritud graaf on paar G = (A,R), kus A on tippude
hulk ja kaarte hulk R on seos hulgal A.
Graafi saab esitada paaride hulgana (A + R analüütiliselt,
või predikaadina) või joonisena.
Graafide võrdsus:
Graafid G1 = (A1, R1) ja G1 = (A2, R2) on võrdsed
ehk isomorfsed, kui leidub selline bijektiivne kujutus f: A1
A2 nii, et aR1b = f(a)R2f(b)
Kui igale tipule a G1-st leidub tipp b G2-st, millele saab vastavusse
seada samade tippude kaared ja kõik G2 tipud saavad ka kaetud.
Kui kaar R1 järgi on esimese graafi tippude vahel, siis on see ka
samade teise graafi tippude vahel ja kui seda pole, pole kummaski.
Graafi märgendus:
Graafi G = (A, R) märgenduseks nimetatakse funktsioonide paari f,g,
kus
f: A
M – tippude märgendus
g: R
L – servade märgendus
Ühesõnaga pannakse igale tipule ja igale servale vastavusse mingid
arvud / tähed / funktsiooni väärtused.
Märgendatud graafid G1 ja G2, mille märgenduste
((f1, g1) ja (f2, g2)) vahel leidub bijektiivne kujutus h: A1
A2, mis
- graafid on võrdsed kui märgendamata graafid (aR1b h(a)R2h(b))
- f1(a) = f2(h(a)) samadele tippudele on samad märgendused
- g1((a,b)) = g1((h(a), h(b))) – samadele tipupaaridele e kaartele on samad märgendused
on võrdsed.
Tippude jada (a1, …, an) nimetatakse teeks
pikkusega n (n >= 1)., kui igast tipust ai
leidub kaar tippu ai+1.
Tsükkel on tee, mille korral a1 = an.
Graaf on tugevalt sidus, kui iga kahe tipu vahel eksisteerib
tee.
Tipu astak sisendite ja väljundite suhtes on vastavalt tipust
sisenevate või tippu väljuvate kaarte arv .
Puud + tsüklivabad orienteeritud graafid:
graafi baas – tippude hulk, mille astak sisendi suhtes 0.
graafi lehed e lõpptipud – mille astak väljundi suhtes 0.
Puu – tsüklivaba graaf, mille baas sisaldab ühe tipu
( juur ), teiste tippude astak sisendu järgi on 1 ja iga tipu jaoks
leidub tee.
Tipu sügavus on juurest temani tuleva tee pikkus.
Tsüklivaba transitiivse orienteeritud graafi kaared määravad
graafi hulgal osalise järjestuse.
Järjestusega Puude esitamine raalis:
- intsidentsusmaatriksina
- viitstruktuurina
- sulgavaldisena (ees-, kesk- ja lõppjärjekorras) – avaldis sugudest, komadest ja puu märgenditest
- Järjestatud puu T eesjärjekord:
avaldis lrep (T), kus
- kui T juur on a, mille vahetud alampuud on T1 .. Tk, siis
lrep(T) = a(lrep(T1), .. , lrep(Tk))
- kui a on terminaalne tipp, siis lrep(T) = a
Juur jääb vasakule – vasakrekursiivne sulgavaldis
- Järjestatud puu T keskjärjekord:
avaldis mrep(T), kus
- kui T juur on a, mille vahetud alampuud on T1 .. Tk, siis
mrep(T) = mrep(T1), a (mrep(T2), .. , mrep(Tk))
- kui a on terminaalne tipp, siis mrep(T) = a
Juur jääb keskele
- Järjestatud puu T lõppjärjekord:
avaldis rrep(T), kus
- kui T juur on a, mille vahetud alampuud on T1 .. Tk, siis
rrep(T) = (rrep(T1), .. , rrep(Tk))a
- kui a on terminaalne tipp, siis rrep(T) = a
Juur jääb paremale
Komad eraldavad sulus sama taseme tippe – sulu ees on selle taseme
juur
Programmi struktuuri esitamine puuna:
Lehed on operandid , juur on operaator .
Varem täitmisele tulevad operatsioonid on kõrgematel astmetel.
Kuna viitstruktuurid liiga mahukad, kasutatakse ees-, kesk- või
lõppjärjekordi.
Selliseid programme saab täita ühe magasiniga raali ja funktsioone
pop(element) ja push (element)
Tõestuste esitamine puudena:
Puu lehed on aksioomid ning teised tipud on teoreemid.
Kaared vastavad tuletusreeglite rakendamisele.
Programmeerimiskeelte klassid .
Arvuti töötleb fikseeritud märgisüsteemis esitatud infot. See
märgisüsteem on keel. Enamus raalis kasutatavatest keeltest
moodustavad programmeerimiskeeled.
Programmeerimiskeel on tähistuste ja reeglite süsteem algoritmide esitamiseks arvutile .
Inimesele sobiva kuju alusel jaotatakse progemiskeeled
- masinkeeled (masinkood – konkreetse raali 01010 jada, autokood – konkreetse raali märgiline progemiskeel)
- algoritmilised e kõrgtaseme keeled (raalist sõltumatute protsesside kirjeldamiseks)
aritmeetilised arvutused algebraliselt
peamiste algoritmiliste juhtstruktuuride jaoks oma laused
IO kirjeldamise laused
erinevad andmetüübid / objektid
- teadmiste esitamise e spetsifitseerimiskeeled
teadmuskeeled, deklaratiivsed keeled
Arvutikeelena võib kasutada mistahes märgisüsteemi, mis on raalile
söödavale kujule teisendatav.
Arvutiprogramm kui translaator, mis tõlgib sisendi väljundiks.
Programmeerimiskeelte formaalne spetsifitseerimine. Transleerimisprotsessi osad.
Raaliga on võimalik lahendada vaid matemaatiliselt
formaliseeritavaid ülesandeid. Seega peab raali keelte jaoks leiduma
formaalne esitus.
Süntaks (teksti sisemine struktuur) versus semantika (teksti väline
tähendus).
Süntaksi esitamine lihtne.
Semantika esitamine peamiselt tõlke, verifitseerimise kaudu.
Süntaksidiagramm kui graaf.
Wirthi diagramm: kast – kasutaja lause
ovaal – reserveeritud sõna
ring - operaator
Võimalik mitu alternatiivset teed.
Plokkskeemid.
Bacus-Nauri formaat.
Transleerimisprotsess:
lause keeles L1
(süntaksanalüüs)
lause süntaktiline struktuur keeles L1
(semantiline analüüs)
Lause süntaktiline struktuur keeles L2
(teksti genereerimine)
Lause keeles L2
NF – nimisõnafraas
TF – tegusõnafraas
OMF – omadussõnafraas
N – nimisõna
T – tegusõna
OM – omadussõna
M – määrsõna
Tehakse puu, kus lause jagatakse üha väiksemateks tükkideks.
Keel kui matemaatiline objekt.
Ehk keel kui stringihulk.
Tähestik ∑
Kõigi stringide hulk ∑*
String :
- Tühi string e
- kui x on string ja a on sümbol, siis ax on string
- ainult nende kahe tingimusega määratud ühendid kuuluvad
Stringide konkatenatsioon (ex = xe = x).
Keel L on alamhulgaks ∑*.
Keelte konkatenatsioon – L = L1 ühend L2, kus L on
alamhulgaks ∑1 ühend ∑2
L = (xy | x kuulub L1 AND y kuulub L2)
Keelte iteratsioon :
L* = ühend ühest n-ni Lk
L0 = e
Ln = Ln-1L, (n>0)
Homomorfism:
∑1 ja ∑2 on tähestikud. Kujutust h: ∑1*
∑2* nimetatakse
homomorfismiks, kui
h(e) = e
h(ax) = h(a)h(x) iga a AND x kuulub ∑1* korral.
Fraasistruktuuri grammatikad . Chomsky klassifikatsioon .
Grammatika:
Formaalne aparatuur keele ja tema fraasistruktuuri esitamiseks.
Keel on teatud tähestiku ∑ stringide alamhulk.< alamhulgaks kõigi
stringide alamhulgale.
Predikaat on semantika aluseks.
Terminaalide tähestik ∑ = keeele tähestik.
Mitteterminaalide tähestik N = hulk fraase tähistavaid
metasümboleid
Stringid tähestikus V = ∑ ühend N on lausevormid.
Teisendusreegel e produktsioon kui lausevormide paar alfa ->
beta.
Generatiivne grammatika e grammatika:
Nelik G = (∑,N,P,S0)
∑ - terminaalide tähestik
N – mitteterminaalide tähestik
P – produktisoonide hulk
S0 – stardisümbol
Lausevormis vahetult tuletatav (vahetu tuletatavus kui binaarne relatsioon hulgal V*, tähistatakse =>G) lausevorm.
Grammatika poolt genereeritav keel L(G).
Grammatikate hierarhia:
0-tüüpi (L0) .. ei lisakitsendusi
1-tüüpi (L1) .. kontekstist sõltuv
iga produktsiooni vasak pool on lühem kui parem pool
välja arvatud S -> e
2-tüüpi (L2) .. kontekstivaba
iga produktsioon kujul A w
A kuulub N, w kuulub V*
3-tüüpi (L3) .. paremlineaarsed keeled
kõik produktsioonid kujul A bC
või A b
A,C kuulub N, b kuulub ∑
L3 on alamhulgaks L2 on alamhulgaks L1 jne.
Regulaarsed avaldised ja hulgad.
Regulaarne hulk tähestikus ∑:
- tühihulk
< – tühjast sõnast koosnev hulk
< kuulub ∑ - ühest terminaalist koosnev hulk
hulk P ühend Q, P lõige Q, Q*, kus P ja Q on regulaarsed hulgad
Regulaarne avaldis regulaarset hulka tähistav lühendkirjapilt, mis
on määratud AINULT järgnevate rekursiivsete reeglitega:
- o – tähistus tühjale hulgale
- e – tähistus tühjast sõ
- a – tä
- regulaarsete avaldiste p ja q, mis tähistavad vastavalt regulaarseid hulki P ja Q korral on regulaaravaldised ka:
Regulaarsed avaldised on võrdsed, kui tähistavad üht ja sama
hulka.
Regulaarsed hulgad tü on paremlineaarsed keeled.
Kui keeled L1, L2 on paremlineaarsed, on paremlineaarsed ka nende
ühend, vahe ja täiend.
Tõestuseks
koostan vastavad grammatikad .. ehk siis näitan kaudset
tuletatavust.
Järeldus:
Regulaarne hulk on genereeritav paremlineaarse grammatikaga
Lõplikud automaadid. Mittedeterministlike automaatide teisendamine deterministlikeks.
Automaat on algoritm , mis lahendab sõna keeles
aktsepteerimise või mitteaktsepteerimise ülesannet.
Lõplik automaat on viisik :
M = (∑,Q, delta ,Q0,F)
∑ sisendtähestik
Q olekusümbolite lõplik tähestik
delta üleminekuf.-n (Q P(Q) ..
lähtuvalt produktsioonidest)
Q0 lähteolekud (alamhulgaks olekutele)
F lõppolekud (alamhulgaks olekutele)
Mittedeterministlick |delta(a,q)| 1
Deterministlick |delta(a,q)| = 1
|delta(a,q)| = n olekus q sümboli
a lugemisel võrdvõimalik minna n olekusse
Konfiguratsioon – paar (w,q) kuulub ∑* x Q
(aktiivne sümbol / lindile jäänud sõna + olek)
lähtekonfiguratisioon – (w,q0) q0 kuulub
algolekute hulka
lõppkonfiguratsioon – (e,r) r kuulub lõppolekute hulka
Töötakt – relatsioon konfiguratsioonide hulgal (aw, q1)
├ (w, q2),
parajasti siis, kui q2 kuulub delta(a,q1) –
kui üleminekufunktsioonis on lubatud a lugemisel minna olekust q1
olekusse q2.
Lõpliku automaadi poolt aktsepteeritav keel:
Ülalmainit' automaat aktsepteerib keele:
T(M)
Regulaarsete avaldiste, lineaarsete grammatikate ja lõplike automaatide samaväärsus.
Iga lõpliku automaadi poolt aktsepteeritav keel on paremlineaarne
Automaat M = (∑,Q,delta,Q0,F). Grammatika G = (∑,Q,P,S).
Produktsioonide hulgaks saab: <
võ
võ
Produktsioonideks on üleminekud olekute vahel (konkateneerides
loetud sümboli olemasolevasse stringi), kus üleminek on
stardisübolist algolekusse, lõppolekusse või olekufunktsiooniga
määratud olekusse.
On ilmne, et:
q =>*G wq' parajasti siis, kui (w,q) ├*
(e,q')
S =>* w parajasti siis, kui w kuulub T(M)
Iga lõpliku automaadi poolt aktsepteeritav keel on regulaarne
hulk
L = T(M); M = (∑,Q,delta,Q0,F)<
Kõigi stringide hulk, mis viivad automaadi olekust qi olekusse qj:<
Kuna automaadi poolt aktsepteeritav keel on selliste stringide hulk
(ühend, kus qi kuulub algolekute, qj lõppolekute hulka), piisab näidata, et iga i,j n, peab mõni olek (näiteks olek r esinema korduvalt,
masinas olema tsükkel – vastasel juhul peaks masina olekute arv
olema lõpmatu).
Masina tsüklilises osas tekibki sõna keskele 0..lõpmatu arv
stringe v.
Siit on näha, et kui keel ei võimalda sellist
genereerimist, siis see kindlasti ei ole paremlineaarne, kui aga
võimaldab, võib see olla paremlineaarne
Kuna pumpamise lemmaga saab näidata keele L =
0n1n
mitteregulaarsuse, saame järeldada, et keelteklasside L3
on alamhulgaks L2-le
sisalduvus on range.
Myhill-Nerode'I teoreem (piisav ja tarvilik tingimus keelte
regulaarsuseks):
Olgu antu keel L stringide hulgast ∑*.
Olgu antud seos HL on alamhulgaks ∑*
x ∑*.
H kehtib stringide x ja y vahel parajasti siis, kui iga stringi z
korral stringid xz ja yz kas kuuluvad korraga keelde L või ei kuulu
sellesse.
HL on ekvivalentsiseos, kuna xzHxz, xzHyz yzHxz,
xzHwz AND wzHyz => xzHyz.
Myhill ja Nerode väitsid, et keel on regulaarne parajasti
siis, kui seose H ekvivalentsiklasside hulk on lõplik.
Tarvilikkuse tõestus:
Moodustame keelt L aktsepteeriva lõpliku automaadi M =
(∑,Q,delta,Q0,F).
Moodustame hulgad:<
Seose H ekvivalentsiklass on esitatav ühendina:
Ck = R0i1 U ... U R0ik
Iga kahe sõna x kuulub R0i ja y kuulub R0i korral masin kas
aktsepteerib neid sõnu korraga või ei aktsepteeri – tuleneb
masina definitsioonist . Sõnu xz ja yz aktseopteerib või ei
aktsepteeri ta samuti korraga – kuna alamsõna analüüs algab
samast olekust ning lõpeb samas.
R0i ei pruugi kokku langeda ekvivalentsiklassiga, kuna ka mõnest
teisest olekust qj lähtudes võib automaat samu sõnu aktsepteerida.
Seega on ekvivalentsiklassiks hulkade ühend.
Basically .. kuna automaadi olekute hulk on lõplik, on lõplik ka
ekvivalentsiklasside hulk.
Piisavuse tõestus:< i = 0,..,m. Algolekuks saab ekvivalentsiklass, mis sisaldab
tühja sõna ().
Kui aga ekvivalentsiklass sisaldab keele sõna, siis kuulub sellesse
ekvivalentsiklassi terve keel (xe kuulub keelde ja ye kuulub keelde). Klassist Ck sagu lõppolek.
Kui x ja y kuuluvad ühte ekvivalentsiklassi, siis kuuluvad sinna ka
terminaali a korral xa ja ya.
Automaati lisame iga oleku Ci ja iga terminaali a jaoks kaare
olekusse Cj.
Nii tagame, et (w,C0) ├*
(e,Ck) – mis tähendab, et automaat aktsepteerib keele – mis
omakorda tähendab, et keel on regulaarne.
KV-keelte süntaksi- ja tuletuspuud.
Süntaksipuu:
Iga järjestatud puu T = (A,R), mille tippude märgendus on antud
kujutusega f, on esitatav termina:
- kui tipp a on terminaalne tipp, siis märgend M = f(a) on term
- kui tipp a on mitteterminaalne tipp märgendiga M = f(a), mille vahetuid alampuid vasakult paremale tähistavad termid t1 .. tn, siis avaldis M(t1,..,tn) on term, mis tähistab puu T alampuud juurega a
Idee poolest sama on lrep(T) – asendame lihtsalt tipud neile
vastavate märgenditega.
Puu kroon Kr(T) = string terminaalsete tippude märgenditest vasakult
paremale kirjutades.
Puu T1 terminaalse tipu A asendamine puuga T2 tä
Märgendatud järjestatud elementaarpuid saab esitada kontekstivabade
grammatikate produktsioonide esitamiseks.
Süntaksipuuks KV-grammatikas
G = (∑,N,P,S)
nimetatakse märgendatud järjestatud puud t, kui iga r kuulub E(t)
korral r
p, p kuulub produktsiooni.
Ehk siis kui iga puu kaar esitab produktsiooni.
Iga puu on üheselt esitatav oma
elementaarpuude nimistuna E(t)
(elementaarpuu on puu, mis koosneb vaid juurest ja terminaalsetest
tippudest).
Märgendatud järjestatud elementaarpuu esitab produktsiooni.
Mitteterminaalist A on tuletatav lausevorm α
parajasti siis, kui grammatikas G leidub tuletuspuu A[α].
Näidata, et see on tarvilik ja piisav ja tingimus sõna
aktsepteerimiseks:
Tarvilik:
Kui string on tuletatav 0 sammuga , siis saame kostrueerida ühest
tipust koosneva puu A[A] – mis on süntaksipuu, kuna vastav
produktsioon on elementaarpuuks.
Iga produktsioon on esitatav elementaarpuuna ja iga elementaarpuu on
kokku kleebvitav suuremaks puuks .
Piisav:
Olgu antud ühe tipuga süntaksipuu – saame 0-sammulise tuletuse .
Iga alampuu esitab terviklikku sõnajupi sünteesi .. igale
elementaarpuule on vastavusse seatav produktsioon ja muud polegi
vaja.
Sõna tuletuspuu:
Täielikku süntaksipuud (mittelaiendatavat süntaksipuud – mille
juureks on lähtesümobl ja lehtedeks ainult terminaalid) ning mille
krooniks on string x nimetatakse sõna x tuletuspuuks.
Sõna kuulub keelde, kui eksisteerib tuletuspuu, mille
krooniks see sõna on.
Tuletuspuu on reeglina ka lause semantika näitaja (mitme tuletuspuu
korral mitmes erinevas tähenduses). Progemiskeelte korral igal
lausel vaid 1 tuletuspuu.
KV-grammatika,
mille korral leidub sõna, millel on mitu tuletuspuud, nimetatakse
mitmeseks.
Teatud mitmestele grammatikatele leidub
ekvivalentseid
üheseid grammatikaid.
KV keelt, millel
leidub ühene genereeriv grammatika,
nimetatakse üheseks, millel ei leidu,
mitmeseks.
KV-grammatika G on ühene, kui ei leidu keelde kuuluvaid sõnu,
mille erinevad vasak-, paremtulemused omaksid erinevaid tuletuspuid
( mitmene grammatika on see, mille korral leidub mitu erinevat
vasaktuletust).
Vasak- ja paremtuletus.
KV-grammatikate redutseerimine.
Keele mittetühjuse kontroll:
IN: KV grammatika G = (∑,N,P,S)
OUT: Jah/Ei
METHOD :
Koostame hulgad N0,N1,… nii, et:
ehk siis need sõnad, mis saab
eelmiste sõnadest produktsioonil ühe
terminaali lisamisega
- Jätkame, kuni lisandub sõnu.
- Kui stardisübol on viimases Ni-s sees, siis keel ei ole tühi, vastasel juhul on.
Saavutamatute sümbolite eemaldamine:
IN: KV grammatika G = (∑,N,P,S)
OUT:
Ekvivalentne KV grammatika G' = (∑',N',P',S),
milles pole saavutamatuid sümboleid ja L(G) = L(G') ja hulk N' U ∑'
ei sisalda saavutamatuid sümboleid
Iga X ε N' U ∑'
korral eksisteerivad stringid α,β
ε (N' U ∑'),
nii et S =>* G
αXβ
METHOD: <, i = 1< U Vi-1
Leiame sellised stringid, milleni viib produktsioon, lisame need
sümbolid tähestikku
Jätkame, kuni lisandub sümboleid, kui ei lisandu, siis
N' = Vi lõige N (jäävad need, mis on mõlemas olemas)
∑'
= Vi lõige ∑
P'
G' = (∑',N',P',S)
Kasutute sümbolite elimineerimine:
Sümbolit nimetatakse kasutuks, kui sellest ei saa tuletada mingit
stringi väljundisse
IN: KV grammatika G = (∑,N,P,S)
OUT: Ekvivalentne KV grammatika G' = (∑',N',P',S),
mille korral L(G) = L(G') ja hulk N' U ∑'
ei sisalda kasutuid sümboleid
METHOD:
- Kasutades keele tühjuse algoritmi , koostame hulga Ne (viimase hulga, millele lisandus sümboleid) ja grammatika G1 = (∑,N lõige Ne,P1,S), kus<
Need produktsioonid, mille parema poole stringid on
saadavad stardisümbolist produktsioonide teel.
- Kasutades saavutamatute sübolite elimineerimise algoritmi, genereerime grammatikast G1 grammatika G'
Grammatikat nimetatakse ε-vabaks, kui ta ei
sisalda ühtegi paremas poolest ε
evivat produktsiooni või on üks produktsioon S
ε ja S ei sisaldu ühegi teise produktisiooni paremas
pooles .
Tühja parema poolega reeglite elimineerimine:
IN: KV grammatika G = (∑,N,P,S)
OUT: Ekvivalentne KV grammatika G', milles pole ε-reegleid
METHOD:
- Keele tühjuse algoritmiga
- Konstrueerime hulga P:
- kui A a0B1a1B2a3 .. Bkak on produktsioon (k>= 0), Bi kuulub Ne, a1 ei kuulu Ne, siis lülitame P koosseisu kõik reeglid kujul
A
a0X1a2X2a3 .. Xkak, kus Xi on Bi või ε (välja arvatud prod
A
ε)
- Kui S ε Ne, lülitada produktsioonide hulka S' S, S' ε ja luua N', vastasel juhul N' = N
Ahelproduktsioonide elimineerimine:
IN: KV grammatika G = (∑,N,P,S)
OUT: Ekvivalentne KV grammatika G', milles pole ahelprduktsioone
METHOD:
need A-st tuletatavad mitteterminaalid, millest ei saa
produktsioonides terminaale
- Kui lisandus elemente, teeme veelkorra, kui ei NA = Ni
- Konstrueerime hulga P', millesse lisame järgmiselt:
- kui produktsioonid B α pole ahelproduktsioon, lisame P'-sse A α kõigi selliste mitteterminaalide A jaoks, mille korral B kuulus NA
Ehk siis .. lisame uue grammatika produktsioonideks need, mille
korral mitte-ahelproduktsioon B ei saa ahelproduktsiooniks
Redutseeritud grammatika definitsioon:
KV grammatikat G = (∑,N,P,S)
nimetatakse redutseerituks, kui see ei sisalda tsükleid, ε-reegleid
ja kasutuid sümboleid.
Iga KV keele jaoks leidub genereeriv redutseeritud grammatika.
KV-grammatikate normaalkujud.
Chomsky normaalkuju :
KV-grammatika G = (∑,N,P,S)
öeldakse olevat Chomsky normaalkujul, kui see sisldab produktsioone
järgnevatel kujudel:
A
BC (kõik on mitteterminaalid)
A
b (b on terminaal , a mitteterminaal)
S
ε (S on lähtesümbol, mis ei esine
ühegi produktsiooni paremas pooles)
Iga KV grammatika evib Chomsky normaalkuju.
Chomsky normaalkuju korral on sõna tuletuspuuks kahendpuu.
Greibachi normaalkuju:
ε-vaba KV grammatika on Graibachi normaakujul,
kui kõik produktsioonid (va S
ε) on kujul A
aα, kus a on terminaal ja α on
mitteterminaal
Mitteterminaali nimetatakse rekursiivseks, kui A =>+ αAβ.
Kui α = ε, siis vasakrekursiivne.
Iga KV keel on genereeritav mitte-vasakrekursiivse grammatikaga.
Teisendamine Greibachi normaalkujule :
- Vasakrekursiooni elimineerimine (redutseeritud grammatika sisendiks)
- Grammatika viimine greibachi normaalkujule
Näide:
- Seame sisse mitteterminaalide järjestus nii, et järjestuses vasakul paiknevad oleksid ka produktsioonides pigem vasakul
- Hakkan järjestuse vasakult vaatama produktsioone, mis evivad antud mitteterminaali vasakus pooles
- kui selles produktsioonis pole vastuolusid mitteterminaalide järjestusega, jäävad
- vastasel juhul asendan need kõigi produktsioonidega, mis evivad sama produktsiooni vasakus pooles
kõik uued mitteterminaalid asetan järjestuses vasakule
kui tekiad vasakrekursiooniga produktsioonid, toon sisse uue mitteterminaali ning kirjutan produktsiooni algama selle mitteterminaaliga. Lisaks kirjutan kõigi produktsioonide koopiad, millles lõpus uus mitteterminaal
- Hakkan mitteterminaalide järjestuses produktsioone, milles antud mitteterminaal vasakus pooles paremalt vasakule läbi käima.
- asendan iga produktsiooni, milles paremal esimesel kohal suurem mitteterminaal hulga produktsioonidega, milles see mitteterminaal on vasakus pooles (ehk siis A>B>C korral ja C BD korral A CB asendan A BDB )
Iga keele jaoks leidub genereeriv grammatika Greibachi normaarkujul.
KV-keelte süntaksanalüüsi ülesanne. CKY- algoritm .
Cocke-Kasami-Youngeri algoritm:
Chomsky normaalkujul oleva grammatika ning terminaalse stringi korral
otsustab, kas sõna kuulub keelde või mitte.
Ühendab kõikvõimalikud tuletuspuud tuletuspäramiidiks.
Tabeli alumise astme laiuseks saab analüüsitava sõna pikkus.
Tipulahtrisse peab tekkima stardisümbol.
Vahepealsetesse lahtritesse kirjutatakse mitteterminaal parajasti
siis, kui ...
Algoritmi tulemusena tekib lahtrisse mitteterminaal A, kui
grammatikas G on esitatav tuletus A
xjxj+1w, sõna kuulub keelde ning tipulahtris
on stardisümbol.
Keerukuseks n pikkuse sõna korral O(n3).
Earley algoritm.
Ülesanne: kas sõna x kuulub grammatikaga G genereeritavasse
keelde L.
Üritame ehitada sõna vasaktuletust.
G produktsiooni A v võib olla
kasutatud sõna w = x1x2...xn (xi on terminaal) vasaktuletamiseks
vaid siis, kui leidub tuletus:
S =>* x1..xiAδ
Kui sõna v koosneb alamsõnadest α ja β
(v = αβ), peab leiduma tuletus:
S =>* x1..xiAδ => x1..xiαβδ =>*x1.xi-1xi..xjβδ (1)
Earley algoritm moodustab massiivi || Iij ||, mille
elementideks on punktiga produktsioonid. A
α.β kuulub Iij koosseisu parajasti siis, kui sõna w = x1..xn
vasaktuletuse võib ehitada ülalnimetatud (1) osatuletuse jätkamise
teel.
Sõna kuulub keelde, kui produktsioon S
v kuulub maatriksi elementi I0n.
Antud: ε-vaba kontekstivaba grammatika + string x = x1 .. xn
keele tähestiku stringide hulgast.
Tulemus: maatriks Iij, kus 0q1 ning ollakse
q1-s niikaua , kuni on sümboleid lugeda. Kui süna on väär,
jäädakse q1 lõpmatusse tsüklisse. Kui sõna aktsepteerit ja läbi,
minnakse q2.
Ühe olekuga magasinmäluga automaatide ja Greibachi mõttes normaliseeritud KV-grammatikate ekvivalentsus .
Iga MMA M jaoks leidub ekvivalentne ühe olekuga MMA M' nii, et T(M)
= T(M')
Teeme ühe lõppolekuga MMA M = (∑,Γ,Q,p,q0,$,F).<
Konstrueerime uue MMA M' = (∑,Γ',Q',p',*,).
Automaadi magasini tähestiku moodustavad sümbolid [sAt] (sümboli A
lugemisel võib masin minna olekust s olekusse t).
Üleminekufunktsioon:
- ([tBx1][x1Cx2][x2Dx3],*) ε p' (a, [sAx3],*) iga oleku x1x2x3 korral, kui automaadi M korral (BCD,t) ε p(a,A,s)
- (ε,*) ε p'(a,[sAt],*), kui M korral kehtib (ε,t) kuulub p(a,A,s)
Masina tööa algab sammudega (w,#,*)├(w,[q0,$q],*)
Igale masina konfiguratsioonile (w,[q1A1q2][q2A2q3]... [qn-1Anqn],*)
vastab
korteež
Et näidata genereeritavate keelte samasust, piisab näidata, et M
korral kehtib seos:
(w,$,q0)├*(w',γ,q)
parajasti siis, kui M' korral kehtib
├* ├
50 punkti
Autor soovib selle materjali allalaadimise eest saada 50 punkti.
~ 37 lehte
Lehekülgede arv dokumendis
2008-01-12
Kuupäev, millal dokument üles laeti
96 laadimist
Kokku alla laetud
0 arvamust
Teiste kasutajate poolt lisatud kommentaarid
Rain Ungert
Õppematerjali autor
annaabi.ee 
Kõik kommentaarid