Rasmiy til sahifasining manbasini koʻrish

[[Fayl:Syntax_tree.svg|link=//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Syntax_tree.svg/250px-Syntax_tree.svg.png|thumb| Sintaktik jihatdan yaxshi shakllangan inglizcha jumlaning tuzilishi, ''„Rangsiz yashil gʻoyalar gʻazab bilan uxlaydi“'' ([[Noam Chomsky|Xomskiydan]] tarixiy misol,1957).]]
[[Mantiq]], [[matematika]], [[informatika]] va [[Tilshunoslik|tilshunoslikda]] '''rasmiy til''' harflari alifbodan olingan va maʼlum qoidalar toʻplamiga muvofiq yaxshi shakllangan soʻzlardan iborat.

Rasmiy tilning alifbosi til qatorlariga birikadigan [[harf]]lar yoki [[belgi]]lardan iborat<ref>See e.g. {{Kitob manbasi|title=Formal Languages and Compilation|series=Texts in Computer Science|first=Stefano Crespi|last=Reghizzi|publisher=Springer|year=2009|isbn=9781848820500|page=8|quote=An alphabet is a finite set|url=https://books.google.com/books?id=AxH6cWm61i0C&printsec=frontcover}}</ref>. Ushbu alifbo belgilaridan birlashtirilgan har bir qator soʻz deb ataladi va maʼlum bir rasmiy tilga tegishli soʻzlar baʼzan ''yaxshi shakllangan soʻzlar'' yoki ''yaxshi shakllangan formulalar'' deb ataladi. Rasmiy til koʻpincha uni shakllantirish qoidalaridan tashkil topgan oddiy grammatika yoki kontekstsiz grammatika kabi rasmiy grammatika orqali aniqlanadi.

Informatika sohasida rasmiy tillar [[Dasturlash tili|dasturlash tillarining]] grammatikasini va tabiiy tillar kichik toʻplamlarining rasmiylashtirilgan versiyalarini aniqlash uchun asos sifatida ishlatiladi. Bunda til soʻzlari maʼlum maʼnolar yoki [[semantika]] bilan bogʻliq boʻlgan tushunchalarni ifodalaydi.

'''Rasmiy til nazariyasi''' sohasi, birinchi navbatda, bunday tillarning sof [[Sintaksis|sintaktik]] tomonlarini, yaʼni ularning ichki strukturaviy qonuniyatlarini oʻrganadi. Rasmiy til nazariyasi tabiiy tillarning sintaktik qonuniyatlarini tushunish usuli sifatida tilshunoslikdan paydo boʻldi.

== Tarixi ==
XVII asrda [[Gottfried Leibniz|Gotfrid Leybnits]] piktogrammalardan foydalanadigan universal va rasmiy til boʻlgan universal tilni tasvirlab berdi. Bu davrda Gauss Gauss kodlari muammosini ham tadqiq qildi<ref>{{Veb manbasi|url=https://www.researchgate.net/publication/220530857_In_the_prehistory_of_formal_language_theory_Gauss_Languages|sarlavha=In the prehistory of formal language theory: Gauss Languages|sana=January 1992|kirish sanasi=30 April 2021}}</ref>.

Gottlob Frege attempted to realize Leibniz’s ideas, through a notational system first outlined in ''Begriffsschrift'' (1879) and more fully developed in his 2-volume Grundgesetze der Arithmetik (1893/1903).<ref>{{Veb manbasi|url=https://plato.stanford.edu/entries/frege/|sarlavha=Gottlob Frege|sana=5 December 2019|kirish sanasi=30 April 2021}}</ref> This described a „formal language of pure language.“<ref name="Herken1279">{{Kitob manbasi|editor=Rolf Herken|title=The universal Turing machine: a half-century survey|chapterurl=https://books.google.com/books?id=YafIDVd1Z68C&pg=PA290|year=1995|publisher=Springer|isbn=978-3-211-82637-9|page=290|chapter=Influences of Mathematical Logic on Computer Science|last=Martin Davis}}</ref>

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<ref>{{Veb manbasi|url=https://core.ac.uk/download/pdf/297029993.pdf|sarlavha=Thue’s 1914 paper: a translation|sana=28 August 2013|kirish sanasi=30 April 2021}}</ref>. Keyinchalik Post ushbu maqoladan rasmiy tillarni yaratish uchun kanonik tizimni ishlab chiqdi.

[[Noam Chomsky|Noam Xomskiy]] Xomskiy iyerarxiyasi deb nomlanuvchi rasmiy va tabiiy tillarning mavhum tasvirini ishlab chiqdi<ref>{{Cite journal|last=Jager|first1=Gerhard|last2=Rogers|first2=James|date=19 July 2012|title=Formal language theory: refining the Chomsky hierarchy|journal=Philosophical Transactions of the Royal Society B|volume=367|issue=1598|doi=10.1098/rstb.2012.0077}}</ref>. 1959-yilda Jon Backus [[Fortran|FORTRANni]] yaratganidan soʻng yuqori darajadagi dasturlash tilining sintaksisini tavsiflash uchun Backus-Naur shaklini ishlab chiqdi<ref>{{Veb manbasi|url=https://mathshistory.st-andrews.ac.uk/Biographies/Backus/|sarlavha=John Warner Backus|sana=February 2016|kirish sanasi=30 April 2021}}</ref>. Piter Naur 1960-yilda xuddi shunday sxemani ixtiro qilgan.

== Alifbodagi soʻzlar ==
Rasmiy tillar kontekstida '''alifbo''' har qanday toʻplam boʻlishi mumkin, garchi koʻpincha soʻzning odatiy maʼnosida [[Alifbo|alifboni]] yoki umuman olganda, [[ASCII]] yoki Unicode kabi har qanday chekli belgilarni kodlashdan foydalanish mantiqiy boʻladi. Alfavit elementlariga uning '''harflari''' deyiladi. 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.

Alifbodagi '''soʻz''' har qanday chekli harflar ketma-ketligi (yaʼni, qator) boʻlishi mumkin. S alifbosidagi barcha soʻzlar toʻplami odatda S <sup>*</sup> 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 u ''boʻsh soʻz deb ataladi.'' B''oʻsh soʻz'' koʻ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, ayniqsa [[Mantiq|mantiqda]], alifbo ''lugʻat'' va ''formulalar'' yoki ''jumlalar'' sifatida ham tanilgan. .

== Taʼrifi ==
S alifbosidagi '''rasmiy til''' ''L'' — bu S <sup>*</sup> 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 .[[Fayl:Formal_languages.svg|link=//upload.wikimedia.org/wikipedia/commons/thumb/d/da/Formal_languages.svg/220px-Formal_languages.svg.png|right|thumb| Ushbu diagrammada rasmiy tizim ichidagi sintaktik boʻlinishlar koʻrsatilgan. Belgilar qatorlarini yaxshi shakllangan formulalarga boʻlish mumkin. Yaxshi shakllangan formulalar toʻplami [[teorema]] va 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 til [[Natural son|natural sonlar]], yaxshi shakllangan qoʻshimchalar va yaxshi shakllangan qoʻshilish tengliklarini ifodalaydi, lekin ular nimani anglatishini ([[Semantika|semantikasi]]) emas, balki faqat qanday koʻrinishini (ularning [[Sintaksis|sintaksisi]]) 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&nbsp;=&nbsp;{a, b, ab, cba}. Ushbu konstruktsiyaning degenerativ holati '''boʻsh til''' boʻlib, unda umuman soʻz yoʻq (<span class="nounderlines">L&nbsp;=&nbsp;∅</span>).

Biroq, hatto S kabi cheklangan (boʻsh boʻlmagan) alifboda ham&nbsp;=&nbsp;{a,&nbsp;b} potentsial sifatida ifodalanishi mumkin boʻlgan cheksiz sonli soʻzlar mavjud: „a“, „abb“, „ababba“, „aaababbbbaab“,&nbsp;. . . . Shuning uchun rasmiy tillar odatda cheksizdir va cheksiz rasmiy tilni tavsiflash ''L'' yozish kabi oddiy emas. L&nbsp;=&nbsp;{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ʻraydigan [[algoritm]]) HA javobini beradigan qatorlar.

Bunday rasmiyatchiliklar haqida soʻraladigan odatiy savollarga quyidagilar kiradi:

* Ularning ifoda kuchi nimada? (''X'' formalizm ''Y'' tasvirlashi mumkin boʻlgan har bir tilni tasvirlay oladimi? U boshqa tillarni tasvirlay oladimi?)
* Ularning tan olinishi nimada? (Maʼlum bir soʻz ''X'' formalizm bilan tavsiflangan tilga tegishli yoki yoʻqligini aniqlash qanchalik qiyin?)
* Ularning solishtirish qobiliyati qanday? (Biri ''X'' formalizmda, ikkinchisi ''Y'' formatida yoki yana ''Xda'' tasvirlangan 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.


== Manbalar ==
{{manbalar}}
[[Turkum:Tillar]]