Žinome kalbų jungimo operacijas. Apibrėžkime sujungimo ir iteracijos (kartais vadinamos Kleene uždarymu) operacijas.

Tegul L 1 ir L 2 yra kalbos abėcėlėje

Tada, t.y. kalbos sujungimas susideda iš visų pirmosios kalbos žodžių sujungimų su visais antrosios kalbos žodžiais. Visų pirma, jei , tada ir jei , tada .

Įveskime kalbos L „laipsnių“ žymėjimą:

Taigi, L i apima visus žodžius, kuriuos galima suskirstyti į i eilės žodžius iš L .

Kalbos L iteraciją (L) * sudaro visi žodžiai, kuriuos iš L galima suskirstyti į kelis iš eilės einančius žodžius:

Jis gali būti pavaizduotas naudojant laipsnius:

Dažnai patogu laikyti „sutrumpintą“ kalbos iteraciją, kurioje nėra tuščio žodžio, jei jo kalboje nėra: . Tai nėra nauja operacija, o tiesiog patogus išraiškos trumpinys.

Taip pat atkreipkite dėmesį, kad jei abėcėlę laikome baigtine kalba, susidedančia iš vienos raidės žodžių, tada anksčiau įvestas visų žodžių, įskaitant tuščią, aibės žymėjimas abėcėlėje atitinka šios kalbos iteracijos apibrėžimą.

Šioje lentelėje pateikiamas formalus indukcinis apibrėžimas reguliarios išraiškos per abėcėlę ir kalbas, kurias jie atstovauja.

Išraiška r	Kalba L r
	L a =(a)
Tegul r 1 ir r 2 yra	L r1 ir L r2 -atstovaujami
reguliarios išraiškos.	jų kalbos.
Tada šios išraiškos
yra reguliarūs	ir atstovauja kalboms:
r=(r 1 +r 2)
r = (r 1 circr 2)
r=(r 1) *	L r = L r1 *

Įrašant reguliarios išraiškos Mes praleisime sujungimo ženklą ir darome prielaidą, kad operacija * turi didesnį prioritetą nei sujungimas ir +, o sujungimas turi didesnį prioritetą nei +. Tai leis praleisti daug skliaustų. Pavyzdžiui, galima parašyti kaip 10(1 * + 0) .

Apibrėžimas 5.1. Du reguliarios išraiškos R ir p laikomi lygiaverčiais, jei jų atstovaujamos kalbos yra tos pačios, t.y. L r = L p . Šiuo atveju rašome r = p.

Nesunku patikrinti, pavyzdžiui, toliau nurodytus dalykus reguliarios savybės operacijos:

• r + p= p+ r (sąjungos komutaciškumas),
• (r+p) +q = r + (p+q) (sąjungos asociatyvumas),
• (r p) q = r (p q) (sujungimo asociatyvumas),
• (r *) * = r * (iteracijos idempotencija),
• (r +p) q = rq + pq(paskirstymas).

5.1 pavyzdys. Įrodykime, kaip pavyzdį, ne tokią akivaizdžią lygybę: (r + p) * = (r * p *) *.

Tegul L 1 yra kalba, pavaizduota jos kairiąja puse, o L 2 – dešine. Tuščias žodis priklauso abiem kalboms. Jei žodis yra netuščias, tai pagal iteracijos apibrėžimą jis gali būti vaizduojamas kaip kalbai priklausančių požodžių junginys. Tačiau ši kalba yra kalbos L"=L r * L p * poaibis (kodėl?). Todėl . Ir atvirkščiai, jei žodis , tai jis pavaizduojamas kaip požodžių, priklausančių kalbai L ", junginys. Kiekvienas iš tokių požodžių v yra atvaizduojamas forma v= v 1 1 ... v k 1 v 1 2 ... v l 2, kur visiems i=1, ... , k yra požodis, o visiems j=1, ... , l yra požodis (gali būti, kad k arba l lygus 0). Bet tai reiškia, kad w yra požodžių junginys, kurių kiekvienas priklauso ir todėl .

Įprasti rinkiniaiir reguliariąsias išraiškas

Įprasti rinkiniai

Šiame skyriuje apžvelgsime baigtinio žodyno grandinių rinkinių, kuriuos labai lengva apibūdinti tam tikromis formulėmis, klasę. Šie rinkiniai vadinami įprastais.

1 apibrėžimas.Leisti V 1 Ir V 2 - daug grandinių. Apibrėžkime tris operacijasšiuose rinkiniuose.

