चॉम्स्की पदानुक्रम: Difference between revisions

Revision as of 21:39, 25 July 2023

चॉम्स्की पदानुक्रम द्वारा वर्णित समावेशन सेट करें

चॉम्स्की पदानुक्रम (अक्सर इसे चॉम्स्की-शूट्ज़ेनबर्गर पदानुक्रम के रूप में जाना जाता है)^[1]) औपचारिक भाषा, कंप्यूटर विज्ञान और भाषाविज्ञान के क्षेत्र में, औपचारिक व्याकरण की कक्षाओं का पदानुक्रम#कंटेनमेंट पदानुक्रम है। औपचारिक व्याकरण यह वर्णन करता है कि किसी भाषा की शब्दावली (या वर्णमाला) से स्ट्रिंग कैसे बनाई जाए जो भाषा के वाक्यविन्यास के अनुसार मान्य हों। भाषाविद् नोम चौमस्की ने सिद्धांत दिया कि औपचारिक व्याकरण के चार अलग-अलग वर्ग मौजूद हैं जो तेजी से जटिल भाषाएँ उत्पन्न कर सकते हैं। प्रत्येक वर्ग पूरी तरह से सभी निम्न वर्गों की भाषा उत्पन्न कर सकता है।

इतिहास

व्याकरण के पदानुक्रम का सामान्य विचार सबसे पहले भाषाविद् नोम चॉम्स्की द्वारा वर्णित किया गया था Chomsky 1956. मार्सेल-पॉल शुट्ज़ेनबर्गर ने औपचारिक भाषाओं के सिद्धांत के विकास में भी भूमिका निभाई; कागज़ Chomsky & Schützenberger 1963 संदर्भ-मुक्त व्याकरण सहित आधुनिक पदानुक्रम का वर्णन करता है।^[1]

स्वतंत्र रूप से और भाषाविदों के साथ, गणितज्ञ गणना मॉडल (ऑटोमेटा) विकसित कर रहे थे। किसी भाषा में वाक्य को पार्स करना गणना के समान है, और चॉम्स्की द्वारा वर्णित व्याकरण विभिन्न मशीन मॉडलों की कम्प्यूटेशनल शक्ति के समान और समकक्ष साबित हुए हैं।^[2]

पदानुक्रम

निम्नलिखित तालिका चॉम्स्की के चार प्रकार के व्याकरणों में से प्रत्येक का सारांश प्रस्तुत करती है, भाषा का वह वर्ग जो इसे उत्पन्न करता है, ऑटोमेटन का प्रकार जो इसे पहचानता है, और इसके नियमों का स्वरूप कैसा होना चाहिए।

Grammar	Languages	Recognizing Automaton	Production rules (constraints)*	Examples^[3]^[4]
Type-0	Recursively enumerable	Turing machine	$\gamma \rightarrow \alpha$ ( $\gamma$ non-empty)	$L=\{w\|w$ describes a terminating Turing machine $\}$
Type-1	Context-sensitive	Linear-bounded non-deterministic Turing machine	$\alpha A\beta \rightarrow \alpha \gamma \beta$	$L=\{a^{n}b^{n}c^{n}\|n>0\}$
Type-2	Context-free	Non-deterministic pushdown automaton	$A\rightarrow \alpha$	$L=\{a^{n}b^{n}\|n>0\}$
Type-3	Regular	Finite state automaton	$A\rightarrow {\text{a}}$ and $A\rightarrow {\text{a}}B$	$L=\{a^{n}\|n\geq 0\}$
* Meaning of symbols: ${\text{a}}$ = terminal $A$ , $B$ = non-terminal $\alpha$ , $\beta$ , $\gamma$ = string of terminals and/or non-terminals

ध्यान दें कि पुनरावर्ती भाषाओं के अनुरूप व्याकरणों का सेट इस पदानुक्रम का सदस्य नहीं है; ये ठीक प्रकार से टाइप-0 और टाइप-1 के बीच होंगे।

