Üldjuhul on keel lõpmatu hulk ja lõpmatuid objekte on isegi raske defineerida: neid ei saa defineerida lihtsalt elementide loetlemisega. Igasugust lõplikku keele määramise mehhanismi nimetatakse grammatikaks.
Formaalne keel on stringide kogum mingis lõplikus tähestikus. Ametlikud keeled hõlmavad inimese ja masina vahelise suhtluse tehiskeeli – programmeerimiskeeli.
Formaalse keele kirjelduse täpsustamiseks on vaja esiteks määrata tähestik, st objektide kogum, mida nimetatakse sümboliteks (või tähtedeks), millest igaüks saab taasesitada piiramatul arvul koopiatel (nagu tavalised trükitähed või numbrid) ja teiseks defineerida keele formaalne grammatika, st loetleda reeglid, mille järgi sümboleid kasutatakse defineeritavasse keelde kuuluvate jadade – regulaarsete ahelate – koostamiseks.
Formaalse grammatika reegleid võib pidada produktideks (järeldusreegliteks), st elementaartehteteks, mis teatud järjestuses algahelale (aksioomile) rakendatuna genereerivad ainult õigeid ahelaid. Teatud ahela loomise protsessis kasutatav reeglite jada on selle järeldus. Sel viisil defineeritud keel on formaalne süsteem.
Korrektsete ahelate täpsustamise meetodi järgi jagunevad formaalsed grammatikad generatiivseteks ja äratundvateks. Generatiivsete grammatikate hulka kuuluvad keele L grammatika,
millest on võimalik konstrueerida mis tahes “õige” ahel, mis näitab selle struktuuri, ja pole võimalik konstrueerida ühte valet ahelat. Keele L tuvastusgrammatika on grammatika, mis võimaldab kindlaks teha, kas suvaliselt valitud string on õige, ja kui see on õige, siis määrata selle struktuuri. Tuvastamisgrammatika seab suvalise stringi teatud keelde kuulumise kriteeriumi.
Formaalseid grammatikaid kasutatakse laialdaselt lingvistikas ja programmeerimises.
teadmisi loomulike keelte ja programmeerimiskeelte õppimisest.
Automaatsed ja lingvistilised mudelid on üles ehitatud formaalsete grammatikateooria alusel, millele pani aluse N. Chomsky töödes. Peamised objektid, mida see teooria käsitleb, on sümbolid, mis on mis tahes laadi mittetühja hulga A põhielemendid, samuti nendest elementidest koostatud ahelad. Hulka A nimetatakse ka tähestikuks.
Tähistame sümboleid ladina tähestiku väiketähtedega ja ahelaid kujul ffghhh, mida käsitleme vasakult paremale orienteerituna. Samuti tähistame ahelaid erisümbolitega - ladina tähestiku suurtähtedega või kreeka tähtedega, näiteks: = ffg, B = abba. Võtame arvesse tühja ahela , mis ei sisalda ühtki märki.
Keti pikkus on selles ahelas sisalduvate märkide arv.
Keti pikkus on näidatud järgmiselt:
| | = | ffg | = 3;
| B | = | abba| = 4;
Kahe ahela X ja Y konkatenatsioon on ahel Z, mis saadakse vasakpoolse ahela X ja parempoolse ahela Y otsesel liitmisel. Näiteks kui X = ffg, Y = ghh, siis X ja Y konkatenatsioon on ahel Z = ffgghh. Tähistame ühendamistehte sümboliga o. Selle toimingu omadused
saab kirjutada järgmiselt:
1) sulgemisomadus:
o: A* × A* → A*;
2) assotsiatiivsuse omadus:
(∀X ∈ A*, Y ∈ A*, Z ∈ A*) [(X o Y) o Z = X o (Y o Z)],
kus A* tähistab kõigi võimalike ahelate hulka (loomulikult lõpmatu), mis koosneb sõnastiku põhielementide (sümbolite) lõplikust hulgast A, sealhulgas tühi ahel ; tähis x tähistab kahe hulga Descartesiuse korrutise toimimist; ja X, Y, Z on suvalised ahelad, mis kuuluvad rühma A*.
Vaatleme paari (A*, 0). Võttes arvesse tehte o loetletud omadusi, on see paar identiteedielemendiga poolrühm ehk monoid. Algebras nimetatakse poolrühmaks ainult hulka (antud juhul A*), mis on varustatud defineeritud assotsiatiivsete tehtega.
String võib, aga ei pruugi kuuluda keelde L. Igasugust stringide komplekti L ≤ A* (kus A* on monoid) nimetatakse formaalseks keeleks, kui see stringide hulk on defineeritud tähestikus A.
Näide 1. Olgu A hulk vene tähestiku tähti. Siis esindab viiest tähest koosnev stringide komplekt formaalset keelt L1. Teine näide samas tähestikus määratletud keelest on L2 viietäheline komplekt
vene keele sõnad, mida võib leida õigekirjasõnaraamatust. Ai-
võib näha L2 ⊂ L1, kuna paljud L1 keele stringid ei ole venekeelsed sõnad.
Olgu B ja C mingid hulga A* alamhulgad.
Hulkade B ja C korrutis on ahelate hulk D, mis on
mis koosneb B ja C ahelate konkateneerimisest, st.
D = ( X o Y | X ∈ B, Y ∈ C).
Toode on tähistatud järgmiselt: D = BC.
Vaatleme tähestikku A. Tähistame hulka, mis koosneb , A0-ga. Defineeri
jagage tähestiku aste järgmiselt: Аn = An-1 A iga n ≥ 1 jaoks.
Ei ole raske näidata, et kogum kõik võimalikud ahelad tähestiku
Sellist komplekti nimetatakse tähestiku A iteratsiooniks. Tähestiku kärbitud iteratsiooniks
Favita A kutsutakse
Kui X ja Y on hulga A* ahelad, siis ahelat X nimetatakse ahela alamahelaks
pungad Y, kui A*-st on ahelad U ja V sellised, et
Veelgi enam, kui U on tühi ahel, siis alamahelat X nimetatakse ahela peaks
ki Y ja kui V on tühi ahel, siis X nimetatakse ahela Y sabaks.
Kahe stringi X ja Y konkatenatsiooni tähistatakse XY või XY. Vaatleme ahelapaare (P1, Q1), (P2, Q2), ..., (Pn, Qn) alates A* x A*. Thu suhted on reeglid, mille järgi mis tahes väärtust
pung X = U Pi V komplektist A* seostatakse ahelaga Y = U Qi V samast hulgast A* (i = 1, 2, ..., n) ja vastupidi. Need seosed viivad nn assotsiatiivse arvutuseni.
Kui ahel Y saadakse ahelast X ühe Thue seose ühekordse rakendamisega (st alamahela Pi asendamisega alamahelaga Qi), siis ütleme, et X ja Y on külgnevad ahelad.
Ahel Xn on korrelatsioonis ahelaga X0, kui on olemas ahelate jada
X0, X1, ..., Xn,
nii, et X i-1 ja Xi on külgnevad ahelad.
Näide 2. Olgu A see vene tähestiku tähtede hulk, millel
lim Thue suhe, mis seisneb õiguses asendada sõna üks täht mis tahes teisega. Siis on ahelate jadas JAHU, MUUSA, LUZA, VINE, POSE, AEG, PORT, KOOK kõrvuti suvalised kaks külgnevat ahelat ning ahelad JAHU ja KOOK on antud seoste tähenduses korrelatsioonis.
Thue suhete tutvustamine võimaldab paljude keelte hulgas tuvastada teatud keeleklassid, mida kasutatakse erinevat tüüpi automaatsete keelemudelite koostamisel.
Thue seosed on kahepoolsed, kui ahel X külgneb ahelaga Y ja vastupidi, ahel Y külgneb ahelaga Y
ahel X. Formaalsete grammatikateooria seisukohalt huvitavamad on
On suhteid, mille suunas tutvustatakse.
Sel juhul nimetatakse neid Thue semi-relations ehk toodeteks ja kirjeldusteks.
tähendab järgmist:
(P1 → Q1), (P2 → Q2), ..., (Pn → Qn).
Toodete komplekti puhul ütleme, et ahel Y on puudulik.
genereeritakse otse ahelast X ja tähistatakse kui X ⇒ Y, kui on olemas ahelad U ja V,
X = U Pi V, Y = U Qi V,
ja (Pi → Qi) – tooted sellest komplektist.
Öeldakse ka, et X sünnitab Y.
Kui on olemas ahelate jada X0, X1, ..., Xn nii, et iga
enne i = 1, 2, ..., n
X i-1 ⇒ X i,
siis nad ütlevad, et Xn genereeritakse X0-st (X0 genereerib Xn), ja tähistavad seda kui X0 ⇒ * Xn. .
Chomsky grammatikad vastavad formaalsetele kombinatoorsetele skeemidele,
mis on Thue poolsüsteemid, mis põhinevad Thue poolsuhetel
Märkus: Selles jaotises käsitletakse distsipliini põhitõdesid: "formaalne grammatika". See distsipliin käsitleb mis tahes toiminguid sümbolitega ja selle järeldusi kasutatakse laialdaselt formaalsete ja "inimkeelte" analüüsimisel, aga ka tehisintellektis. See loeng on kursuse kõige olulisem ja samas ka kõige raskemini mõistetav loeng. Sellega seoses esitab autor lugejale ainult oma järeldused, jättes välja matemaatilised tõendid. Materjali paremaks mõistmiseks peate võib-olla viitama eelmistele ja järgmistele loengutele.
10.1. Tähestik
Inimene alustab mis tahes keele õppimist tähestikuga. IN formaalne grammatika keel on määratletud sõltumata selle tähendusest. Pealegi võib sama keelt moodustada mitu grammatikat! See on nagu koolis - tulemus (mida saab lugeda õpiku lõpust) pole nii oluline kui selle kättesaamine - vihikusse salvestatud probleemi lahendus. Seetõttu lähenegem tähestiku määratlusele ka formaalselt.
Definitsioon. Tähestik on mittetühi lõplik elementide kogum.
Klassikalises keeles on tähestik tähtede kogum. Foneetikas on inimeste tekitatud kõnehelide kogum. Muusikas on see nootide komplekt jne.
Tähestiku abil on sageli võimalik kirjeldada lõpmatu hulk sõnad Kõigi sõnade kogumit, mida saab grammatika abil luua (teisisõnu grammatika abil genereeritud), nimetatakse keeleks. Erinevalt tähestikust võib keel olla lõpmatu.
Ükskõik milline lõplik järjestus tähestiku tähed nimetatakse sõnaks või professionaalsemalt ahelaks. Tähemärkidest (a, b, c) koosnevad ahelad on järgmised: a, b, c, aa, ab, bc, ac, bb, abba ja teised. Lubatud on ka tühja ahela A olemasolu – sümbolite täielik puudumine. Tähtis on ka tegelaste järjekord ahelas. Niisiis, ahelad ab ja ba on erinevad ketid. Lisaks kasutatakse muutujate ja sümbolitena suuri ladina tähti ning ahelaid tähistavad väikesed ladina tähed. Näiteks:
X = SVT loend 10.1.
string, mis koosneb tähemärkidest S, V ja T ning selles järjekorras.
Definitsioon. Keti pikkus on selle ahela märkide arv. Seda tähistatakse kui |x| . Näiteks: |L| = 0, |A| = 1, |BA| = 2, |ABBA| = 4.
Kui x ja y on stringid, on nende konkatenatsiooniks string xy. Kettide ümberpaigutamine konkateneerimise ajal muudab tulemust (nagu rühmateoorias). Kui z = xy on kett, siis x on ahela pea ja y on ahela saba. Kui me ei hooli keti peast, tähistame:
Z = … x Loetelu 10.2.
ja kui me sabast ei hooli, kirjutame:
Z = x ...Loetelu 10.3.
Definitsioon. Kahe ahelate komplekti korrutis on määratletud kui kõigi nendes komplektides sisalduvate ahelate konkatenatsioon. Näiteks kui hulk A = (a, b) ja B = (c, d), siis:
AB = (ac, ad, bc, bd) Nimekiri 10.4.
Hulkade korrutises, nagu ka konkatenatsioonis, on tegurite järjekord oluline.
Nii ahelate ühendamisel kui ka ahelate korrutamisel jääb assotsiatsiooniseadus tõeseks, kirjutatuna järgmiselt:
Z = (ab)c = a(bc) = abc Nimekiri 10.5.
D = (AB)C = A(BC) = ABC loetelu 10.6.
Ja lõpuks määrame ahela astme. Kui x on mittetühi ahel, siis x 0 = (L), x 1 = x, x 2 = xx, x n = x(x) (n-1). Sama lugu on komplektide astmega.
10.2. Terminali ja mitteterminali sümbolid
Terminali mõiste ja mitteterminaalsed sümbolid on tihedalt seotud asendamise (või tootmise) reegli mõistega. Määratleme selle.
Definitsioon. Tootmis- ehk asendusreegel on järjestatud paar (U, x), mis on kirjutatud järgmiselt:
U::= x Nimekiri 10.7.
kus U on sümbol ja x on mittetühi lõplik märgistring.
Kutsutakse tähemärke, mis ilmuvad ainult paremal pool terminali tähemärgid. Nii reeglite vasakul kui ka paremal küljel leiduvaid sümboleid nimetatakse mitteterminaalseteks sümboliteks ehk keele süntaktilisteks ühikuteks. Trobikond mitteterminaalsed sümbolid tähistatakse kui VN ja terminali tähemärgid- VT.
Märge. See mõiste terminal ja mitteterminaalsed sümbolid kehtib KS-grammatika ja A-grammatika kohta (vt punkt 10.4.3).
Definitsioon. Grammatika G[Z] on piiratud, mittetühi reeglite kogum, mis sisaldab mitteterminaalne sümbol Z vähemalt üks kord reeglistikul. Z-märki nimetatakse algusmärgiks. Järgmiseks me kõik mitteterminaalsed sümbolid tähistame seda kui<символ>.
[Näide 01]
Grammatika: "number"
<число> ::= <чс> <чс> ::= <цифра> <чс> ::= <чс><цифра> <цифра> ::= 0 <цифра> ::= 1 <цифра> ::= 2 <цифра> ::= 3 <цифра> ::= 4 <цифра> ::= 5 <цифра> ::= 6 <цифра> ::= 7 <цифра> ::= 8 <цифра> ::= 9
Anname veel ühe definitsiooni:
Definitsioon. Ahel v genereerib otse ahela w, kui:
V=x y ja w = xuy Nimekiri 10.8.
Kus ::= u on grammatika reegel. Seda tähistatakse kui v => w. Samuti ütleme, et w on otseselt tuletatav v-st. Sel juhul võivad ahelad x ja y olla tühjad.
Definitsioon. Ütleme, et v genereerib w või w taandatakse v-ks, kui on olemas lõplik väljundite ahel u0, u1, …, u[n] (n > 0), et
V = u0 => u1 => u2 => ... => u[n] = w Nimekiri 10.9.
Seda jada nimetatakse tihvtiks pikkusega n ja seda tähistatakse v =>+ w. Ja lõpuks kirjutavad nad:
V =>* w, kui v => w või v =>+ w Nimekiri 10.10.
10.3. Fraasid
Definitsioon. Olgu G[Z] grammatika, x string. Siis nimetatakse x-i lausevormiks if
Definitsioon. Olgu G[Z] grammatika. Ja w = xuy olgu lausevorm. Siis nimetatakse u lausevormiks w for mitteterminaalne sümbol , Kui:
Z =>* x y ja =>+ u Nimekiri 10.11.
Z =>* x y ja => u Nimekiri 10.12.
siis stringi u nimetatakse lihtsaks fraasiks.
Mõistega "fraas" peate olema ettevaatlik. Asjaolu, et =>+ u (ahel u on tuletatav ) ei tähenda, et u on lause vormis x y; on samuti vajalik ahela tuletatavus x y grammatika algsümbolist Z.
Fraasi illustreerimiseks kaaluge [Näide 01] lausevormi<чс>1 . Kas see tähendab, et sümbol<чс>on fraas, kui on olemas reegel:<число> ::= <чс>? Muidugi mitte, kuna aheldamine pole võimalik:<число><1>- algustähest:<число>. Mis on lausekujulised laused?<чс>1 ? Mõelge väljundile:
<число> => <чс> => <чс><цифра> => <чс><1>Nimekiri 10.13.
Seega
<число> =>* <чс>Ja<чс> =>+ <чс>1 Nimekiri 10.14.
Vaatleme formaalset grammatikat, mis mingil määral meenutab vene keele grammatika fragmenti ja täpsustab neljast venekeelsest lausest koosnevat formaalset keelt. See ametlik grammatika kasutab elemente, mis toimivad lauseliikmete või kõneosadena:
<предложение>
<подлежащее>
<сказуемое>
<дополнение>
<прилагательное>
<существительное>
Need elemendid on suletud nurksulgudesse, et eristada neid tegelikest sõnavara sõnadest, mis moodustavad keele laused. Meie näites koosneb sõnastik järgmisest viiest sõnast ehk "tähemärgist": V= (maja, tamm, ebaselge, vana, (punkt)). Grammatikal on teatud reeglid, mis sisaldavad teavet selle kohta, kuidas saab neid sümboleid kasutades mõnes keeles lauseid konstrueerida. Üks neist reeglitest on:
1. <предложение> ® <подлежащее> <сказуемое> <дополнение>.
Seda reeglit tõlgendatakse järgmiselt: "Lause võib koosneda subjektist, millele järgneb predikaat, seejärel objekt ja punkt." Grammatikas võib olla ka teisi reegleid, mis määratlevad erineva struktuuriga lauseid. Selles grammatikas aga selliseid reegleid pole. Ülejäänud reeglid on järgmised:
2. <подлежащее> ® <прилагательное> <существительное>
3. <дополнение> ® <прилагательное> <существительное>
4. <сказуемое>® varjab
5. <прилагательное>® vana
6. <существительное>® koju
7. <существительное>® tamm
Rakendame seda grammatikat lause genereerimiseks (või väljastamiseks).
Vastavalt reeglile 1 näeb lause välja selline:
<предложение>1®<alluvad e><сказуемое> <дополнение> 2 →
2 →<прилагательное><существительное> <сказуемое><lisamine> 3 →
3 →<omadussõna e><существительное> <сказуемое> <прилагательное> <существительное> 4 → Vana <существительное> <сказуемое> <omadussõna e><существительное>
4 →Vana <существительное > <сказуемое> vana <существительное >
6.7 →Vana maja <сказуемое> vana tamm
4 → Vana maja varjab vana tamm
Seega saame valmis ettepaneku:
Vana maja varjab vana tamm.
Seda järeldust võib kujutada puuna. Väljundpuu näitab, milliseid reegleid erinevatele vaheelementidele rakendati, kuid peidab nende rakendamise järjekorra. Seega on näha, et tekkiv ahel ei sõltu vaheelementide asenduste tegemise järjekorrast. Nad ütlevad, et puu on "süntaktiline struktuur" pakkumisi.
Järelduste idee näitab reegliga sarnaseid reeglite muid tõlgendusi <подлежащее> ® <прилагательное> <существительное> . Selle asemel, et öelda " teema See omadussõna, millele järgneb nimisõna", võime seda öelda teema"tekitab" (või "on sellest tuletatud" või "saab asendada")<omadussõna><существительное>.
Ülaltoodud grammatikat kasutades saab tuletada ka kolm teist lauset, nimelt:
Vana tamm varjab vana maja.
Vana maja varjab vana maja.
Vana tamm varjab vana tamme.
Need laused ja varem tuletatud lause on kõik selle grammatika poolt genereeritud laused.
Nendest neljast lausest koosnevat kogumit nimetatakse keeleks, mille määratleb antud grammatika ("selle poolt genereeritud" või "sellest tuletatud").
Üks formaalsetest süsteemidest on asendussüsteem või Thue poolsüsteem (nimetatud Norra matemaatiku Axel Thue järgi), mis on määratletud tähestiku A ja vormi lõpliku asenduste komplektiga:
kus α i,β i on sõnad, mis A-s võib-olla tühjad, Þ on asendussümbol, mida me varem mõistsime kui "vihjet", "tuletatud".
Thue süsteem kasutab seoseid järgmisel kujul:
mõistetakse asenduspaaridena:
α i Þ β i (vasakul);
β i Üα i (paremal).
Thue poolsüsteemis tõlgendatakse asendust α i Þβ i järeldusreeglina R i . Neid poolsüsteeme kasutades kujundas ja arendas Ameerika matemaatik N. Chomsky 50ndatel välja nn formaalsete grammatikate teooria, mis on nende erijuhtum.
Olgu V mittetühi sümbolite kogum – tähestik (või sõnastik) ja seega, arvestades tähestiku V kõigi lõplike sõnade komplekti V *. Tähestiku V formaalne keel L on V * suvaline alamhulk . Niisiis, kui V sisaldab vene keele tähti, kirjavahemärke, tühikumärke jne, siis V * on hüpoteetiline komplekt, mis sisaldab kõiki suure vene kirjanduse teoseid (kirjalikud ja tulevased).
Sümbolitena võib kasutada ka sõnu, matemaatilisi märke, geomeetrilisi kujutisi jne.
Keeled on täpsustatud või määratletud grammatika– reeglite süsteem, mis genereerib kõik antud keele ahelad ja ainult need.
Formaalne grammatika – formaalne süsteem, arvutus.
On olemas formaalsete grammatikate äratundmine, genereerimine ja teisendamine.
äratundmine, kui see mis tahes stringi puhul otsustab, kas see string on antud grammatika tähenduses õige.
Formaalset grammatikat nimetatakse generatiivne, kui see suudab luua mis tahes õige ahela.
Formaalset grammatikat nimetatakse transformatiivne kui mis tahes õigesti ehitatud ahela jaoks koostab see oma kaardistuse õige ahela kujul.
Mõelge generatiivsete formaalsete grammatikate klassile.
G generatiivne formaalne grammatika on nelik
G=
kus T on lõplik mittetühi lõppsümbolite komplekt;
N – mitteterminaalsete (abi)sümbolite lõplik mittetühi hulk;
P on lõplik mittetühi järeldusreeglite kogum (produktsioonid);
S on algusmärk.
T – terminaalsõnastik – algsümbolite kogum, millest ehitatakse grammatika poolt genereeritud ahelad;
N – mitteterminaalne sõnastik – abisümbolite kogum, mis tähistab lähtesümbolite klasse.
Lõplik hulk on grammatika G täielik sõnastik.
Järeldusreegel on lõplik mittetühi binaarseoste hulk kujul φÞψ, kus φ ja ψ on sõnastikus V ahelad, tähis Þ on “asendada”.
Ahel β on grammatikas G otseselt tuletatav ahelast α (tähistus αβ; alamindeks G jäetakse ära, kui on selge, millisest grammatikast jutt käib) kui α=α 1 φα 2, β=α 1 ψα 2, (φÞψ ).
Ahel β on tuletatav α-st, kui on olemas jada E 0 =α, E 1 ,E 2 ,…,E n =β, nii et "i =0,1,...,n-1 E i => E i +1.
Seda jada nimetatakse α väljundiks β ja n on väljundi pikkus.
β tuletavust α-st tähistab α=> n β (kui on vaja määrata tuletise pikkus).
Grammatika G poolt genereeritud keel L(G) on terminaalsõnastiku T stringide kogum, mis on tuletatud S-st, kus S on algsümbol, mis tähistab keeleobjektide klassi, mille jaoks see grammatika on mõeldud. Algsümbolit nimetatakse grammatika eesmärgiks või selle aksioomiks.
Grammatikad G ja G 1 on samaväärsed, kui L(G)=L(G 1).
Loomuliku keele kirjeldamisel formaalsete grammatikateooria seisukohalt tõlgendatakse terminaalseid sümboleid sõnade või morfeemidena - keele väikseimate tähenduslike üksustena (juured, sufiksid jne), mitteterminaalseid sümboleid - sõnaklasside ja fraasid (subjekt, predikaat, predikaadirühm jne. .P.). Märkide jada tõlgendatakse tavaliselt loomuliku keele lausena.
Näide 1. Olgu grammatika antud järgmiselt:
T-(a,b), N-(S,A,B), S-S,
P=(1. SÞaB; 2.SÞbA; 3. AÞaS; 4. AÞbAA; 5. AÞa; 6.BÞbS; 7. BÞaBB; 8. BÞb).
Ettepanekute tüüpilised järeldused:
Kasutatava järeldusreegli number on näidatud noolte kohal sulgudes. Väljund lõpeb, sest ei ole reeglit P, mille vasak pool oleks võrdne ab-ga.
Sellise generatiivse grammatika graafik on näidatud joonisel fig. 125.
Riis. 125. Generatiivse grammatika graafik
Siin on a ja b viimased tipud (terminal).
Näide 2. Olgu grammatika antud järgmiselt:
T=(<студент>, <прилежный>, <ленивый>, <выполняет>, <не выполняет>, <домашнее задание>};
N=(<сказуемое>, <подлежащее>, <определение>, <дополнение>, <группа подлежащего>, <группа сказуемого>, <предложение>};
Saate keti väljastada<прилежный> <студент> <выполняет> <домашнее задание>.
Ilmselgelt on viimane järeldusahel lõplik ja esindab loomuliku keele lauset. Samamoodi saate ahela tuletada<ленивый> <студент> <не выполняет> <домашнее задание>. Pange tähele, et selles näites on mitteterminaalsed sümbolid süntaktilised kategooriad.
Väljundit saab kirjeldada ka nn struktuuripuuga, mis on näidatud joonisel fig. 126.
Riis. 126. Lauseväljundi struktuuripuu
Grammatikat saab täpsustada ka nn Wirthi süntaktiliste diagrammidega - nagu Pascali keeles, mis meenutavad lülitusahelaid, milles jadaühendus tähistab ahelat ja paralleelühendus tähistab ahelate variante - sümboli asemel.
Seega võivad formaalsed grammatikad olla ära tundvad, genereerivad, teisendatavad. Lisaks on formaalsete grammatikateoorias nelja tüüpi keeli, mis on loodud nelja tüüpi grammatika abil. Grammatikat eristatakse järjestikku kasvavate piirangute seadmisega reeglisüsteemile R.
Üldtunnustatud grammatika ja nende loodud keelte klassifikatsioon on Chomsky hierarhia, mis sisaldab nelja tüüpi grammatikat.
Tüüp 0 grammatika on grammatika, milles järeldusreeglitele jÞy piiranguid ei sea, kus j ja y võivad olla mis tahes stringid V-st. Sellist grammatikat saab realiseerida Turingi masin. Sel juhul vastab Turingi masina olek mitteterminaalsetele (abisümbolitele) ja lindil olevad sümbolid vastavad terminali sümbolitele. Kettide genereerimise reegleid kirjeldab käskude süsteem.
Sisestage grammatika 1 on grammatika, mille kõik reeglid on kujul aАbÞawb, kus wÎТUN, A on mitteterminaalne sümbol. Ahelad a ja b on reeglite kontekst. Need ei muutu kasutamisel. Seega 1. tüübi grammatikates läheb üks terminali sümbol A mittetühja stringi w (A saab asendada w-ga) ainult a ja b kontekstis. 1. tüüpi grammatikaid nimetatakse kontekstitundlikeks või kontekstitundlikeks.
Tüüp 2 grammatika on grammatika, milles on lubatud ainult AÞa-kujulised reeglid, kus aÎТUN, s.o. a on V mittetühi ahel. 2. tüüpi grammatikaid nimetatakse kontekstivabadeks või kontekstivabadeks. Kaasaegseid algoritmkeeli kirjeldatakse kontekstivaba grammatika abil.
Sisestage grammatika 3 – omama reegleid kujul АÞaB või AÞb, kus А,ВОN; natuke.
Siin on A,B,a,b vastavate sõnaraamatute üksikud märgid (mitte ahelad). Seda tüüpi grammatikatega määratletud keeli nimetatakse automaatne või tavaline.
Sel juhul kasutatakse vormi regulaaravaldise keelt (tavakeelt):
Sellise keele annab lõplik automaat (Kleene teoreem). Enamikus algoritmilistes keeltes määratakse avaldised lõplike olekumasinate või regulaaravaldiste abil.
Vaatleme näidet tavakeele määramisest piiratud masinaga:
X=(0,1) – sisendsümbolite kogum;
Y=(S,A,B,q k ) – siseolekute hulk, q k – lõppseisund, S – algolek.
Mõnikord vaadeldakse mitut lõppolekut ja kombineeritakse need hulgaks F. Sel juhul F = (q k ).
j: üleminekufunktsioon – mittedeterministlik:
Lõpliku mittedeterministliku automaati üleminekugraafik on näidatud joonisel fig. 127.
Riis. 127. Lõpliku mittedeterministliku automaati siirdegraafik
Vastav generatiivne grammatika on:
Vastav tavakeel L= 
:
0, 010, 01010,...
Formaalsete grammatikate teooriat kasutatakse kompilaatorite konstrueerimisel. Kompilaator parsib lähteprogrammi. Samal ajal tehakse kindlaks, kas antud tähemärkide ahel on õigesti üles ehitatud lause, ja kui on, siis taastatakse selle vorm. Parsimist ehk süntaktilist analüüsi teostab eriprogramm – parser (parse – parse). Selle probleemi lahendamiseks on välja töötatud spetsiaalsed programmid, näiteks LEX ja YACC.
UNIX operatsioonisüsteemil on standardsed programmid LEX ja GREP – need on üles ehitatud tavakeeleteooria alusel.
Programm LEX teostab teksti leksikaalset analüüsi – jagades teksti vastavalt kindlale regulaaravaldiste komplektile.
GREP programm - valib mustri kasutades regulaaravaldist - st. viib läbi kontekstipõhise otsingu ühes või mitmes failis, ehitades samal ajal lõpliku oleku masina, kuhu suunatakse sümbolid sisendsümbolivoost.
Automaattõlkesüsteemides ühest keelest teise tuvastatakse subjekt, predikaat, definitsioon ja täiend; seejärel koostatakse vastav ettepanek vastavalt nõutava keele reeglitele.
Praegu kasutavad arvutid tõlkijaid nagu Promt, Magic Gooddy, Socrat Personal. Lisaks kasutatakse lihtsaid sõnastikke, nagu .Context, Socrat Dictionary, MultiLex.
Keeleteadmiste esitamine formaalsete grammatikate abil on üks teadmiste esitusmudeleid üldiselt, mida kasutatakse sellises valdkonnas nagu tehisintellekti elementidega süsteemid. Tuleb märkida, et teadmised erinevad andmetest näiteks selle poolest, et andmeid tõlgendab tähenduslikult ainult vastav arvutiprogramm ning teadmistes on mõtestatud tõlgendamise võimalus alati olemas. Rakendatakse süsteemide tarkvara- ja riistvaraosa, mis pakuvad kasutajaga loomulikus või loomulikus keeles liidest keeleline protsessor, mille ülesandeks on loomuliku keele tekstide otse- ja pöördtõlge selle sisemise esituse formaalsesse keelde, millega arvuti töötab.
Jaapanis on mõned ettevõtted juba hakanud müüma majapidamises "rääkivaid" roboteid, mis suudavad omanikuga suhelda.
Keelelisel töötlejal on deklaratiivne ja protseduuriline osa. Esimene sisaldab sõnastike kirjeldust, teine - loomuliku keele tekstide analüüsi ja sünteesi algoritmi.
Teadmiste esitamise loogilised mudelid on meile juba tuntud propositsioonide ja predikaatide arvutused.
Teatud ainevaldkonna semantiliste (mõtteliste) teadmiste formaliseerimise aluseks on nn semantilised võrgustikud. Semantiline võrk on suunatud graaf, mille tipud on seotud konkreetsete objektidega ja kaared nendevaheliste semantiliste suhetega. Vertexi sildid on oma olemuselt viitavad ja esindavad teatud nimesid. Nimede rollis võivad olla näiteks loomuliku keele sõnad. Kaarsildid tähistavad suhete komplekti elemente. Lisaks kasutatakse teadmiste esitamiseks raame, mida kõige sagedamini defineeritakse stereotüüpsete olukordade kujutamise andmestruktuurina.
Gödeli teoreemid
Matemaatilises loogikas on tõestatud, et predikaatarvutus on järjekindel – s.t. ei ole võimalik samaaegselt kuvada ja . Lisaks on Gödeli teoreemi alusel predikaatarvutuse täielikkuse kohta tuletatav predikaatarvutuses üldiselt kehtiv valem.
Vaadeldav predikaatarvutus on esimest järku predikaatarvutus. Teist järku arvutuses on võimalikud kvantorid predikaatide järgi, s.t. avaldised kujul "P(P(x))" või funktsioonide järgi.
Seega on kõigi propositsiooniloogika tõeste väidete hulk loendatav ja otsustatav. Predikaatloogika kõigi tõeste väidete hulk on loendatav (täielikkuse tõttu), kuid otsustamatu (aineala lõpmatuse tõttu).
Teise formaalse teooriana matemaatilises loogikas käsitletakse itaalia matemaatiku Giuseppe Peano (1858-1932) välja pakutud nn formaalset aritmeetikat. Peano tutvustas sümboleid ja tehteid O, U, I ning esitas esimesena loogika kui matemaatilise distsipliini. Esimese katse taandada matemaatika loogikale tegi saksa matemaatik ja loogik Gottlieb Frege (1848-1925). Tema oli see, kes määratles komplekti kontseptsiooni mahuna. Ta kirjutas: "Aritmeetika on loogika osa ja see ei tohiks laenata ei kogemusest ega mõtisklustest mingeid tõestusaluseid." Kuulus paradoks kõigi hulkade hulga kohta on vastuolu Frege süsteemis, mille tuvastas Bertrand Russell.
Gödel tõestas, et iga formaalne aritmeetikat sisaldav formaalne teooria T on mittetäielik: see sisaldab suletud valemit F, mis on tõene, kuid ei F ega tuletatav T-st. Gödeli kuulsa mittetäielikkuse teoreemi kohaselt on iga järjekindla formaalse teooria T korral, mis sisaldab formaalset aritmeetikat, T konsistentsi väljendav valem on T-s tõestamatu.
Seega on aritmeetika ja arvuteooria mitteaksimiseeritavad teooriad ning kõigi aritmeetika tõeste väidete hulk on loendamatu.
Gödeli teoreemidel on oluline metodoloogiline tähendus. Selgub, et piisavalt rikkalike matemaatiliste teooriate jaoks puuduvad piisavad formaliseeringud. Tõsi, iga mittetäielikku teooriat T saab laiendada, lisades sellele aksioomina valemi, mis on tõene, kuid mitte tuletatav T-s, kuid ka uus teooria jääb puudulikuks. Lisaks on võimatu uurida teooria metaomadusi kasutades formaalse teooria enda vahendeid, s.t. iga metateooria T peab vähemalt järjepidevuse tõestamiseks olema T-st rikkam.
Seega seatakse kahtluse alla juba lähenemine konstrueerida matemaatikat kui kindlat kindlat vahendite kogumit, mida võiks kuulutada ainsaks legitiimseks ja mille abil ehitada üles mistahes teooriate metateooriaid. Kuid see pole sugugi formaalse lähenemise kokkuvarisemine. Lahendamatute probleemide olemasolu ei tähenda, et konstruktiivne lähenemine ei sobi, kui sellega ei saa midagi teha, siis ainult sellepärast, et keegi ei saa hakkama.
Sisuliselt määratletud teooriate täieliku formaliseerimise võimatus ei ole kontseptsiooni puudus, vaid objektiivne fakt, mida ei saa kõrvaldada ühegi mõistega.
Teooria adekvaatse formaliseerimise võimatus tähendab, et tuleb kas otsida sellest formaliseeritavaid fragmente või ehitada üles tugevam formaalne teooria, mis jääb aga jällegi poolikuks, kuid võib-olla sisaldab kogu algset teooriat.
MITTEKLASSIKALINE LOOGIKA
SISSEJUHATUS……………………………………………….…………….4
Peatükk 1. KEELED JA GRAMMATIKA. SÜMBOLID, MÕISTED JA KLASSIFIKATSIOON………………………………………………………………………………6
1.1. Keelegrammatika mõiste. Nimetused………………………………………………………7
1.2. Grammatikate klassifikatsioon Chomsky järgi…………………………………………………………
1.3. KS- ja A-grammatika koostamise tehnikad………………………………………………………..16
1.4. Süntaktilised järelduspuud KS-grammatikates. Esitus
A-grammatika olekugraafiku kujul. Grammatika mitmetähenduslikkus……………..19
1.5. A-keelte süntaktiline analüüs……………………………………………………..23
Harjutused………………………………………………………………………………….29
Peatükk 2. TUNNISTAJAD JA MASINAD.……………………………….….…………32
Peatükk 3. AUTOMAATGRAMMATIKA JA LÕPETUD MASINAD…………….35
3.1. Automaatsed grammatikad ja lõplikud automaadid……………………………………….35
3.2.Mittedeterministlike ja deterministlike A-grammatikate samaväärsus...... 36
Harjutused…………………………………………………………………………………… 41
4. peatükk. KONTEKSTIVABAD TEISED
JA AUTOMAATGRAMMATIKA………………………………………………..….42
4.2. Ummikreeglite kõrvaldamine grammatikast……………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………………
4.3. Üldistatud KS-grammatikad ja grammatika taandamine pikendavasse vormi…….48
4.4. Vasakpoolse rekursiooni ja vasakpoolse faktoriseerimise elimineerimine………………………………..…52
Harjutused………………………………………………………………………………….53
Peatükk 5. AUTOMAATSETE JA KONTEKSTIVABADE KEELTE OMADUSED…55
5.1. Üldvaade A- ja KS-keelte ahelatest……………………………………………………………………………………………………………
5.2. Operatsioonid keeltes………………………………………………………………………….59
5.2.1. Toimingud CS keeltes……………………………………………………………………………………………………………………………
5.2.2. Tehted A-keeltes…………………………………………………………………………………………………………………………
5.2.3. Tehted K-keeltes…………………………………………………………………66
5.3. Järeldused harjutamiseks…………….………………………………………………………………….67
5.4. KS-grammatika ja keelte mitmetähenduslikkus…………………………………………………………………71
Harjutused…………………………………………………………………………………..74
Peatükk 6. CS-keelte SÜNTAKTILINE ANALÜÜS……………………………...……...75
6.1. CS-keelte analüüsimeetodid. Tähtsuse grammatika……………………..75
6.2. Wirthi eelisjärjekorras grammatikad…………………………………………………………………77
Floydi eelisjärjekorras grammatikad………………………………………………………………79
Tähtsusfunktsioonid…………………………………………………………81
Harjutused………………………………………………………………………………84
Peatükk 7. SISSEJUHATUS SEMANTIKASSE……………………………………………………….85
7.1. Poola pöördtähistus………………………………………………………………..85
7.2. POLIZi tõlgendus………………………………………………………………..87
7.3. Käskude genereerimine POLIZi jaoks…………………………………….……………89
7.4. Zamelsoni ja Baueri algoritm avaldiste tõlkimiseks POLIZ-i………..………….91
7.5. Atribuutide grammatika…………………………………………………………………………………97
Harjutused…………………………………………………………………………………..100
8. peatükk. KOOSTAMISE PEAMISED ETAPID……………………………………...……100
KOKKUVÕTE
RAKENDUS…………………………………………………………………………………105
TEEMA INDEX……………………………………………………….…….…115
Sissejuhatus
Keeleteadus- keeleteadus. Matemaatiline lingvistika- teadus, mis tegeleb keelte konstrueerimise ja õppimise formaalsete meetoditega.
Formaalsete grammatikate teooria- matemaatilise lingvistika osa, sealhulgas meetodid keelte formaalsete grammatikate kirjeldamiseks, meetodite ja algoritmide konstrueerimine ahelate kuuluvuse analüüsimiseks keelde, samuti algoritmide tõlkimise algoritmid masinkeelde.
Selle teooria loomise ja täiustamise tõukejõuks oli arvutitehnoloogia areng ja sellest tulenevalt vajadus suhtlusvahendite järele inimese ja arvuti vahel. Kõigis rakendustes peab arvuti mõistma mõnda keelt, milles kasutaja saab edastada talle probleemide ja algandmete lahendamise algoritme. Igal arvutil on oma masinakäskude keel, mis on esitatud kahendkoodina ja kajastavad protsessori üksikuid toiminguid. Arvutitehnoloogia arengu esimestel etappidel suhtlesid programmeerijad arvutitega selles primitiivses keeles, kuid inimesed ei suuda hästi mõelda masina digitaalse keeles. Programmeerimise automatiseerimine viis esmalt komplekteerimiskeelte ja seejärel kõrgetasemeliste algoritmiliste keelte loomiseni, mille tõlkimine emakeelde usaldati arvutile endale. Selliseid tõlkeprogramme nimetatakse ringhäälinguorganisatsioonid.
Paljud tarkvaraarendajad seisavad silmitsi masinale keele selgitamise probleemiga. Inimesele on omane uusi keeli välja mõelda. Siin ei räägi me ainult uute algoritmiliste programmeerimiskeelte keerukatest kompilaatoritest. Iga automatiseeritud süsteem peab mõistma mõnda sisestuspäringu keelt. Uued infotehnoloogiad hõlmavad lõppkasutaja (teadlane, disainer, tehnoloog, operaator) - konkreetse valdkonna, mitte arvutitehnoloogia ja programmeerimistehnoloogia valdkonna spetsialisti, kaasamist oma probleemide lahendamisesse arvutis. Selle probleemi kvaliteetseks lahendamiseks peab kasutaja ja arvuti vahel eksisteerima intelligentne liides: kasutaja peab püstitama probleeme ja saama nende lahenduse tulemused talle teadaolevas ainevaldkonnas. See tähendab, et on vaja välja töötada lai valik domeenispetsiifilisi keeli. Tarkvaraspetsialist peab teadma, kuidas keeli luuakse ja nende tarkvara tuge.
Masinale keele selgitamiseks peab meil olema selge arusaam, kuidas see töötab ja kuidas me sellest aru saame. Sellele mõeldes näeme, et me ei tea, kuidas me oma emakeelt mõistame. Selle mõistmise protsess on alateadlik ja intuitiivne. Kuid tõlkija loomiseks on vaja algoritmi teksti tõlkimiseks toiminguteks, mida see tekst nõuab, ja see omakorda nõuab keele vormistamine. Keele formaliseerimise probleeme lahendab matemaatiline lingvistika. Loomulikud keeled on liiga keerulised ja neid pole veel võimalik täielikult vormistada. Algoritmilised keeled, vastupidi, on juba loodud formaliseerimist silmas pidades. Formaalsete keelte teooria on matemaatilise lingvistika kõige arenenum haru, mis sisuliselt kujutab endast tehnikat keele masinale seletamiseks. Enne selle teooria definitsioonide, mudelite ja meetodite uurimist vaatleme mõningaid mõisteid, kasutades näiteid loomulikest keeltest.
Keel- teatud reeglite järgi koostatud lausete (fraaside) kogum.
Grammatika- reeglite kogum, mis määrab, kas fraas kuulub mõnda keelde.
Iga keel peab rahuldama otsustatavuse ja ühemõttelisuse omadusi.
Keel on lahendatav, kui lõpliku aja jooksul on võimalik kindlaks teha, et fraas või lause kuulub keelde. Keel on ühemõtteline, kui mõnda fraasi mõistetakse ainulaadsel viisil.
Grammatika peamised osad on süntaks ja semantika.
Süntaks- reeglistik, mis määrab keele lausete õige ülesehituse.
Semantika- reeglite kogum, mis määrab keele lausete semantilise või semantilise korrektsuse.
Lause võib olla süntaktiliselt õige ja semantiliselt vale.
Süntaksit lihtsustab tavaliselt asjaolu, et kõik keele fraasid ei pea olema mõistlikud. Sageli on raske mõista futuristide tähendust või mõne poliitiku sõnavõttu. Sellega seoses on huvitav akadeemik L. V. Shcherba näide: "Glokka kuzdra shtekol on bokr kiilas ja ta kõverdab bokrenkat." See on venekeelne fraas, kuna lause liikmed saavad seda sõeluda, kuid selle tähendus on ebaselge.
Fraasi süntaktilise analüüsi saab kirjutada parsipuu kujul. Puu sõlmed, nagu subjekt, predikaat, subjektirühm, lause vastavad süntaktilistele mõistetele ja lehed on sõnad, millest lause on üles ehitatud. Lõigates maha osa puu lehti ja oksi, saame sentiaalse vormi (järeldatava ahela).
<предложение>
Fraasi mitmetähenduslikkuse olemust saab selgitada sama parsipuu näitel fraasi "Ema armastab oma tütart" jaoks.
See fraas on mitmetähenduslik, kuna sellel on kaks sõelumisvalikut. Süntaktiline mitmetähenduslikkus toob otseselt kaasa semantilise mitmetähenduslikkuse. Kuid võite pakkuda ka näiteid süntaktiliselt üheselt mõistetavatest fraasidest, mis ei pruugi sõnade mitmetähendusliku tähenduse tõttu aru saada. Tuletagem meelde, et algoritmiline keel peab olema üheselt mõistetav.
Formaalne keel on matemaatiline abstraktsioon, mis tekkis tavaliste keelemõistete üldistamisel loomulikes keeltes. Formaalsete keelte teooria uurib peamiselt keelte süntaksit ja on süntaktiliselt juhitud tõlkeprotsesside alus, mis hõlmab tõlkimist, koostamist ja kompileerimist. Selle teooria aluse pani 50ndate lõpus ja 60ndate alguses Ameerika matemaatik N. Chomsky ning see areneb koos arvutitehnoloogia arenguga tänapäevani. Vaatleme selle teooria põhielemente.