Formal diLLƏr və avtomatlar nəZƏRİYYƏSİ

IV.FORMAL QRAMMATİKALAR VƏ DİLLƏR.

4.1.Törəmə qrammatikanın əsas anlayışları
Əlifba – boş olmayan sonlu çoxluqdur.Əlifbanın elementləri simvol adlanır.Σ={a_1,a₂,..., a_n} əlifbası üzərindəki zəncir a_i elementlərinin sonlu ardıcıllığıdır. Σ əlifbası üzərindəki bütün zəncirlər Σ^* ilə işarələnir.X zəncirinin uzunluğu onun elementlərinin sayına bərabərdir və │x│ ilə işarələnir.

Zəncirin uzunluğu sıfıra bərabər olarsa, o boş adlanır və ε ilə işarələnir.Uyğun olaraq da boş olmayan zəncir də boş olmayan uzunluqli zəncirlə təyin olunur.Tutaq ki, Σ={a,b} əlifbası verilmişdir.Onda bütün zəncirlər çoxluğu aşağıdakı kimi təyin olunur:

Σ^*={ ε,a,b,aa,ab,ba,bb,aaa,aab,aba,...}

x və y zəncirləri o vaxt bərabər olur ki,əgər onların uzunluğu eyni olsun və ibarət olduqları simvolların düzülüş qaydaları da dəqiqliklə üst-üstə düşsün.

x və y zəncirləri üzərindəki birləşmə (konkatenasiya) əməliyyatı aşağıdakı kimi yerinə yetirilir:

Σ əlifbası üzərindəki L dili Σ üzərindəli zəncirlər çoxluğundan ibarətdir.Boş dil olan L=0 ilə boş zəncirdən ibarət olan L= { ε } ≠0 dilini seşmək lazımdır. Σ əlifbasından ibarət L formal dili bir neçə formal qaydalardan ibarət sonlu çoxluqlardan ibarət dildir.

Tutaq ki,M və L -əlifbalar üzərində olan dillərdir.Onda onların konkatenasiyası LM = {xy|x∈L, y∈M} olur.Haradaki, {ε}L = L{ε}=L.

L çoxluğunun L^* və L⁺ iterasiyasının törəmə anlayışından istifadə edərək təyin edək.

L⁺= Lⁱ

L*= Lⁱ

Haradaki, i- dilin dərəcəsidir,Lrekursiv olaraq aşağıdakı kimi təyin olunur:

L⁰ = {ε};