Rasmiy til

Sintaktik jihatdan yaxshi shakllangan inglizcha jumlaning tuzilishi,"Rangsiz yashil gʻoyalar gʻazab bilan uxlaydi"(Xomskiydantarixiy misol,1957).

Mantiq,matematika,informatikavatilshunoslikdarasmiy tilharflari alifbodan olingan va maʼlum qoidalar toʻplamiga muvofiq yaxshi shakllangan soʻzlardan iborat.

Rasmiy tilning alifbosi til qatorlariga birikadigan harflar yoki belgilardan iborat.Ushbu alifbo belgilaridan birlashtirilgan har bir qator soʻz deb ataladi va maʼlum bir rasmiy tilga tegishli soʻzlar baʼzanyaxshi shakllangan soʻzlaryokiyaxshi shakllangan formulalardeb ataladi. Rasmiy til koʻpincha uni shakllantirish qoidalaridan tashkil topgan oddiy grammatika yoki kontekstsiz grammatika kabi rasmiy grammatika orqali aniqlanadi.

Informatika sohasida rasmiy tillardasturlash tillarininggrammatikasini va tabiiy tillar kichik toʻplamlarining rasmiylashtirilgan versiyalarini aniqlash uchun asos sifatida ishlatiladi.Bunda til soʻzlari maʼlum maʼnolar yokisemantikabilan bogʻliq boʻlgan tushunchalarni ifodalaydi.

Rasmiy til nazariyasisohasi, birinchi navbatda, bunday tillarning sofsintaktiktomonlarini, yaʼni ularning ichki strukturaviy qonuniyatlarini o‘rganadi. Rasmiy til nazariyasi tabiiy tillarning sintaktik qonuniyatlarini tushunish usuli sifatida tilshunoslikdan paydo boʻldi.

Tarixi

XVII asrdaGotfrid Leybnitspiktogrammalardan foydalanadigan universal va rasmiy til boʻlgan universal tilni tasvirlab berdi. Bu davrda Gauss Gauss kodlari muammosini ham tadqiq qildi.

Gottlob Frege attempted to realize Leibniz’s ideas, through a notational system first outlined inBegriffsschrift(1879) and more fully developed in his 2-volume Grundgesetze der Arithmetik (1893/1903).This described a „formal language of pure language. “

XX asrning birinchi yarmida rasmiy tillar bilan bogʻliq bir qancha ishlanmalar amalga oshirildi. Axel Thue 1906-yildan 1914-yilgacha soʻzlar va tilga oid toʻrtta maqola chop etdi. Emil Post keyinchalik „Thue Systems “deb atagan narsani taqdim etdi.Keyinchalik Post ushbu maqoladan rasmiy tillarni yaratish uchun kanonik tizimni ishlab chiqdi.

Noam XomskiyXomskiy iyerarxiyasi deb nomlanuvchi rasmiy va tabiiy tillarning mavhum tasvirini ishlab chiqdi.1959-yilda Jon BackusFORTRANniyaratganidan soʻng yuqori darajadagi dasturlash tilining sintaksisini tavsiflash uchun Backus-Naur shaklini ishlab chiqdi.Piter Naur 1960-yilda xuddi shunday sxemani ixtiro qilgan.

Alifbodagi soʻzlar

Rasmiy tillar kontekstidaalifbohar qanday toʻplam boʻlishi mumkin, garchi koʻpincha soʻzning odatiy maʼnosidaalifboniyoki umuman olganda,ASCIIyoki Unicode kabi har qanday chekli belgilarni kodlashdan foydalanish mantiqiy boʻladi. Alfavit elementlariga uningharflarideyiladi. Alifbo cheksiz koʻp elementlardan iborat boʻlishi mumkin.Ammo rasmiy til nazariyasidagi koʻpgina taʼriflar cheklangan miqdordagi elementlarga ega alifbolarni belgilaydi va koʻpchilik natijalar faqat ularga tegishli boʻladi.

Alifbodagisoʻzhar qanday chekli harflar ketma-ketligi (yaʼni, qator) boʻlishi mumkin. S alifbosidagi barcha soʻzlar toʻplami odatda S^*bilan belgilanadi (Kleene yulduzi yordamida). Soʻzning uzunligi u tuzilgan harflar soni bilan tavsiflanadi. Har qanday alifbo uchun uzunligi 0 boʻlgan faqat bitta soʻz mavjudva uboʻsh soʻz deb ataladi.Boʻsh soʻzkoʻpincha, e, e, l yoki hatto l bilan belgilanadi. Ikki so‘zni birlashtirib, yangi so‘z hosil qilish mumkin, uning uzunligi asl so‘zlarning uzunliklari yig‘indisiga teng. So‘zning bo‘sh so‘z bilan bog‘lanishi natijasida asli so‘z hosil bo‘ladi.

Baʼzi ilovalarda, ayniqsamantiqda,alifbolugʻatvaformulalaryokijumlalarsifatida ham tanilgan..

Taʼrifi

S alifbosidagirasmiy tilL— bu S^*ning kichik toʻplami, yaʼni shu alifbo ustidagi soʻzlar toʻplami. Baʼzan soʻzlar toʻplami iboralarga guruhlanadi. „Yaxshi shakllangan iboralar “yaratish uchun qoidalar va cheklovlar ishlab chiqilishi mumkin.