Sąjunga: V 1 V 2 =(|   V 1 ) arba   V 2 .

Sujungimas (gaminys, klijavimas): Vl V2 = (|  V 1 ,  V 2 ) Sujungimo operacijos ženklas dažniausiai praleidžiamas.

Pavyzdys: V, = (abc, ba), V 2 = (b, cb). V1V2 =(abcb, abccb, bab, bacb).

V n pažymėkime n aibių sandaugą V:V n =VV...V,V° =() (čia  tuščia grandinė).

Pavyzdys: V 1 = (abc, ba), V 1 2 = (abcabc, abcba, baba, baabc).

3. Iteracija: V* = V 0 V 1 V 2 ... =   =0 ∞ V n .

Pavyzdys: V = (a, bc), V* = (, a, bc, aa, abc, bcbc, bca, aaa, aabc,...).

Apibrėžimas 4.13.Įprastų rinkinių klasė baigtiniame žodyne V apibrėžtivyksta taip:

sąjunga ST;

ST sujungimas;

iteracija S* ir T*.

5. Jei aibės negalima sudaryti baigtiniu 1-4 taisyklių taikymo skaičiumi, tai ji yra netaisyklinga.

Įprastų aibių pavyzdžiai: (ab, ba)* (aa); b)(c)(d, ab)*). Netaisyklingų aibių pavyzdžiai: (a n b n | n > 0); ( | grandinėje  simbolių a ir b pasikartojimų skaičius sutampa).

Reguliarūs reiškiniai

Įprastos aibės yra geros, nes jas labai paprastai galima apibūdinti formulėmis, kurias vadinsime reguliariosiomis išraiškomis.

2 apibrėžimas.Reguliariųjų reiškinių klasė, palyginti su baigtiniu žodynu V apibrėžtivyksta taip:

jų suma R1+R2;

jų produktas R1R2;

jų iteracija R1* ir R2*.

4. Jei išraiška nesukonstruota taikant taisykles 1-3 iki galo, tai ji nėra reguliari.

Darbo simbolio galima praleisti. Norint sumažinti skliaustų skaičių, kaip ir bet kurioje algebroje, naudojami operacijų prioritetai: iteracija turi aukščiausią prioritetą; darbas turi mažesnį prioritetą; papildymas turi žemiausią prioritetą.

Reguliariųjų reiškinių pavyzdžiai: ab + bа*; (aa)*b + (c + dab)*.

Akivaizdu, kad reguliarūs rinkiniai ir reguliarios išraiškos yra labai artimi. Tačiau jie atstovauja skirtingus subjektus: įprastas rinkinys yra grandinių rinkinys (bendruoju atveju begalinis) ir reguliarioji išraiška yraformulė, schematiškai rodanti, kaip atitinkama reguliari aibė buvo sudaryta naudojant aukščiau išvardytas operacijas(ir ši formulė yra baigtinė).

Tegul R^ yra reguliarioji aibė, atitinkanti reguliariąją išraišką R. Tada:

Taigi reguliarioji išraiška yra baigtinė formulė, apibrėžianti begalinį skaičių grandinių, tai yra kalba.

Pažvelkime į reguliariųjų reiškinių ir juos atitinkančių kalbų pavyzdžius.

Įprasta išraiška	Atitinkama kalba
	Visos eilutės, prasidedančios raide b, po kurių eina savavališkas simbolių skaičius a
	Visos a ir b eilutės, kuriose yra tiksliai du b atvejai
	Visos a ir b grandinės, kuriose simboliai b yra tik poromis
(a+b)*(aa+bb)(a+b)*	Visos a ir b grandinės, turinčios bent vieną gretimų a arba b porą
(0+1)*11001(0+1)*	Visos 0 ir 1 grandinės, turinčios subgrandę 11001
	Visos a ir b eilutės, pradedant a ir baigiant b

Akivaizdu, kad eilučių rinkinys yra reguliarus tada ir tik tada, kai jį galima pavaizduoti reguliariąja išraiška. Tačiau tą patį grandinių rinkinį galima pavaizduoti skirtingomis reguliariosiomis išraiškomis, pavyzdžiui, grandinių rinkinys, susidedantis iš simbolių a ir turintis bent du a, gali būti pavaizduotas reiškiniais: aa*a; a*aaa*; aaa*; a*aa*aa* ir kt.

3 apibrėžimas.Dvi reguliarios išraiškos R1 Ir R2 vadinami lygiaverčiais (žymimi Rl = R2) tada ir tik tadaR1 ^ = R2 ^ .

