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

L¹ = L;

Lⁿ⁺¹=LⁿL=LLⁿ

{ε}L=L{ε}=L.
Məsələn,L={a} dili verilmişdir.Onda

L^*={ε,a,aa,aaa,...}, L⁺=^*={a,aa,aaa,...}.

Əmələ gələn törəmə qrammatika

G=( V_T, V_N, P, S) dördlüyüdür,

Haradaki,

V_T - terminal simvollar çoxluğunu təyin edən sonlu avtomat

V_N – terminal olmayan simvollar çoxluğunu təyin edən sonlu avtomat

P – çıxış qaydalarının sonlu çoxluğu,yəni,aşağıdakı şəkildə cütlüklər şoxluğu U→V ,haradaki, u, v ∈(V_T∪V_N)*;

S – ilkin simvol (qrammatikanın aksiomu) , S ∈V_N

Qrammatikadan əmələ gələn zəncir,dilin terminal simvollarından ibarətdir.

Terminal və terminal olmayan simvolları bir birindən seçmək üçün onlar aşağıdakı kimi işarələnir:

terminal simvollar-sətirlərlə,

terminal olmayan simvollar – latın əlifbasının hərfləri ilə.

G qrammatikasında x birbaşa y zəncirini əmələ gətirir,əgər x= αuβ, у = αvβ

və u→v ∈ Р,yəni, y birbaşa x-dən əmələ gəlir, х => у.

G=( VT, VN, P, S) qrammatikasından əmələ gələn dil,terminal zəncirlər çoxluğudur,haradaki

L(G) = {х | х ∈ V_T*; S => *х}, haradaki,=>*-çıxış.

Məsələ. G=( VT, VN, P, S) qrammatikası verilmişdir,haradaki,V_T = {а, b}, V_N = {S}, Р = {S →aSb, S → ab).

Bu qrammatikadan əmələ gələn dili təyin etməli.

Həlli .Rekursiyadan istifadə edərək,dilin bir neçə zəncirini yazaq:
S → ab;

S → aSb => aabb;

S → aSb =>aaSbb => aaabbb; . . .

Bu qrammatikadan əmələ gələn dili təyin edək

L(G) = {a_nb_n | n > 0}.