प्रत्येक नियमित भाषा संदर्भ-मुक्त है, प्रत्येक संदर्भ-मुक्त भाषा संदर्भ-संवेदनशील है, प्रत्येक संदर्भ-संवेदनशील भाषा पुनरावर्ती है और प्रत्येक पुनरावर्ती भाषा पुनरावर्ती रूप से गणना योग्य है। ये सभी उचित समावेशन हैं, जिसका अर्थ है कि पुनरावर्ती रूप से गणना योग्य भाषाएं मौजूद हैं जो संदर्भ-संवेदनशील नहीं हैं, संदर्भ-संवेदनशील भाषाएं जो संदर्भ-मुक्त नहीं हैं और संदर्भ-मुक्त भाषाएं जो नियमित नहीं हैं।^[5]

प्रकार-0 व्याकरण

टाइप-0 व्याकरण में सभी औपचारिक व्याकरण शामिल होते हैं। वे बिल्कुल सभी भाषाएँ उत्पन्न करते हैं जिन्हें ट्यूरिंग मशीन द्वारा पहचाना जा सकता है। इन भाषाओं को पुनरावर्ती गणना योग्य भाषा या ट्यूरिंग-पहचानने योग्य भाषा के रूप में भी जाना जाता है।^[6] ध्यान दें कि यह पुनरावर्ती भाषाओं से भिन्न है, जिसे ऐसी मशीन द्वारा तय किया जा सकता है जो ट्यूरिंग मशीन को हमेशा रोकती है।

प्रकार-1 व्याकरण

टाइप-1 व्याकरण संदर्भ-संवेदनशील भाषाएँ उत्पन्न करते हैं। इन व्याकरणों में रूप के नियम होते हैं $\alpha A\beta \rightarrow \alpha \gamma \beta$ साथ $A$ नॉनटर्मिनल और $\alpha$ , $\beta$ और $\gamma$ टर्मिनलों और/या गैर-टर्मिनलों की तारें। तार $\alpha$ और $\beta$ खाली हो सकता है, लेकिन $\gamma$ गैररिक्त होना चाहिए. नियम $S\rightarrow \epsilon$ अनुमति है यदि $S$ किसी भी नियम के दाईं ओर प्रकट नहीं होता है. इन व्याकरणों द्वारा वर्णित भाषाएँ वास्तव में सभी भाषाएँ हैं जिन्हें रैखिक बाउंडेड ऑटोमेटन (एक गैर-नियतात्मक ट्यूरिंग मशीन जिसका टेप इनपुट की लंबाई के निरंतर समय से घिरा होता है) द्वारा पहचाना जा सकता है।

प्रकार-2 व्याकरण

टाइप-2 व्याकरण संदर्भ-मुक्त भाषाएँ उत्पन्न करते हैं। इन्हें प्रपत्र के नियमों द्वारा परिभाषित किया गया है $A\rightarrow \alpha$ साथ $A$ नॉनटर्मिनल होने के नाते और $\alpha$ टर्मिनलों और/या गैर-टर्मिनलों की श्रृंखला होना। ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिन्हें गैर-नियतात्मक पुशडाउन ऑटोमेटन द्वारा पहचाना जा सकता है। संदर्भ-मुक्त भाषाएं - या इसके नियतात्मक संदर्भ-मुक्त भाषा का सबसेट - अधिकांश प्रोग्रामिंग भाषाओं की वाक्यांश संरचना के लिए सैद्धांतिक आधार हैं, हालांकि उनके वाक्यविन्यास में घोषणाओं और स्कोप (कंप्यूटर) के कारण संदर्भ-संवेदनशील नाम रिज़ॉल्यूशन (प्रोग्रामिंग भाषाएं) भी शामिल हैं विज्ञान)। पार्सिंग को आसान बनाने के लिए अक्सर व्याकरणों के उपसमूह का उपयोग किया जाता है, जैसे कि एलएल पार्सर द्वारा।