Taigi, aa*a = a*aaa* = aaa* = a*aa*aa*. Kyla klausimas, kaip nustatyti dviejų reguliarių išraiškų ekvivalentiškumą.

Teorema1 . Bet kurioms reguliariosioms išraiškoms R, S Ir T šviesus:

Šiuos ryšius galima įrodyti patikrinus atitinkamų grandinių aibių lygybę. Jie gali būti naudojami norint supaprastinti reguliariąsias išraiškas. Pavyzdžiui: b (b + aa*b) = b (b + aa*b) = b ( + aa*) b = ba*b. Vadinasi, b (b + aa*b) = ba*b, o tai nėra akivaizdu.

Kleene teorema

Reguliarios išraiškos yra paskutinės formulės, apibrėžiančios įprastas kalbas. Tačiau baigtinių būsenų mašinos taip pat turi panašią savybę – jos taip pat apibrėžia kalbas. Kyla klausimas: kaip kalbų klasės, apibrėžtos baigtinių būsenų mašinomis ir reguliariosiomis išraiškomis, yra susijusios viena su kita? Pažymėkime Ir daug automatinių kalbų, R yra įprastų kalbų rinkinys. Amerikiečių matematikas Stephenas Kleene'as įrodė tokią teoremą.

Teorema2 . (Kleene'o teorema.) Taisyklingųjų aibių ir automatų kalbų klasės sutampa, tai yra A = R .

Kitaip tariant, kiekvieną automato kalbą galima nurodyti formule (reguliariąja išraiška), o kiekvieną reguliariąją aibę gali atpažinti baigtinis automatas. Šią teoremą įrodysime konstruktyviai, dviem etapais. Pirmuoju žingsniu įrodysime, kad bet kuri automato kalba yra reguliarioji aibė (arba, kas yra tas pats, bet kuriam baigtiniam automatui galime sukurti reguliariąją išraišką, nurodančią šio automato atpažįstamą kalbą). Antrame žingsnyje įrodysime, kad bet kuri reguliarioji aibė yra automatų kalba (arba, kas yra tas pats, iš bet kurios reguliariosios išraiškos galima sukonstruoti baigtinį automatą, įleidžiantį tiksliai atitinkamos reguliariosios aibės grandines).

Pereinamojo grafo modelį pristatykime kaip baigtinio automato modelio apibendrinimą. Pereinamajame grafe yra viena pradinė ir savavališkas galutinių viršūnių skaičius, o nukreiptos briaunos pažymėtos, skirtingai nei baigtinis automatas, ne simboliais, o reguliariosiomis išraiškomis. Perėjimo grafikas įleidžia grandinę a if A priklauso grandinių aibei, aprašomai reguliariųjų reiškinių sandauga R 1 R 2 ...R n , kurie žymi kelią nuo pradinės viršūnės iki vienos iš galinių viršūnių. Perėjimo grafiko leidžiamų grandinių rinkinys sudaro jo leidžiamą kalbą.

Ryžiai. 1. Perėjimo grafikas

Fig. 1 paveiksle parodytas perėjimo grafikas, leidžiantis, pavyzdžiui, grandinę abbca, nes kelias s->r->p->s->r->q, vedantis į galutinę būseną q, yra pažymėtas grandine reguliarios išraiškos ab* c*a. Baigtinės būsenos mašina yra ypatingas perėjimo grafiko atvejis, todėl visos kalbos, kurias priima būsenos mašinos, taip pat palaiko perėjimo grafikus.

3 teorema.Kiekviena automato kalba yra įprastas rinkinys, A  R.

Įrodymas. Pereinamasis grafikas su viena pradine ir viena galutine viršūne, kuriame vienintelė briauna nuo pradinės iki galutinės viršūnės pažymėta reguliaria išraiška R, įleidžia kalbą R^ (1 pav.).

Ryžiai. 2. Perėjimo grafikas, leidžiantis taisyklingą kalbą FT

Įrodykime, kad kiekviena automato kalba yra taisyklinga aibė, sumažindami bet kurį pereinamąjį grafą, nekeisdami jo leidžiamos kalbos į ekvivalentinę formą (2 pav.).

Bet kurį baigtinį automatą ir bet kurį pereinamąjį grafą visada galima pavaizduoti normalizuota forma, kurioje yra tik viena pradinė viršūnė su tik išeinančiomis briaunomis ir tik viena galutinė viršūnė su tik įeinančiomis briaunomis (3 pav.).

Ryžiai. 3. Pereinamasis grafikas su viena pradine ir viena galutine viršūne

Naudojant normalizuotą perėjimo grafiką, galima atlikti dvi redukcijos operacijas – briaunų mažinimą ir viršūnių sumažinimą – išsaugant šio perėjimo grafiko leidžiamą kalbą:

a) šonkaulių sumažinimas:

