"Grammatika" ning ta'rifi

1.2 "Grammatika" ning ta'rifi
“Grammatika” ni ta’riflash uchun quyidagi tushunchalarni keltrib o’rishimiz zarur:
Lug'at, terminali bo'lmagan lug'at, keltirib chiqarish qoidalari va boshlang’ich belgilar
Terminal lug'atni belgi bilan bilan belgilab olamiz. - bu tilning gaplari tuzilishi mumkin bo'lgan terminal elementlar to'plamidir. elementlari lotin alifbosining dastlabki kichik harflari bilan belgilanadi. Agar terminal so'z ga tegishli bo'lsa, biz yoki kabi yozamiz. Endi ikkinchi belgilashni kiritamiz. Bu Terminal bo'lmagan elementlar to’plam bo’lib, ular faqat gaplarni hosil qilishda ishlatiladi. Terminal bo'lmagan elementlar to’plamini kabi belgilaymiz. elementlari Lotin alifbosi katta harflari bilan belgilanadi va o’zgaruvchilar yoki kategoriya belgilari deyiladi.
Ma’lumki,
va lar grammatikaning V lug’atini tashkil qiladi. Shuning uchun:
ko’rinishda yozish mumkin.
V ning elelementlaridan tashkil topgan belgilar ketma ketligi(satr) , ularning o'zgaruvchi ekanligi yoki terminal elementligidan qat'iy nazar, Yunon alifbosining kichik harfi bilan belgilanadi. Bunda satr 0, 1 yoki undan ortiq element bo'lishi mumkin; 0 ta elementdan iborat satr nol satr deb ataladi va λ kabi belgilanadi. Faqatgina terminal elementlardan tashkil topgan satrlotin alifbosining oxirigi kichik harf bilan belgilanishi mumkin.
belgisi bilan terminal lug’tdan tuzish mumkin bo’lgan barcha chekli satrlar to’plamini belgilaymiz.
Masalan: agar ikkita elementdan iborat bo'lsa, ya'ni
U holda, Agar dan bo'sh satrini chiqarib tashlamoqchi bo'lsak: to’plam musbat uzunlikdagi barcha satrlar to'plami bo’ladi. Ma’lumki, bo’sh bo’lmagan to’plam bo’lib, va to’plamlar cheksiz to’plamlardir. α satrning uzunligi bilan belgilanadi;
Shunday qilib, =1, , =3, | λ | = 0.
Grammatikaning keltirib chiqarish qoidalari (yoki oddigina keltirib chiqarish qoidalari) belgilar juftligidan iborat bo’ladi: . Bunda
Buning ma'nosi belgi (musbat uzunlikka ega itiyoriy belilar ketma-ketligi bo’lib, nol uzunlikka ega bo’la olmaydi) o’rniga, belgi (musbat uzunlikka ega itiyoriy belilar ketma-ketligi bo’lishi,shuningdek, λ bo’lishi mumkin ham mumkin) qayta yozish degani. Bu qoidalarni ixtiyoriy kontekstga qo’llaniladi. Masalan: yozuvning qismi bo’lsin. U holda bu yozuv yozuvga o’tadi.
Agar satr bitta belgisi keltirib chiqarish qoidalariga asosan boshqa bir belgiga almashtirishdan yangi satrga o’tsa,ushbu ⇒ belgini ishlatamiz.
Yuqoridagi misol uchun ⇒ . Buning ma’nosi oxirgi satr oldingisining hosilasi(oldingisidan kelib chiqadi) deganidir. Agar keltirib qoidasida bir necha o’rniga qo’yish
ni kabi yozishimiz mumkin.
Gramatikaning keltirib chiqarish qoidalarini P ni dekart ko’paytma shaklida ham yozish mumkin. Ya’ni,
Grammatikaning boshlang'ich belgisi S bilan belgilanadi. S ning ma'lum bir elementi.
Shunday qilib grammatikani quyidagicha ta'riflashimiz mumkin:
Grammatika G=( , , , )-terminal lug'at- , terminali bo'lmagan lug'at- , keltirib chiqarish qoidalari- va boshlang’ich belgilar to’plami- lardan tashkil topgan to’plam bo’lib, quyidagi xususiyatlarga ega:

1. 
   , , lar bo’sh bo’lmagan chekli to’plamlardir
   
2. 
   
   
3. 
   
   
4. 
   S