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

5.5.Maqazin yaddaşlı avtomat

Maqazin yaddaçlı avtomatın (MY-avtomat) maqazin şəkildə təşkil edilmiş işçi lenti var. MY-avtomat yeddilik şəklində olur:

M = (К, Σ, Г, δ, p₀, F, B₀), haradaki

К – vəziyyətlərin sonlu çoxluğu;

Σ - əlifba;

Г – maqazin əlifbası;

δ – keçidlər funksiyası;

p₀ – ilkin vəziyyət;

F - son vəziyyətlər çoxluğu;

B₀ - Г çoxluğundan simvol-maqazinin sonunu bildirən marker.

Ümumi halda bu təyin determinə olmayan avtomata uyğun gəlir.MY-avtomat ixtiyari şəkildə olan KS-qrammatikanın təhlil vasitəsi kimi daha maraqlıdır.Bu fakt aşağıdakı teoremdə öz əksini tapır.

Teorem. KS-qrammatika ilə gələn dillər MY-avtomat tərəfindən tanınan dillərlə üst-üstə düşür.

İsbatı. Təhlilin iki strategiyası var:yüksələn və azalan təhlil.Bu təhlillərin ikisinə də baxaq.

1. MY-avtomatın yüksələn təhlili

Yüksələn strategiya zamanı dilin əsasını taparaq onu verilmiş qrammatikanın qaydalarına uyğun olaraq reduksiya edilir.Bunu MY-avtomatın aşağıdakı fəaliyyət alqoritmini tərtib edərək həyata keçirmək olar:

1. 
   İstənilən giriş simvolu maqazinə yazılır;
   
2. 
   Əgər maqazinin yuxarı hissəsində əsas əmələ gəlibsə,hansı ki,qaydanın sağ hissəsi ilə üst-üstə düşür.Onda o,bu qaydanın sol tərəfindəki terminala yazılır.
   
3. 
   Əgər maqazində aksiom qalıbsa və giriş zənciri tamamilə baxılmışdır,onda təhlil başa çatır.
   

Bu alqoritmə uyğun olaraq , G=( V_T, V_N, P, S) KS-qrammatikanın MY-avtomatını quraq :

M = (К, V_T, Г, δ, p₀, F, B₀), haradaki Г = V_T ∪ V_N ∪ {B₀},

K = {p₀, F}, F = {f}.

δ keşidlər funksiyası aşağıdakı əmrlərdən ibarət olacaqdır:

а) p₀, a, ε → p₀, a – istənilən a ∈ V_T;

б) p₀, ε, ϕ’ → p₀, A – bütün qaydalar üçün A → ϕ ∈ P, где ϕ’ – ϕ-nin əks təsviridir;

в) p₀, ε, SB₀ → f, B₀.

Ümumi halda əmr aşağıdakı kimi olacaqdır:

p_i, σ, γ → p_j, λ , haradaki, p_i ∈ K – əmrin yerinə yetirilməsinə qədər avtomatın vəziyyəti,

σ∈V_t –giriş lentindəki simvol, γ∈Γ – maqazinin yuxarısındakı simvol ,

p_j ∈ K – əmrin yerinə yetirilməsindən sonra avtomatın vəziyyəti, λ∈Γ – maqazinə yazılan simvol.

Beləliklə, G qrammatikasında istənilən nəticə birmənalı olaraq ,MY-avtomatı tərəfindən qurulan əmrlər ardıcıllığına uyğun gəlir.

Misal.G qrammatikası verilmişdir:
S → S+A | S/A | A

A → a | (S);

V_N={S, A}, V_T={a, (, ), +, /}.

Verilmiş KS-qrammatika üçün MY-avtomatını quraq. Ekvivalent MY-avtomat aşağıdakı əmrlərdən ibarət olmalıdır.

1.Terminal simvolların maqazinə keçid əmrləri

p₀, a, ε → p₀, a ;

p₀, +, ε → p₀, + ;

p₀, /, ε → p₀, / ;

p₀, (, ε → p₀, ( ;

p₀, ), ε → p₀, ).

Bu əmrlər vasitəsilə terminal simvollar giriş lentindən maqazinə yazılır.

2.Qrammatika qaydalarına uyğun reduksiya əmrləri

p₀, ε, A+S → p₀, S ;

p₀, ε, A/S → p₀, S ;

p₀, ε, A → p₀, S ;

p₀, ε, )S( → p₀, A ;

p₀, ε, a → p₀, A.

Bu əmrlər qaydaların əks təsvirini əvəz edir.hansılar ki,qrammatikanın sol hissəsində maqazinin başında alınır.

3.Təhlilin sonunu bildirən yoxlama əmri

p₀, ε, SB₀ → f, B₀.

Təhlil o zaman başa çatır ki,əgər maqazində aksiom və maqazinin sonunu bildirən marker qalıb və giriş zənciri tamamilə baxılmışdır.