B ) viršūnės sumažinimas (pakeitimas atliekamas kiekvienam keliui, einusiam per viršūnę p, po to jos atmetimas kaip nepasiekiama būsena):

Akivaizdu, kad kiekviena redukcinė operacija nekeičia kalbos, kurią atpažįsta pereinamasis grafikas, bet sumažina arba briaunų skaičių, arba viršūnių skaičių, o galiausiai redukcija perėjimo grafiką pateiks į formą, parodytą Fig. 2. Įrodyta teorema: kiekviena automato kalba yra taisyklinga aibė.

Pavyzdys

Tegul baigtinė mašina A yra duota:

Sukuriame lygiavertį perėjimo grafiką normalizuota forma.

3 viršūnės sumažinimas:

Lankų sumažinimas ir taisyklės R = R taikymas:

2 viršūnės sumažinimas:

Lanko ir viršūnės 1 sumažinimas:

Taigi automato A atpažįstamą kalbą suteikia reguliarioji išraiška: R A = b+(a+bb)(b+ab)*a.

Įrodykime Kleeno teoremą kita kryptimi.

2 teorema.Kiekvienas įprastas rinkinys yra automatinė kalba: R A.

Įrodymas. Parodykime, kad kiekvienai reguliariajai išraiškai R galima sukonstruoti baigtinį automatą A r (galbūt nedeterministinį), kuris atpažįsta R nurodytą kalbą. Tokius automatus apibrėžsime rekursyviai.

(sujungiamos pradinės ir galutinės A būsenos).

Pavyzdys(tęsinys)

Automatų teorija – tai teorijos skyrius valdymo sistemos, tiriantis diskrečiųjų informacijos keitiklių matematinius modelius, vadinamas kulkosvaidis. Tam tikru požiūriu tokie keitikliai yra ir realūs įrenginiai (kompiuteriai, automatai, gyvi organizmai ir kt.), ir abstrakčios sistemos (pavyzdžiui, formali sistema, aksiomatinės teorijos ir kt.), leidžiančios pritaikyti teoriją automatai įvairiuose moksliniuose ir taikomuosiuose tyrimuose. Automatų teorija glaudžiausiai susijusi su matematine logika ir algoritmų teorija. Visų pirma, kai kurių formalių skaičiavimų išsprendžiamumas įrodomas naudojant automatų teorijos priemones.

Kitas svarbus šio kurso studijų dalykas yra formalią kalbą 1 – savavališkas tam tikros abėcėlės žodžių rinkinys. Formalių kalbų svarbą teoriniam informatikos mokslui lemia tai, kad paprasčiausias ir patogiausias kompiuterių programose naudojamas duomenų modelis yra baigtinė seka, kurios kiekvienas elementas yra paimtas iš tam tikros iš anksto nustatytos baigtinės aibės. Kadangi programose naudojamos formalios kalbos paprastai yra begalinės, reikalingas būdas formalią kalbą apibūdinti ribotai. Šiame kurse išnagrinėsime 3 klasikines šio aprašymo priemones: kulkosvaidis, reguliarios išraiškos Ir generatyvinės gramatikos.

Įvadas

1. Pagrindinės formaliųjų kalbų teorijos sampratos

Apsvarstykite netuščią baigtinę aibę A, sudarytas iš simbolių ( a 1 , …, a k). Mes paskambinsime A abėcėlė , o jo simboliai yra laiškus . Vadinama bet kokia baigtinė šios abėcėlės raidžių seka žodyje (grandine arba linija ): w=a 1 a 2 …a n- žodis ( a i A), |w| – žodžio ilgis (žodį sudarančių raidžių skaičius, kiekvienas simbolis kartojamas tiek kartų, kiek w). Per | w| bžymi simbolio pasikartojimų skaičių b už žodį w.

Begalinė abėcėlės raidžių seka A paskambino superžodis , – begalinio skaičiaus raidžių superžodis A. Tuščia yra žodis, kuriame nėra nė vienos raidės. Jis žymimas . Akivaizdu, kad ||=0.

