Rasmiy til: Versiyalar orasidagi farq
Redirecting to Davlat tili |
„Formal language“ sahifasi tarjima qilib yaratildi Teglar: Removed redirect [tarjimon] [tarjimon 2] |
||
| Qator 1: | Qator 1: | ||
#REDIRECT [[Davlat tili]] |
|||
[[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 harflar yoki belgilardan 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 . |
|||
* "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 = {a, b, ab, cba}. Ushbu konstruktsiyaning degenerativ holati '''bo'sh til''' bo'lib, unda umuman so'z yo'q ( <span class="nounderlines">L = ∅</span> ). |
|||
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 tavsiflash ''L'' yozish 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'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'llanilishi 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'llaniladi. |
|||
[[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.]] |
|||
== Manbalar == |
|||
[[Turkum:Pages with unreviewed translations]] |
|||
23-Sentyabr 2022, 08:49 dagi koʻrinishi
Mantiq, matematika, informatika va tilshunoslikda rasmiy til harflari alifbodan olingan va maʼlum qoidalar toʻplamiga muvofiq yaxshi shakllangan soʻzlardan iborat.
Rasmiy tilning alifbosi til qatorlariga birikadigan harflar yoki belgilardan iborat[1]. 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 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 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 Gotfrid Leybnits piktogrammalardan foydalanadigan universal va rasmiy til bo'lgan universal tilni tasvirlab berdi. Bu davrda Gauss Gauss kodlari muammosini ham tadqiq qildi[2].
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).[3] This described a "formal language of pure language."[4]
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[5]. Keyinchalik Post ushbu maqoladan rasmiy tillarni yaratish uchun kanonik tizimni ishlab chiqdi.
Noam Xomskiy Xomskiy iyerarxiyasi deb nomlanuvchi rasmiy va tabiiy tillarning mavhum tasvirini ishlab chiqdi[6]. 1959-yilda Jon Backus FORTRANni yaratganidan so'ng yuqori darajadagi dasturlash tilining sintaksisini tavsiflash uchun Backus-Naur shaklini ishlab chiqdi[7]. 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 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 * 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. Bo'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 mantiqda, alifbo lug'at va formulalar yoki jumlalar sifatida ham tanilgan. .
Ta'rifi
S alifbosidagi rasmiy til L - 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 .
- "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 sonlar, yaxshi shakllangan qoʻshimchalar va yaxshi shakllangan qoʻshilish tengliklarini ifodalaydi, lekin ular nimani anglatishini (semantikasi) emas, balki faqat qanday koʻrinishini (ularning 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 = {a, b, ab, cba}. Ushbu konstruktsiyaning degenerativ holati bo'sh til bo'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 tavsiflash L yozish 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'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'llanilishi 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'llaniladi.
Manbalar
- ↑ See e.g. Reghizzi, Stefano Crespi. Formal Languages and Compilation, Texts in Computer Science. Springer, 2009 — 8 bet. ISBN 9781848820500. „An alphabet is a finite set“
- ↑ „In the prehistory of formal language theory: Gauss Languages“ (1992-yil yanvar). Qaraldi: 2021-yil 30-aprel.
- ↑ „Gottlob Frege“ (2019-yil 5-dekabr). Qaraldi: 2021-yil 30-aprel.
- ↑ Martin Davis „Influences of Mathematical Logic on Computer Science“,. The universal Turing machine: a half-century survey Rolf Herken: . Springer, 1995 — 290 bet. ISBN 978-3-211-82637-9.
- ↑ „Thue’s 1914 paper: a translation“ (2013-yil 28-avgust). Qaraldi: 2021-yil 30-aprel.
- ↑ Jager, Gerhard; Rogers, James (19 July 2012). "Formal language theory: refining the Chomsky hierarchy". Philosophical Transactions of the Royal Society B 367 (1598). doi:10.1098/rstb.2012.0077.
- ↑ „John Warner Backus“ (2016-yil fevral). Qaraldi: 2021-yil 30-aprel.