प्रकार-3 व्याकरण

टाइप-3 व्याकरण नियमित भाषाएँ उत्पन्न करते हैं। ऐसा व्याकरण अपने नियमों को बाईं ओर एकल नॉनटर्मिनल तक सीमित करता है और दाईं ओर एकल टर्मिनल से युक्त होता है, जिसके बाद संभवतः एकल नॉनटर्मिनल (दाएं नियमित) होता है। वैकल्पिक रूप से, व्याकरण के दाईं ओर एकल टर्मिनल शामिल हो सकता है, संभवतः एकल नॉनटर्मिनल (बाएं नियमित) से पहले। ये समान भाषाएँ उत्पन्न करते हैं। हालाँकि, यदि बाएँ-नियमित नियमों और दाएँ-नियमित नियमों को मिला दिया जाए, तो भाषा को नियमित होने की आवश्यकता नहीं है। नियम $S\rightarrow \varepsilon$ यदि यहाँ भी अनुमति है $S$ किसी भी नियम के दाईं ओर प्रकट नहीं होता है. ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिनका निर्णय सीमित राज्य ऑटोमेटन द्वारा किया जा सकता है। इसके अतिरिक्त, औपचारिक भाषाओं के इस परिवार को नियमित अभिव्यक्ति द्वारा प्राप्त किया जा सकता है। नियमित भाषाओं का उपयोग आमतौर पर खोज पैटर्न और प्रोग्रामिंग भाषाओं की शाब्दिक संरचना को परिभाषित करने के लिए किया जाता है।

यह भी देखें

चॉम्स्की सामान्य रूप

संदर्भ

↑ ^1.0 ^1.1 Allott, Nicholas; Lohndal, Terje; Rey, Georges (27 April 2021). "संक्षिप्त परिचय" (PDF). A Companion to Chomsky: 1–17. doi:10.1002/9781119598732.ch1.
↑ Kozen, Dexter C. "Automata and Computability" Springer, 1997. Pages 3-4
↑ Geuvers, H.; Rot, J. (2016). "Applications, Chomsky hierarchy, and Recap" (PDF). Regular Languages. Archived (PDF) from the original on 2018-11-19.
↑ Sudkamp, Thomas A. "Languages and Machines: An Introduction to the Theory of Computer Science" Second Edition, Addison Wesley Longman, 1997 page 310
↑ Chomsky, Noam (1963). "Chapter 12: Formal Properties of Grammars". In Luce, R. Duncan; Bush, Robert R.; Galanter, Eugene (eds.). गणितीय मनोविज्ञान की पुस्तिका. Vol. II. John Wiley and Sons, Inc. pp. 323–418.
↑ Sipser, Michael (1997). संगणना के सिद्धांत का परिचय (1st ed.). Cengage Learning. p. 130. ISBN 0-534-94728-X. The Church-Turing Thesis

Chomsky, Noam (1956). "Three models for the description of language" (PDF). IRE Transactions on Information Theory. 2 (3): 113–124. doi:10.1109/TIT.1956.1056813. Archived (PDF) from the original on 2016-03-07.
Chomsky, Noam (1959). "On certain formal properties of grammars" (PDF). Information and Control. 2 (2): 137–167. doi:10.1016/S0019-9958(59)90362-6.
Chomsky, Noam; Schützenberger, Marcel P. (1963). "The algebraic theory of context free languages". In Braffort, P.; Hirschberg, D. (eds.). Computer Programming and Formal Systems (PDF). Amsterdam: North Holland. pp. 118–161. Archived (PDF) from the original on 2011-06-13.
Davis, Martin D.; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (2nd ed.). Boston: Academic Press, Harcourt, Brace. p. 327. ISBN 0-12-206382-1.

[Allott-1] 1.0 ^1.1 Allott, Nicholas; Lohndal, Terje; Rey, Georges (27 April 2021). "संक्षिप्त परिचय" (PDF). A Companion to Chomsky: 1–17. doi:10.1002/9781119598732.ch1.