- daug abėcėlės žodžių A ilgio n. Visų abėcėlės žodžių rinkinys A(įskaitant superžodžius) yra nurodyta A*. Ši aibė yra skaičiuojama, nes ji yra skaičiuojamo skaičiaus baigtinių aibių sąjunga
. Visų netuščių žodžių abėcėlėje rinkinys Ažymimas A+ . Jeigu A={a), tai A*={a)* bus žymimas A*.

Bet koks poaibis
paskambino liežuvis (formalią kalbą ) virš abėcėlės A.

Jeigu x Ir y– kalbos žodžiai
, tada žodis xy(žodžio priskyrimo rezultatas adresužodžio pabaigoje X) vadinamas sujungimas (sankaba , dirbti ) žodžiai X Ir adresu.
(n paimkime vieną kartą X). Padėkime
.

Jie sako, kad žodis X – požodis žodžius adresu, Jei y=uxv už kai kuriuos žodžius u Ir v. Visi kalbos pokalbiai
forma daug požodžių kalba L, kuris žymimas Subw( L).

Pavyzdžiai. 1. ba 3 =baaa,
- šis žodis turi požodžius ab, aba, ba ir taip toliau.

2. Nustatyti ( a, abb) - kalba (galutinė) virš abėcėlės ( a, b}.

3. Daug
yra kalba virš abėcėlės ( a, b). Ši kalba yra begalinė, joje yra žodžių b, ba, aba, baa, abaa, baaa, aabaa, abaaa ir tt

Kadangi kiekviena kalba yra rinkinys, galime apsvarstyti kalbų jungimo, susikirtimo ir skirtumo operacijas, apibrėžtas ta pačia abėcėle. Taip, kalba
, Kur
, vadinamas kalbos papildiniu L dėl abėcėlės A. Ir jei  visada įtraukiamas į A*, tada kalba
gali būti arba negali būti . Pastaruoju atveju
.

Leisti ,
. Tada kalba vadinama sujungimas (sankaba , dirbti ) kalbomis Ir . Kuriame
,
(n kartus), jei n>0.

Pavyzdžiai. 1. Jeigu
,
, Tai.

2. Jei L=(0, 01), tai
.

Iteracija kalba L vadinama kalba
(ši operacija taip pat vadinama Kleene žvaigždutė ). Kalba
paskambino teigiama iteracija kalba L.

Pavyzdys. Jeigu A={a, b) Ir L={aa, ab, ba, bb), tai
.

Pagal apeliaciją arba veidrodiniame vaizde žodžius wžodis vadinamas w R, kuriame žodžio raidės w eikite atvirkštine tvarka. Pavyzdžiui, jei w=bac, Tai

Leisti
. Tada liežuvis
paskambino apeliacija kalba L.

Vadinsime kiekvieną žodžio pradžią priešdėlis , ir kiekviena žodžio pabaiga - priesaga . Pavyzdžiui, jei y=xv, Tai X– žodžio priešdėlis adresu(pavadinimas – X[y), A v– žodžio priesaga adresu(pavadinimas – v]y). Akivaizdu, kad tuščias žodis yra bet kurio žodžio priešdėlis ir priesaga. Visi kalbos žodžių priešdėliai
forma daug priešdėlių šios kalbos: Pref( L)
. Panašus į Suf( L)
-m priesagų peilis kalba
.

Jei kalba L ar tai ne žodis L nėra jokio kito žodžio priešdėlis (priesaga). L, tada jie taip sako L turi priešdėlis (priesaga) nuosavybė .

Leisti A 1 ir A 2 – abėcėlės. Jei ekranas f:
atitinka visų žodžių sąlygą
Ir
, tada atvaizdavimas f paskambino homomorfizmas .

Pastabos. 1. Galima įrodyti, kad jeigu f tai yra homomorfizmas
.

2. Homomorfizmai ne visada yra dviprasmybės, bet kiekvienas homomorfizmas yra vienareikšmiškai nulemtas jo reikšmės vienaraidiuose žodžiuose.

3. Homomorfizmo taikymas kalbai L, gauname kitą kalbą f(L).

Jeigu f:
- homomorfizmas,
Ir
, tada per f(L 1) nurodyta kalba
, ir per
nurodoma kalba
ir pats ekranas
paskambino homomorfizmo inversija .

Pavyzdžiai. 1. Tarkime, kad kiekvieną 0 simbolį eilutėje norime pakeisti simboliu A, ir kiekvienas 1 atvejis įjungtas bb. Tada galime apibrėžti homomorfizmą f Taigi
Ir
. Jeigu
, Tai
.

2. Leiskite f yra homomorfizmas, kuriam
Ir
. Tada
Ir
.

