Prefiks grammatikasi - Prefix grammar

Yilda nazariy informatika va rasmiy til nazariyasi, a prefiks grammatikasi ning bir turi mag'lubiyatni qayta yozish tizimi to'plamidan iborat mag'lubiyat qayta yozish qoidalar va shunga o'xshash rasmiy grammatika yoki a yarim Thue tizimi. Prefiks grammatikalari uchun o'ziga xos narsa bu ularning qoidalari shakli emas, balki ularni qo'llash usuli: faqat prefikslar qayta yozilgan. Prefiks grammatikalari to'liq barchasini tasvirlaydi oddiy tillar.^[1]

Rasmiy ta'rif

Prefiks grammatikasi G a 3-karra, (Σ, S, P), qaerda

Σ cheklangan alifbo
S $ Delta $ ustidagi asosiy satrlarning cheklangan to'plami
P shaklning ishlab chiqarish qoidalarining cheklangan to'plamidir siz → v qayerda siz va v Σ satrlari

Iplar uchun x, y, biz yozamiz x →_G y (va ayting: G kelib chiqishi mumkin y dan x agar bir qadamda) agar satrlar bo'lsa u, v, w shu kabi ${ displaystyle x = vu, y = wu}$ va v → w ichida P. Yozib oling $\to G$ a ikkilik munosabat Σ satrlarida.

The til ning G, belgilangan ${ displaystyle L (G)}$ , dan olinadigan qatorlar to'plami S nol va undan ko'p bosqichlarda: rasmiy ravishda, satrlar to'plami w shunday kimdir uchun s yilda S, s R w, qayerda R bo'ladi o'tish davri yopilishi ning $\to G$ .

Misol

Prefiks grammatikasi

B = {0, 1}
S = {01, 10}
P = {0 → 010, 10 → 100}

tomonidan belgilangan tilni tavsiflaydi doimiy ifoda

{ displaystyle 01 (01) ^ {*} chashka 100 ^ {*}}

Shuningdek qarang

Muntazam grammatika

Adabiyotlar

^ M. Frazier va C. D. Sahifa. Prefiks grammatikalari: oddiy tillarning muqobil tavsifi. Axborotni qayta ishlash xatlari, 51 (2): 67-71, 1994 y.

[1] M. Frazier va C. D. Sahifa. Prefiks grammatikalari: oddiy tillarning muqobil tavsifi. Axborotni qayta ishlash xatlari, 51 (2): 67-71, 1994 y.

[1]