[2] Kozen, Dexter C. "Automata and Computability" Springer, 1997. Pages 3-4

[3] Geuvers, H.; Rot, J. (2016). "Applications, Chomsky hierarchy, and Recap" (PDF). Regular Languages. Archived (PDF) from the original on 2018-11-19.

[4] Sudkamp, Thomas A. "Languages and Machines: An Introduction to the Theory of Computer Science" Second Edition, Addison Wesley Longman, 1997 page 310

[5] Chomsky, Noam (1963). "Chapter 12: Formal Properties of Grammars". In Luce, R. Duncan; Bush, Robert R.; Galanter, Eugene (eds.). गणितीय मनोविज्ञान की पुस्तिका. Vol. II. John Wiley and Sons, Inc. pp. 323–418.

[Sipser-1st-6] Sipser, Michael (1997). संगणना के सिद्धांत का परिचय (1st ed.). Cengage Learning. p. 130. ISBN 0-534-94728-X. The Church-Turing Thesis

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
 {{Short description|Hierarchy of classes of formal grammars}}
-[[Image:Chomsky-hierarchy.svg|thumb|right|200px|alt=The Chomsky hierarchy|चॉम्स्की पदानुक्रम द्वारा वर्णित समावेशन सेट करें]]चॉम्स्की पदानुक्रम (अक्सर इसे चॉम्स्की-शूट्ज़ेनबर्गर पदानुक्रम के रूप में जाना जाता है)<ref name=Allott>{{cite journal |last1=Allott |first1=Nicholas |last2=Lohndal |first2=Terje |last3=Rey |first3=Georges |title=संक्षिप्त परिचय|journal=A Companion to Chomsky |date=27 April 2021 |pages=1–17 |doi=10.1002/9781119598732.ch1 |url=https://www.researchgate.net/profile/Nicholas-Allott/publication/351812216_Synoptic_Introduction/links/641ff75c66f8522c38d42fd4/Synoptic-Introduction.pdf}}</ref>) [[औपचारिक भाषा]], [[कंप्यूटर विज्ञान]] और भाषाविज्ञान के क्षेत्र में, [[औपचारिक व्याकरण]] की कक्षाओं का एक पदानुक्रम#कंटेनमेंट पदानुक्रम है। एक औपचारिक व्याकरण यह वर्णन करता है कि किसी भाषा की शब्दावली (या वर्णमाला) से स्ट्रिंग कैसे बनाई जाए जो भाषा के वाक्यविन्यास के अनुसार मान्य हों। भाषाविद् [[नोम चौमस्की]] ने सिद्धांत दिया कि औपचारिक व्याकरण के चार अलग-अलग वर्ग मौजूद हैं जो तेजी से जटिल भाषाएँ उत्पन्न कर सकते हैं। प्रत्येक वर्ग पूरी तरह से सभी निम्न वर्गों की भाषा उत्पन्न कर सकता है।
+[[Image:Chomsky-hierarchy.svg|thumb|right|200px|alt=The Chomsky hierarchy|चॉम्स्की पदानुक्रम द्वारा वर्णित समावेशन सेट करें]]चॉम्स्की पदानुक्रम (अक्सर इसे चॉम्स्की-शूट्ज़ेनबर्गर पदानुक्रम के रूप में जाना जाता है)<ref name=Allott>{{cite journal |last1=Allott |first1=Nicholas |last2=Lohndal |first2=Terje |last3=Rey |first3=Georges |title=संक्षिप्त परिचय|journal=A Companion to Chomsky |date=27 April 2021 |pages=1–17 |doi=10.1002/9781119598732.ch1 |url=https://www.researchgate.net/profile/Nicholas-Allott/publication/351812216_Synoptic_Introduction/links/641ff75c66f8522c38d42fd4/Synoptic-Introduction.pdf}}</ref>) [[औपचारिक भाषा]], [[कंप्यूटर विज्ञान]] और भाषाविज्ञान के क्षेत्र में, [[औपचारिक व्याकरण]] की कक्षाओं का पदानुक्रम#कंटेनमेंट पदानुक्रम है। औपचारिक व्याकरण यह वर्णन करता है कि किसी भाषा की शब्दावली (या वर्णमाला) से स्ट्रिंग कैसे बनाई जाए जो भाषा के वाक्यविन्यास के अनुसार मान्य हों। भाषाविद् [[नोम चौमस्की]] ने सिद्धांत दिया कि औपचारिक व्याकरण के चार अलग-अलग वर्ग मौजूद हैं जो तेजी से जटिल भाषाएँ उत्पन्न कर सकते हैं। प्रत्येक वर्ग पूरी तरह से सभी निम्न वर्गों की भाषा उत्पन्न कर सकता है।
 == इतिहास ==
 व्याकरण के पदानुक्रम का सामान्य विचार सबसे पहले भाषाविद् नोम चॉम्स्की द्वारा वर्णित किया गया था {{harvnb|Chomsky|1956}}. मार्सेल-पॉल शुट्ज़ेनबर्गर ने औपचारिक भाषाओं के सिद्धांत के विकास में भी भूमिका निभाई; कागज़ {{harvnb|Chomsky|Schützenberger|1963}} संदर्भ-मुक्त व्याकरण सहित आधुनिक पदानुक्रम का वर्णन करता है।<ref name=Allott/>
-स्वतंत्र रूप से और भाषाविदों के साथ, गणितज्ञ गणना मॉडल (ऑटोमेटा) विकसित कर रहे थे। किसी भाषा में एक वाक्य को पार्स करना गणना के समान है, और चॉम्स्की द्वारा वर्णित व्याकरण विभिन्न मशीन मॉडलों की कम्प्यूटेशनल शक्ति के समान और समकक्ष साबित हुए हैं।<ref>Kozen, Dexter C. "Automata and Computability" Springer, 1997. Pages 3-4</ref>
+स्वतंत्र रूप से और भाषाविदों के साथ, गणितज्ञ गणना मॉडल (ऑटोमेटा) विकसित कर रहे थे। किसी भाषा में वाक्य को पार्स करना गणना के समान है, और चॉम्स्की द्वारा वर्णित व्याकरण विभिन्न मशीन मॉडलों की कम्प्यूटेशनल शक्ति के समान और समकक्ष साबित हुए हैं।<ref>Kozen, Dexter C. "Automata and Computability" Springer, 1997. Pages 3-4</ref>
 == पदानुक्रम ==
 निम्नलिखित तालिका चॉम्स्की के चार प्रकार के व्याकरणों में से प्रत्येक का सारांश प्रस्तुत करती है, भाषा का वह वर्ग जो इसे उत्पन्न करता है, ऑटोमेटन का प्रकार जो इसे पहचानता है, और इसके नियमों का स्वरूप कैसा होना चाहिए।
@@ Line 51: / Line 49: @@
 प्रत्येक नियमित भाषा संदर्भ-मुक्त है, प्रत्येक संदर्भ-मुक्त भाषा संदर्भ-संवेदनशील है, प्रत्येक संदर्भ-संवेदनशील भाषा पुनरावर्ती है और प्रत्येक पुनरावर्ती भाषा पुनरावर्ती रूप से गणना योग्य है। ये सभी उचित समावेशन हैं, जिसका अर्थ है कि पुनरावर्ती रूप से गणना योग्य भाषाएं मौजूद हैं जो संदर्भ-संवेदनशील नहीं हैं, संदर्भ-संवेदनशील भाषाएं जो संदर्भ-मुक्त नहीं हैं और संदर्भ-मुक्त भाषाएं जो नियमित नहीं हैं।<ref>{{cite book |last=Chomsky |first=Noam |editor1-last=Luce |editor1-first=R. Duncan |editor2-last=Bush |editor2-first=Robert R. |editor3-last=Galanter |editor3-first=Eugene |year=1963 |title=गणितीय मनोविज्ञान की पुस्तिका|volume=II |chapter=Chapter 12: Formal Properties of Grammars |publisher=John Wiley and Sons, Inc. |pages=323–418}}</ref>
 ===प्रकार-0 व्याकरण===
-{{Cleanup section|reason=All these "type" sections would benefit from examples|date=June 2022}}
+टाइप-0 व्याकरण में सभी औपचारिक व्याकरण शामिल होते हैं। वे बिल्कुल सभी भाषाएँ उत्पन्न करते हैं जिन्हें [[ट्यूरिंग मशीन]] द्वारा पहचाना जा सकता है। इन भाषाओं को पुनरावर्ती गणना योग्य भाषा या ट्यूरिंग-पहचानने योग्य भाषा के रूप में भी जाना जाता है।<ref name=Sipser-1st>{{cite book |last=Sipser |first=Michael |author-link=Michael Sipser |year=1997 |title=संगणना के सिद्धांत का परिचय|edition=1st |publisher=Cengage Learning |isbn=0-534-94728-X |page=[https://archive.org/details/introductiontoth00sips/page/130 130] |url=https://archive.org/details/introductiontoth00sips/page/130 |url-access=registration |quote=The Church-Turing Thesis }}</ref> ध्यान दें कि यह पुनरावर्ती भाषाओं से भिन्न है, जिसे ऐसी मशीन द्वारा तय किया जा सकता है जो ट्यूरिंग मशीन को हमेशा रोकती है।
-{{main|Unrestricted grammar}}
-टाइप-0 व्याकरण में सभी औपचारिक व्याकरण शामिल होते हैं। वे बिल्कुल सभी भाषाएँ उत्पन्न करते हैं जिन्हें [[ट्यूरिंग मशीन]] द्वारा पहचाना जा सकता है। इन भाषाओं को पुनरावर्ती गणना योग्य भाषा या ट्यूरिंग-पहचानने योग्य भाषा के रूप में भी जाना जाता है।<ref name=Sipser-1st>{{cite book |last=Sipser |first=Michael |author-link=Michael Sipser |year=1997 |title=संगणना के सिद्धांत का परिचय|edition=1st |publisher=Cengage Learning |isbn=0-534-94728-X |page=[https://archive.org/details/introductiontoth00sips/page/130 130] |url=https://archive.org/details/introductiontoth00sips/page/130 |url-access=registration |quote=The Church-Turing Thesis }}</ref> ध्यान दें कि यह पुनरावर्ती भाषाओं से भिन्न है, जिसे एक ऐसी मशीन द्वारा तय किया जा सकता है जो ट्यूरिंग मशीन को हमेशा रोकती है।
 ===प्रकार-1 व्याकरण===
 {{main|Context-sensitive grammar}}
-टाइप-1 व्याकरण [[संदर्भ-संवेदनशील भाषा]]एँ उत्पन्न करते हैं। इन व्याकरणों में रूप के नियम होते हैं <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> साथ <math>A</math> एक नॉनटर्मिनल और <math>\alpha</math>, <math>\beta</math> और <math>\gamma</math> टर्मिनलों और/या गैर-टर्मिनलों की तारें। तार <math>\alpha</math> और <math>\beta</math> खाली हो सकता है, लेकिन <math>\gamma</math> गैररिक्त होना चाहिए. नियम <math>S \rightarrow \epsilon</math> अनुमति है यदि <math>S</math> किसी भी नियम के दाईं ओर प्रकट नहीं होता है. इन व्याकरणों द्वारा वर्णित भाषाएँ वास्तव में सभी भाषाएँ हैं जिन्हें एक रैखिक बाउंडेड ऑटोमेटन (एक गैर-नियतात्मक ट्यूरिंग मशीन जिसका टेप इनपुट की लंबाई के निरंतर समय से घिरा होता है) द्वारा पहचाना जा सकता है।
+टाइप-1 व्याकरण [[संदर्भ-संवेदनशील भाषा]]एँ उत्पन्न करते हैं। इन व्याकरणों में रूप के नियम होते हैं <math>\alpha A\beta \rightarrow \alpha\gamma\beta</math> साथ <math>A</math> नॉनटर्मिनल और <math>\alpha</math>, <math>\beta</math> और <math>\gamma</math> टर्मिनलों और/या गैर-टर्मिनलों की तारें। तार <math>\alpha</math> और <math>\beta</math> खाली हो सकता है, लेकिन <math>\gamma</math> गैररिक्त होना चाहिए. नियम <math>S \rightarrow \epsilon</math> अनुमति है यदि <math>S</math> किसी भी नियम के दाईं ओर प्रकट नहीं होता है. इन व्याकरणों द्वारा वर्णित भाषाएँ वास्तव में सभी भाषाएँ हैं जिन्हें रैखिक बाउंडेड ऑटोमेटन (एक गैर-नियतात्मक ट्यूरिंग मशीन जिसका टेप इनपुट की लंबाई के निरंतर समय से घिरा होता है) द्वारा पहचाना जा सकता है।
 ===प्रकार-2 व्याकरण===
 {{main|Context-free grammar}}
-टाइप-2 व्याकरण [[संदर्भ-मुक्त भाषा]]एँ उत्पन्न करते हैं। इन्हें प्रपत्र के नियमों द्वारा परिभाषित किया गया है <math>A \rightarrow \alpha</math> साथ <math>A</math> एक नॉनटर्मिनल होने के नाते और <math>\alpha</math> टर्मिनलों और/या गैर-टर्मिनलों की एक श्रृंखला होना। ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिन्हें एक गैर-नियतात्मक [[पुशडाउन ऑटोमेटन]] द्वारा पहचाना जा सकता है। संदर्भ-मुक्त भाषाएं - या इसके नियतात्मक संदर्भ-मुक्त भाषा का सबसेट - अधिकांश [[प्रोग्रामिंग भाषा]]ओं की वाक्यांश संरचना के लिए सैद्धांतिक आधार हैं, हालांकि उनके वाक्यविन्यास में घोषणाओं और स्कोप (कंप्यूटर) के कारण संदर्भ-संवेदनशील नाम रिज़ॉल्यूशन (प्रोग्रामिंग भाषाएं) भी शामिल हैं विज्ञान)। पार्सिंग को आसान बनाने के लिए अक्सर व्याकरणों के एक उपसमूह का उपयोग किया जाता है, जैसे कि [[एलएल पार्सर]] द्वारा।
+टाइप-2 व्याकरण [[संदर्भ-मुक्त भाषा]]एँ उत्पन्न करते हैं। इन्हें प्रपत्र के नियमों द्वारा परिभाषित किया गया है <math>A \rightarrow \alpha</math> साथ <math>A</math> नॉनटर्मिनल होने के नाते और <math>\alpha</math> टर्मिनलों और/या गैर-टर्मिनलों की श्रृंखला होना। ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिन्हें गैर-नियतात्मक [[पुशडाउन ऑटोमेटन]] द्वारा पहचाना जा सकता है। संदर्भ-मुक्त भाषाएं - या इसके नियतात्मक संदर्भ-मुक्त भाषा का सबसेट - अधिकांश [[प्रोग्रामिंग भाषा]]ओं की वाक्यांश संरचना के लिए सैद्धांतिक आधार हैं, हालांकि उनके वाक्यविन्यास में घोषणाओं और स्कोप (कंप्यूटर) के कारण संदर्भ-संवेदनशील नाम रिज़ॉल्यूशन (प्रोग्रामिंग भाषाएं) भी शामिल हैं विज्ञान)। पार्सिंग को आसान बनाने के लिए अक्सर व्याकरणों के उपसमूह का उपयोग किया जाता है, जैसे कि [[एलएल पार्सर]] द्वारा।
 ===प्रकार-3 व्याकरण===
 {{main|Regular grammar}}
-टाइप-3 व्याकरण [[नियमित भाषा]]एँ उत्पन्न करते हैं। ऐसा व्याकरण अपने नियमों को बाईं ओर एक एकल नॉनटर्मिनल तक सीमित करता है और दाईं ओर एक एकल टर्मिनल से युक्त होता है, जिसके बाद संभवतः एक एकल नॉनटर्मिनल (दाएं नियमित) होता है। वैकल्पिक रूप से, व्याकरण के दाईं ओर एक एकल टर्मिनल शामिल हो सकता है, संभवतः एक एकल नॉनटर्मिनल (बाएं नियमित) से पहले। ये समान भाषाएँ उत्पन्न करते हैं। हालाँकि, यदि बाएँ-नियमित नियमों और दाएँ-नियमित नियमों को मिला दिया जाए, तो भाषा को नियमित होने की आवश्यकता नहीं है। नियम <math>S \rightarrow \varepsilon</math> यदि यहाँ भी अनुमति है <math>S</math> किसी भी नियम के दाईं ओर प्रकट नहीं होता है. ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिनका निर्णय एक सीमित राज्य ऑटोमेटन द्वारा किया जा सकता है। इसके अतिरिक्त, औपचारिक भाषाओं के इस परिवार को [[नियमित अभिव्यक्ति]] द्वारा प्राप्त किया जा सकता है। नियमित भाषाओं का उपयोग आमतौर पर खोज पैटर्न और प्रोग्रामिंग भाषाओं की शाब्दिक संरचना को परिभाषित करने के लिए किया जाता है।
+टाइप-3 व्याकरण [[नियमित भाषा]]एँ उत्पन्न करते हैं। ऐसा व्याकरण अपने नियमों को बाईं ओर एकल नॉनटर्मिनल तक सीमित करता है और दाईं ओर एकल टर्मिनल से युक्त होता है, जिसके बाद संभवतः एकल नॉनटर्मिनल (दाएं नियमित) होता है। वैकल्पिक रूप से, व्याकरण के दाईं ओर एकल टर्मिनल शामिल हो सकता है, संभवतः एकल नॉनटर्मिनल (बाएं नियमित) से पहले। ये समान भाषाएँ उत्पन्न करते हैं। हालाँकि, यदि बाएँ-नियमित नियमों और दाएँ-नियमित नियमों को मिला दिया जाए, तो भाषा को नियमित होने की आवश्यकता नहीं है। नियम <math>S \rightarrow \varepsilon</math> यदि यहाँ भी अनुमति है <math>S</math> किसी भी नियम के दाईं ओर प्रकट नहीं होता है. ये भाषाएँ वास्तव में वे सभी भाषाएँ हैं जिनका निर्णय सीमित राज्य ऑटोमेटन द्वारा किया जा सकता है। इसके अतिरिक्त, औपचारिक भाषाओं के इस परिवार को [[नियमित अभिव्यक्ति]] द्वारा प्राप्त किया जा सकता है। नियमित भाषाओं का उपयोग आमतौर पर खोज पैटर्न और प्रोग्रामिंग भाषाओं की शाब्दिक संरचना को परिभाषित करने के लिए किया जाता है।
 ==यह भी देखें==
@@ Line 95: / Line 87: @@
   | page=[https://archive.org/details/computabilitycom00davi_405/page/n345 327]
   }}
-{{Formal languages and grammars}}
-{{Noam Chomsky}}
-{{Authority control}}
 [[Category: 1956 कंप्यूटिंग में]] [[Category: औपचारिक भाषाएँ]] [[Category: जनरेटिव भाषाविज्ञान]] [[Category: नोम चॉम्स्की|पदानुक्रम, चॉम्स्की]]

Anonymous

Search

चॉम्स्की पदानुक्रम: Difference between revisions

Namespaces

More

Page actions

Revision as of 21:39, 25 July 2023

Contents

इतिहास