Šiame skyriuje pradedame pristatyti formaliųjų kalbų teorijos elementus.

Kai sakome „formalioji kalba“, turime omenyje, kad čia pateikti rezultatai pirmiausia naudojami apibūdinant dirbtines kalbas, kurias žmonės sugalvojo specialiais tikslais, pavyzdžiui, programavimo kalbas. Tačiau tarp specialiai išrastų dirbtinių (formaliųjų) kalbų ir spontaniškai atsirandančių bei besivystančių natūralių kalbų nėra neįveikiamos kliūties. Pasirodo, natūralioms kalboms būdingos sudėtingos gramatinės taisyklės, t.y. yra gana griežtai formalizuoti, ir net labiausiai „moksliškai išvystytoje“ programavimo kalboje yra „tamsiųjų vietų“, kurių vienareikšmiškas supratimas yra problema.

Mokantis kalbų reikia nepamiršti trijų pagrindinių aspektų.

Pirmasis yra kalbos sintaksė . Kalba yra tam tikras „žodžių“ rinkinys, kur „žodis“ yra tam tikra baigtinė „raidžių“ seka - tam tikros iš anksto nustatytos abėcėlės simboliai. Sąvokos „raidė“ ir „žodis“ gali būti suprantamos įvairiai (matematinis šių terminų apibrėžimas bus pateiktas toliau). Taigi „raidės“ iš tikrųjų gali būti kokios nors natūralios ar formalios kalbos, pavyzdžiui, rusų kalbos ar Paskalio programavimo kalbos, abėcėlės raidės. Tada „žodžiai“ bus baigtinės „raidžių“ sekos: krokodilas, „ sveikasis skaičius". Tokie žodžiai vadinami „leksemomis". Bet „raidė" gali būti „žodis" („leksema") kaip visuma. Tada „žodžiai" yra natūralios kalbos sakiniai arba programavimo kalbos programos. Jei koks nors rinkinys „Raidės“ yra fiksuotos, tada ne kiekviena jų seka bus „žodis“, t. y. tam tikros kalbos „Eleksema“, o tik seka, kuri paklūsta tam tikroms taisyklėms. Žodis „krykadil“ nėra leksema rusų kalboje, o žodis „iff“ nėra Paskalio leksema. Sakinys „Aš tave myliu“ nėra teisingas sakinys rusų kalba, kaip ir užrašas „x:= =t“ nėra taisyklingai parašytas Paskalio priskyrimo operatorius. Kalbos sintaksė* – tai taisyklių sistema, pagal kurią galima sudaryti „teisingas“ „raidžių“ sekas. Kiekvienam kalbos žodžiui būdinga tam tikra tai konkrečiai kalbai būdinga struktūra. Tada reikia, viena vertus, sukurti tam tikros struktūros žodžių surašymo arba generavimo mechanizmus, kita vertus, mechanizmus, skirtus patikrinti, ar duotas žodis priklauso tam tikrai kalbai. Visų pirma, būtent šiuos mechanizmus tiria klasikinė formaliųjų kalbų teorija.

Antras aspektas - kalbos semantika . Semantika** apima kalbos žodžių susiejimą su tam tikra „reikšme“, reikšme. Pavyzdžiui, rašydami matematinę formulę turime laikytis tam tikrų sintaksinių taisyklių (skliaustelių išdėstymas, simbolių rašyba, simbolių tvarka ir kt.). ), bet, be to, formulė turi labai apibrėžtą reikšmę, ji kažką reiškia.

Kalba yra komunikacijos ir informacijos perdavimo priemonė. Jei norime būti suprasti, turime ne tik sintaksiškai teisingai konstruoti savo kalbą, laikydamiesi tinkamos raidžių žodyje ir žodžių tvarkos sakinyje, bet ir rūpintis jos reikšme, mintimis, kurias išreiškiame kalboje. Matematinės „prasmės“ teorijos atsirado palyginti neseniai, be to, kitame skyriuje labai trumpai apžvelgsime kai kuriuos programavimo kalbų semantikos matematinio aprašymo būdus.

* Žodis „sintaksė“ kilęs iš senovės graikų „syn“ – „kartu“ ir „taksi“ – „tvarka, struktūra“. Taigi sintaksė gali būti suprantama kaip „kompozicija“.

** Iš senovės graikų žodžių "sema" - "ženklas, ženklas" ir "semanticos" - "žymi".

