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

Qrammatikanın qraf şəklində təsviri
G qrammatikanın qraf şəklində aşağıdakı kimi olacaqdır.

G = (V_T,V_N, Р, S), haradaki,

V_T ={a, b, с}, V_N = {S}, P={S → aSa | bSb | c}.

4.3. KS qrammatikanın çevrilməsi

1. 
   А → В şəkilli qaydanın silinməsi
   

Birinci tip çevrilmə А → В qaydasınnın silinməsindən ibarətdir,ya da “terminal olmayan→ terminal olmayan”.

İstənilən KS-qrammatika ekvivalent qrammatika qurmaq olar,hansında ki,

А → В qaydası yoxdur,haradaki,A və B terminal olmayan simvollardır.

Tutaq ki, G=( V_T, V_N, P, S) KS- qrammatikası verilmişdir,haradaki,

V_N= {A1,A2, . . , An}

P-ni iki bir-biri ilə kəsişməyən çoxluğa bölək. P = P₁ P₂.

P₁-də А_i → A_k şəkilli bütün qaydalar,

P₂- də P\P₁ yəni digər qalan qaydalar.Hər bir A üçün P(A) qaydalar çoxluğunu təyin edək və oraya aşağıdakı qaydaları daxil edək

А_i→ϕ, А_i →* A_j və А_j → ϕ, haradaki А_j → ϕ ∈ P2.

G=( V_T, V_N, P, S) ekvivalent KS- qrammatikasını quraq.Haradaki,P_e qaydalar çoxluğu P₂ və P(A_i) qaydalar çoxluğundan ibarətdir.(bütün 1≤ i ≤n).

P_e =