„Rasmiy til “tushunchasining haqiqiy taʼrifi: berilgan alifbodan tuzilgan chekli uzunlikdagi satrlarning (ehtimol cheksiz) toʻplami.

Misollar

L alifbosida S={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

• Tarkibida „+ “yoki „=" boʻlmagan va "0 “bilan boshlanmagan har bir boʻsh qator mavjud L.

  

  Ushbu diagrammada rasmiy tizim ichidagi sintaktik boʻlinishlar koʻrsatilgan. Belgilar qatorlarini yaxshi shakllangan formulalarga boʻlish mumkin. Yaxshi shakllangan formulalar toʻplamiteoremava teorema boʻlmaganlarga boʻlinadi.

• „0 “qatori mavjud L.
• „= "dan iborat qator mavjud L faqat bitta" = “boʻlsa va u ikkita haqiqiy satrni ajratsa L.
• Tarkibida „+ “boʻlgan, lekin „= “boʻlmagan qator mavjud L, agar satrdagi har bir „+ “ikkita haqiqiy qatorni ajratsa L.

Ushbu qoidalarga koʻra, „23+4=555 “qatori mavjud L, lekin „=234=+ “qatori emas. Bu rasmiy tilnatural sonlar,yaxshi shakllangan qoʻshimchalar va yaxshi shakllangan qoʻshilish tengliklarini ifodalaydi, lekin ular nimani anglatishini (semantikasi) emas, balki faqat qanday koʻrinishini (ularningsintaksisi) ifodalaydi. Masalan, ushbu qoidalarning hech bir joyida „0 “nol sonini, „+ “qo‘shishni, „23+4=555 “noto‘g‘ri ekanligini va hokazo degan ko‘rsatma yo‘q.

Qurilishlar

Cheklangan tillar uchun barcha yaxshi tuzilgan soʻzlarni aniq sanab oʻtish mumkin. Masalan, biz tilni tasvirlashimiz mumkin L, xuddi L = {a, b, ab, cba}. Ushbu konstruktsiyaning degenerativ holatiboʻsh tilboʻlib, unda umuman soʻz yoʻq (L = ∅).

Biroq, hatto S kabi cheklangan (boʻsh boʻlmagan) alifboda ham = {a, b} potentsial sifatida ifodalanishi mumkin boʻlgan cheksiz sonli soʻzlar mavjud: „a “, „abb “, „ababba “, „aaababbbbaab “,.... Shuning uchun rasmiy tillar odatda cheksizdir va cheksiz rasmiy tilni tavsiflashLyozish kabi oddiy emas.L = {a, b, ab, cba}.

Tilning spetsifikatsiyasi rasmiyatchiliklari

Rasmiy tillar bir nechta fanlarda vosita sifatida ishlatiladi. Biroq, rasmiy til nazariyasi kamdan-kam hollarda alohida tillar bilan bogʻliq, lekin asosan tillarni tavsiflash uchun turli xil rasmiyatchiliklarni oʻrganish bilan bogʻliq. Masalan, til sifatida berilishi mumkin

• baʼzi bir rasmiy grammatika tomonidan yaratilgan satrlar;
• maʼlum bir muntazam ifoda bilan tasvirlangan yoki mos keladigan satrlar;
• Tyuring mashinasi yoki chekli holat avtomati kabi baʼzi avtomatlar tomonidan qabul qilingan satrlar;
• baʼzi qaror qabul qilish protseduralari (bogʻliq HA/YOʻQ savollari ketma-ketligini soʻraydiganalgoritm) HA javobini beradigan qatorlar.

Bunday rasmiyatchiliklar haqida soʻraladigan odatiy savollarga quyidagilar kiradi:

• Ularning ifoda kuchi nimada? (XformalizmYtasvirlashi mumkin boʻlgan har bir tilni tasvirlay oladimi? U boshqa tillarni tasvirlay oladimi?)
• Ularning tan olinishi nimada? (Maʼlum bir soʻzXformalizm bilan tavsiflangan tilga tegishli yoki yoʻqligini aniqlash qanchalik qiyin?)
• Ularning solishtirish qobiliyati qanday? (BiriXformalizmda, ikkinchisiYformatida yoki yanaXdatasvirlangan ikkita til aslida bir xil til ekanligini aniqlash qanchalik qiyin?).

Ajablanarlisi shundaki, koʻpincha bu qaror muammolariga javob „buni umuman qilish mumkin emas “yoki „bu juda qimmat “. Shuning uchun, rasmiy til nazariyasi hisoblash nazariyasi va murakkablik nazariyasining asosiy qoʻllanishi sohasidir. Rasmiy tillar Xomskiy iyerarxiyasida generativ grammatikasining ifoda kuchiga, shuningdek, tanib olish avtomatining murakkabligiga qarab tasniflanishi mumkin. Kontekstsiz grammatika va oddiy grammatika ekspressivlik va tahlil qilish qulayligi oʻrtasida yaxshi kelishuvni taʼminlaydi va amaliy dasturlarda keng qoʻllanadi.