Galiausiai trečias aspektas – kalbos pragmatika . Pragmatika siejama su tikslais, kuriuos sau kelia gimtoji kalba: pavyzdžiui, žmogus taria kalbą turėdamas tikslus, susijusius ne su sintaksė, ne su kalbos, kuria jis kalba ar rašo, semantika, o, tarkime, su kalbos gavimu. tam tikra pinigų suma už savo kalbą.pinigų sumos. Pragmatika veikiau yra socialinė-filosofinė disciplina, veikianti individo tikslų nustatymo veiklą. Mes to nė trupučio neliesime.

Šiame skyriuje pirmiausia bus nagrinėjamos pagrindinės formaliųjų kalbų matematinės teorijos sąvokos, tarp kurių svarbiausia yra generatyvinės gramatikos samprata, o vėliau – vadinamosios taisyklingosios kalbos. Taisyklingųjų kalbų teorija kartu su baigtinių automatų teorija sudaro visos formaliųjų kalbų teorijos pamatą.

• Abėcėlė, žodis, kalba

• Generacinės gramatikos

  Kaip jau minėta, klasikinė formaliųjų kalbų teorija pirmiausia tiria kalbos sintaksę. Jame pristatomas matematinis sintaksės modelis, apibūdinantis „gerai suformuotų“ grandinių generavimo ir atpažinimo mechanizmus. Šiame skyriuje apžvelgsime pirmąjį iš šių mechanizmų.

Laboratorinis darbas Nr.3

Leksinio analizatoriaus kūrimas yra gana paprastas, jei naudojama įprastų kalbų ir baigtinių automatų teorija. Pagal šią teoriją to paties tipo leksemų klasės laikomos formaliosiomis kalbomis (identifikatorių kalba, konstantų kalba ir kt.), kurių sakinių rinkinys aprašomas naudojant atitinkamą generatyvinę gramatiką. Be to, šios kalbos yra tokios paprastos, kad jas generuoja paprasčiausia gramatika – įprasta gramatika.

1 apibrėžimas. generatyvinė gramatika G = , kurių taisyklės turi tokią formą: A::=aB arba C::=b, kur A, B, C Є N; a, b Є Т vadinamas reguliariu (automatiniu).

Kalba L (G), kurią sukuria automatinė gramatika, vadinama automatine (įprastine) kalba arba kalba su baigtiniu skaičiumi būsenų.

1 pavyzdys. Identifikatorių klasė, jei identifikatorius yra seka, susidedanti iš raidžių ir skaičių, o pirmasis identifikatoriaus simbolis gali būti tik raidė, aprašoma tokia generatyvine reguliaria gramatika G = , kuriame

N = (I, K), T = (b, c), S = (I),

