Və avtomatlar nəZƏRİYYƏSİ (Məşğələ dərsləri üşün vəsait)

IV. KS-qrammatikanın qurulması

Məsələ1. G = (V_T, V_N, Р, S) qrammatikası verilmişdir,haradaki, V_T = {a, d, е}, V_N= {В, С, S}, Р = {S → аВ, В → Cd | dC, С → е}.Verilmiş qramatikadan əmələ gələn terminal zəncirləri qurmalı və çıxışın uzunluğunu təyin etməli.

Həlli Aşağıdakı terminal zəncirləri alacağıq:

S → аВ → aCd → aed,

S → аВ → adC → ade,

Çıxışın uzunluğu isə 3-ə bərabərdir.

Məsələ2. G = (V_T, V_N, Р, S) qrammatikası verilmişdir,haradaki

V_T = {a, b, c, d, е},

V_N = {A, В,С, D, E} ,

Р = {A → ed, В → Ab, С → Bc, С → dD, D → Ae, E → bc}.

eadabcb zəncirinin L(G) dilinə aid olduğunu təyin etməli.

Həlli Verilmiş cıxış qaydalarına uyğun olaraq , mümkün terminal zəncir quraq:

С → Bc → Abc → edbc,

С → dD → dAe → dede.

Alınmış zəncirlərdən ilkin terminal simvollardan belə nəticəyə gəlmək olar ki, eadabcb zənciri L(G) dilinə aid deyil.

Məsələ3. 0 və 1 ibarət zəncirin KS-qrammatikasını qurmalı(2-ci tip qrammatika).Simvolların sayı bərabər olmalıdır.

Həlli Qrammatikanı verən çoxluğu təyin etməli

VT = {0, 1}; VN = {S};

Р ={S → 0S1, S → 1S0, S → ε, S → S01, S → S10}.

Məsələ4. S → bSS | а qaydasından əmələ gələn dili təsvir etməli.

Həlli Verilmiş çıxış qaydalarından istifadə edərək bir neçə terminal zəncir quraq:

S → a;

S → bSS → baa;

S → bSS → bbSSS → bbaaa;

S → bSS → bbSSbSS → bbaabaa;

S → bSS → bbSSbSS → bbbSSbSSbbSSbSS → ...

Alınmış zəncirlərdən aşağıdakılar görünür:

a)zəncir həmişə b terminalından başlayır və a-da qurtarır.(aksiomdan başqa);

b) İstənilən zəncirdə a –da terminalların sayı b-dən 1 vahid çoxdur;
Buradan belə nəticəyə gəlmək olar ki,

L(G) = {α | α ∈ {a, b}*}, |a| = |b| + 1, zəncir b terminalında başlayır,a terminalında isə başa çatır.