P = ( 1. I::= b

Čia b, c yra apibendrinti terminalo simboliai, skirti atitinkamai žymėti raides ir skaičius.

Identifikatoriaus „bbcbc“ generavimo procesas aprašomas tokia pakeitimų seka

I => bbc => bbc => bbcK => bbcbK => bbcbc

Tačiau pagrindinis LA uždavinys – ne leksinių vienetų generavimas, o jų atpažinimas. Taisyklingos kalbos atpažinimo proceso matematinis modelis yra skaičiavimo įrenginys, vadinamas baigtinių būsenų mašina (FA). Terminas „ribinis“ pabrėžia, kad skaičiavimo įrenginys turi fiksuotą ir baigtinį atminties kiekį ir apdoroja įvesties simbolių seką, priklausančią kokiai nors baigtinei aibei. Yra įvairių KA tipų, jei KA išvesties funkcija (darbo rezultatas) yra tik nuoroda, ar įvesties simbolių seka priimtina ar ne, tokia KA vadinama galutinis sprendėjas.

2 apibrėžimas. Šie penki vadinami baigtiniu automatu:

A = , kur V = (a 1 , a 2 , …, a m ) – įvesties abėcėlė (baigtinė simbolių rinkinys);

Q = (q 0 , q 1 , …, q n -1 ) – būsenų abėcėlė (baigtinė simbolių rinkinys);

δ: Q ×V →Q – perėjimo funkcija;

q 0 Є Q – baigtinio automato pradinė būsena;

F Є Q – galutinių būsenų rinkinys.

Erdvėlaivio veikimo schema.

Yra begalinė juosta, padalinta į langelius, kurių kiekvienoje gali būti po vieną simbolį iš V. Ant juostos parašyta grandinėlė α Є V*. Langeliai grandinės kairėje ir dešinėje yra tušti. Yra galutinis valdymo įtaisas (FCU) su skaitymo galvute, kuri gali nuosekliai nuskaityti simbolius iš juostos, judant juosta iš kairės į dešinę. Šiuo atveju valdymo blokas gali būti bet kurios vienos būsenos nuo Q. Valdymo blokas visada pradeda savo darbą pradinėje būsenoje q 0 ir baigiasi vienoje iš galutinių būsenų F. Kiekvieną kartą, pereinant į naują langelį juosta, valdymo blokas pereina į naują būseną pagal funkciją δ.

Erdvėlaivio perėjimo funkciją galima pavaizduoti šiais būdais:

· Komandų rinkinys;

· Būsenos diagrama;

· Pereinamoji lentelė.

Būsenos mašinos komanda parašyta taip:

(q i, a j) → q k, kur q i, q k Є Q; a j Є V.

Ši komanda reiškia, kad būsenos mašina yra q i būsenoje, nuskaito simbolį a j iš juostos ir pereina į būseną q k.

Grafiškai komanda pavaizduota kaip grafiko lankas, einantis nuo viršūnės q i iki viršūnės q k ir pažymėtas įvesties abėcėlės simboliu a j:

Grafinis viso atvaizdavimo δ vaizdas vadinamas baigtinės būsenos mašinos būsenos diagrama.

Jei erdvėlaivis atsiduria situacijoje (q i, a j), kuri nėra kairioji jokios komandos pusė, tada jis sustoja. Jei valdymo blokas suskaičiuoja visus juostoje įrašytus grandinės α simbolius ir tuo pačiu pereina į galutinę būseną q r Є F, tada jie sako, kad grandinę α leidžia baigtinės būsenos mašina.

Erdvėlaivio perėjimo lentelė sudaryta taip: matricos stulpeliai atitinka simbolius iš įvesties abėcėlės, eilutės atitinka simbolius iš būsenos abėcėlės, o matricos elementai atitinka būsenas, į kurias erdvėlaivis pereina tam tikram įvesties simbolio deriniui. ir valstybės simbolis.

Tegul taisyklinga gramatika G = , kurios taisyklės turi tokią formą: A i::= a j A k arba A i::= a j, kur A i, A k Є N ir a j Є T.

Tada baigtinis automatas A = , leidžianti tą pačią kalbą, kurią generuoja įprastinė gramatika G, yra sudaryta taip:

2) Q = N U (Z), Z N ir Z T, Z yra galutinė erdvėlaivio būsena;

5) Atvaizdavimas δ sudaromas tokia forma:

· Kiekviena A i::= a j A k formos gramatikos G pakeitimo taisyklė susieta su komanda (A i, a j) → A k;

· Kiekviena A i::= a j formos pakeitimo taisyklė susieta su komanda (A i, a j) → Z;

2 pavyzdys. Sukurkite gramatikos CA pagal 1 pavyzdį. Turime A = , Kur

1) V = T = (b, c)

2) Q = N U (Z) = (I, R, Z)

3) q 0 = (S) = (I)

5) δ: a) komandų rinkinio pavidalu:

b) būsenos diagramos pavidalu

Yra deterministinės ir nedeterministinės baigtinių būsenų mašinos. Erdvėlaivis vadinamas nedeterministinis KA (NKA), jei jos būsenos diagramoje iš vienos viršūnės kyla keli lankai su vienodais ženklais. Pavyzdžiui, KA iš 2 pavyzdžio yra NKA.

Praktiniais tikslais būtina, kad galutinis atpažinėjas pats nustatytų įvesties simbolių sekos pabaigos momentą ir pateiktų pranešimą apie įvesties sekos teisingumą ar klaidą. Šiuo tikslu įvesties grandinė laikoma apribota dešinėje galo žymekliu ├, o interpretuojamos būsenos įvedamos į erdvėlaivio būsenos diagramą:

Z – „leisti įvesties grandinę“;

O – „įvesties grandinėje buvo prisiminta klaida“;

E – „atmesti įvesties grandinę“.

Būsenos Z ir E yra galutinės, o erdvėlaivis patenka į jas atitinkamai nuskaitęs galutinį žymeklį ├, apdorojęs teisingą arba klaidingą įvesties grandinę. Būsena O yra tarpinė, erdvėlaivis persikelia į ją iš bet kurios galiojančios erdvėlaivio būsenos, kai aptinkama klaida įvesties grandinėje ir lieka ten, kol atkeliauja pabaigos žymeklis ├, po kurio pereina į būseną E – „atmesti įvesties grandinę. “