अस्पष्ट व्याकरण: Difference between revisions

Latest revision as of 10:34, 12 August 2023

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

कंप्यूटर प्रोग्रामिंग लैंग्वेज के लिए, अन्य समस्या जैसे उद्देश्यों के कारण कांटेक्स्ट ग्रामर अधिकांशतः एम्बिगुयस होता है। यदि उपस्थित है, तो इन एम्बिगुयसओं को सामान्यतः प्राथमिकता नियमों या अन्य कांटेक्स्ट-सेंसिटिव ग्रामर या कांटेक्स्ट-सेंसिटिव पार्सिंग नियमों को जोड़कर हल किया जाता है, इसलिए समग्र वाक्यांश ग्रामर स्पष्ट है। कुछ पार्सिंग एल्गोरिदम (जैसे कि (अर्ली पार्सर) ^[2] या सामान्यीकृत एलआर पार्सर) उन स्ट्रिंग्स से पार्स ट्री (या पार्स फ़ॉरेस्ट) के सेट उत्पन्न कर सकते हैं जो सिंटेक्टिकली एम्बिगुयस हैं।^[3]

उदाहरण

सामान्य लैंग्वेज

सबसे सरल उदाहरण उस सामान्य लैंग्वेज के लिए निम्नलिखित एम्बिगुयस ग्रामर (प्रारंभ प्रतीक A के साथ) है जिसमें केवल रिक्त स्ट्रिंग सम्मिलित है:

A → A | ε

जिसका अर्थ यह है कि नॉनटर्मिनल A को या तो स्वयं से, या रिक्त स्ट्रिंग से प्राप्त किया जा सकता है। इस प्रकार रिक्त स्ट्रिंग में लंबाई 1, 2, 3 और वास्तव में किसी भी लंबाई की सबसे बाईं व्युत्पत्ति होती है, यह इस पर निर्भर करता है कि नियम A → A का कितनी बार उपयोग किया जाता है।

इस लैंग्वेज में स्पष्ट ग्रामर भी है, जिसमें एकल प्रोडक्शन नियम (फॉर्मल लैंग्वेज) सम्मिलित हैं:

A → ε

...कारण कि अद्वितीय प्रोडक्शन केवल रिक्त स्ट्रिंग का प्रोडक्शन कर सकता है, जो लैंग्वेज में अद्वितीय स्ट्रिंग है।

उसी तरह, किसी नॉन-रिक्त लैंग्वेज के लिए किसी भी ग्रामर को डुप्लिकेट जोड़कर एम्बिगुयस बनाया जा सकता है।

यूनरी स्ट्रिंग

किसी दिए गए वर्ण की यूनरी स्ट्रिंग्स की रेगुलर लैंग्वेज, 'a' (रेगुलर अभिव्यक्ति a*), स्पष्ट ग्रामर है:

A → aA | ε

...किन्तु इसमें एम्बिगुयस ग्रामर भी है:

A → aA | Aa | ε

यह दाएँ-साहचर्य ट्री (स्पष्ट ग्रामर के लिए) का निर्माण करने या बाएँ और दाएँ-दोनों-सहयोग की अनुमति देने के अनुरूप हैं। इसका विवरण नीचे दिया गया है।

जोड़ना और घटाना

कांटेक्स्ट फ्री ग्रामर

A → A + A | A - A | A

यह एम्बिगुयस है क्योंकि स्ट्रिंग a + a + a के लिए दो सबसे बाईं व्युत्पत्तियाँ हैं:

A	→ A + A	A	→ A + A
	→ a + A		→ A + A + A (पहले A को A+A से बदल दिया गया है। दूसरे A के प्रतिस्थापन से समान व्युत्पत्ति प्राप्त होगी)
	→ a + A + A		→ a + A + A
	→ a + a + A		→ a + a + A
	→ a + a + a		→ a + a + a

एक अन्य उदाहरण के रूप में, ग्रामर एम्बिगुयस है क्योंकि स्ट्रिंग A + A - A के लिए दो पार्स ट्री हैं:

चूँकि, यह जो लैंग्वेज उत्पन्न करता है, वह स्वाभाविक रूप से एम्बिगुयस नहीं है; निम्नलिखित नॉन-एम्बिगुयस ग्रामर है जो समान लैंग्वेज उत्पन्न करता है:

ए → A + A | A - A | ए

डैंगलिंग एल्स

कंप्यूटर प्रोग्रामिंग लैंग्वेज में एम्बिगुयस का सामान्य उदाहरण डैंगलिंग हुई अन्य समस्या है। अनेक लैंग्वेज में, else कंडीशनल (कंप्यूटर प्रोग्रामिंग) में If–then(–else) या If–then(–else) स्टेटमेंट वैकल्पिक है, जिसके परिणामस्वरूप नेस्टेड कंडीशनल को कांटेक्स्ट-फ्री ग्रामर के कांटेक्स्ट में पहचाने जाने के अनेक विधि होते हैं।

सामान्यतः, अनेक लैंग्वेज में कोई नियमबद्ध को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है:^{[note 1]}

नियमों से युक्त ग्रामर में

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

कुछ एम्बिगुयस वाक्यांश संरचनाएँ प्रकट हो सकती हैं।

if a then if b then s else s2

किसी भी रूप में पार्स किया जा सकता है

if a then begin if b then s end else s2

या जैसे

if a then begin if b then s else s2 end

इस पर निर्भर करता है कि क्या else पहले से जुड़ा है if या दूसरा if.

इसे विभिन्न लैंग्वेज में विभिन्न विधियों से हल किया जाता है। कभी-कभी ग्रामर को संशोधित किया जाता है जिससे यह स्पष्ट हो जाती है, जैसे कि इसकी आवश्यकता होती है इस प्रकार endif कथन या कथन करना else अनिवार्य अन्य स्थितियों में ग्रामर को एम्बिगुयस छोड़ दिया जाता है, किन्तु समग्र वाक्यांश ग्रामर को कांटेक्स्ट-सेंसिटिव बनाकर एम्बिगुयस का समाधान किया जाता है, जैसे कि किसी को संबद्ध करके else निकटतम के साथ if. इस बाद वाले स्थिति में ग्रामर एम्बिगुयस है, किन्तु कांटेक्स्ट-फ्री ग्रामर एम्बिगुयस है।

अनेक व्युत्पत्तियों वाला स्पष्ट ग्रामर

एक ही स्ट्रिंग की एकाधिक व्युत्पत्तियों का अस्तित्व यह इंगित करने के लिए पर्याप्त नहीं है कि ग्रामर एम्बिगुयस है; केवल एकाधिक बाईं ओर की व्युत्पत्तियाँ (या, समकक्ष, एकाधिक पार्स ट्री) एम्बिगुयस का संकेत देती हैं।

उदाहरण के लिए, सरल ग्रामर

S → A + A
A → 0 | 1

लैंग्वेज के लिए स्पष्ट ग्रामर है { 0+0, 0+1, 1+0, 1+1 }। चूँकि इन चार तारों में से प्रत्येक में केवल बाईं ओर की व्युत्पत्ति है, उदाहरण के लिए, इसकी दो भिन्न-भिन्न व्युत्पत्तियाँ हैं

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

और

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

केवल पूर्व व्युत्पत्ति ही सबसे बाईं ओर है।

एम्बिगुयस ग्रामर को पहचानना

एक अनैतिक ग्रामर एम्बिगुयस है या नहीं इसकी निर्णय समस्या अनिर्णीत समस्या है क्योंकि यह दिखाया जा सकता है कि यह पोस्ट कॉरेस्पोंडेंस समस्या के सामान्य है।^[4] कम से कम, कांटेक्स्ट-फ्री ग्रामर की एम्बिगुयस का पता लगाने के लिए कुछ अर्ध-निर्णायक या अर्ध-निर्णय प्रक्रिया को प्रयुक्त करने वाले उपकरण उपस्थित हैं।^[5]

कांटेक्स्ट-फ्री ग्रामर को पार्स करने की दक्षता इसे स्वीकार करने वाले ऑटोमेटन द्वारा निर्धारित की जाती है। डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर डेटर्मिनिस्टिक पुशडाउन ऑटोमेटा द्वारा स्वीकार किए जाते हैं और इन्हें रैखिक समय में पार्स किया जा सकता है, उदाहरण के लिए एलआर पार्सर द्वारा ^[6] वह कांटेक्स्ट-फ्री ग्रामर का सख्त उपसमूह हैं, जिन्हें पुशडाउन ऑटोमेटा द्वारा स्वीकार किया जाता है और बहुपद समय में पार्स किया जा सकता है, उदाहरण के लिए CYK एल्गोरिदम द्वारा प्रयोग इया जाता है।

अनएम्बिगुयस कांटेक्स्ट-फ्री ग्रामर नॉन-डेटर्मिनिस्टिक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले विलोमपद की लैंग्वेज में स्पष्ट कांटेक्स्ट-फ्री ग्रामर S → 0S0 1S1 ε. इस लैंग्वेज की अनैतिक स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करता है।^[7] फिर भी, YACC रण की एम्बिगुयस को दूर करने से डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की एम्बिगुयस को हल करने की विशेषताएं सम्मिलित हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करता है।

स्वाभाविक रूप से एम्बिगुयस लैंग्वेज

जबकि कुछ कांटेक्स्ट-फ्री लैंग्वेज (स्ट्रिंग का सेट जो ग्रामर द्वारा उत्पन्न किया जा सकता है) में एम्बिगुयस और स्पष्ट ग्रामर दोनों होते हैं, वहीं कांटेक्स्ट-फ्री लैंग्वेज उपस्थित होती हैं जिनके लिए कोई भी स्पष्ट कांटेक्स्ट-फ्री ग्रामर उपस्थित नहीं हो सकता है। ऐसी लैंग्वेज को स्वाभाविक रूप से एम्बिगुयस कहा जाता है।

कोई स्वाभाविक रूप से एम्बिगुयस रेगुलर लैंग्वेज नहीं हैं।^[8]^[9] स्वाभाविक रूप से एम्बिगुयस कांटेक्स्ट-फ्री लैंग्वेज का अस्तित्व 1961 में रोहित पारीख द्वारा एमआईटी शोध रिपोर्ट में पारिख के प्रमेय के साथ सिद्ध किया गया था।^[10] लैंग्वेज $\{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ or }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ where }}n,n',m,m'\geq 1\}$ स्वाभाविक रूप से एम्बिगुयस है.^[11]

ओग्डेन की लेम्मा ^[12] यह सिद्ध करने के लिए उपयोग किया जा सकता है कि कुछ कांटेक्स्ट-फ्री लैंग्वेज, जैसे कि $\{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}$ , स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए यह पृष्ठ देखें.

यूनियन $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ साथ $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ स्वाभाविक रूप से एम्बिगुयस है. यह सेट कांटेक्स्ट-फ्री है, क्योंकि दो कांटेक्स्ट-फ्री लैंग्वेज का मिलन सदैव कांटेक्स्ट-फ्री होता है। किन्तु हॉपक्रॉफ्ट & उल्मन (1979) इस बात का प्रमाण दें कि इस यूनियन लैंग्वेज के लिए कोई भी कांटेक्स्ट-फ्री ग्रामर रूप के तारों $a^{n}b^{n}c^{n}d^{n},(n>0)$ को स्पष्ट रूप से पार्स नहीं कर सकता है.^[13]

अधिक उदाहरण, और कांटेक्स्ट-फ्री लैंग्वेज की अंतर्निहित एम्बिगुयस को सिद्ध करने के लिए तकनीकों की सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।^[14]

यह भी देखें

जीएलआर पार्सर, एम्बिगुयस और नॉन-डेटर्मिनिस्टिक ग्रामर के लिए एक प्रकार का पार्सर
चार्ट पार्सर, एम्बिगुयस ग्रामर के लिए अन्य प्रकार का पार्सर
सिंटेक्टिक एम्बिगुयस

कांटेक्स्ट

↑ Willem J. M. Levelt (2008). औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय. John Benjamins Publishing. ISBN 978-90-272-3250-2.
↑ Scott, Elizabeth (April 1, 2008). "प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.
↑ Tomita, Masaru. "An efficient augmented-context-free parsing algorithm." Computational linguistics 13.1-2 (1987): 31-46.
↑ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. Theorem 9.20, pp. 405–406. ISBN 0-201-44124-1.
↑ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Lecture Notes in Computer Science. Vol. 5126. Springer-Verlag. pp. 410–422. doi:10.1007/978-3-540-70583-3_34. ISBN 978-3-540-70582-6.
↑ Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
↑ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. pp. 249–253. ISBN 0-201-44124-1.
↑ Book, R.; Even, S.; Greibach, S.; Ott, G. (Feb 1971). "रेखांकन और अभिव्यक्ति में अस्पष्टता". IEEE Transactions on Computers. C-20 (2): 149–153. doi:10.1109/t-c.1971.223204. ISSN 0018-9340. S2CID 20676251.
↑ "formal languages - Can regular expressions be made unambiguous?". MathOverflow (in English). Retrieved 2023-02-23.
↑ Parikh, Rohit (January 1961). भाषा उत्पन्न करने वाले उपकरण. Quarterly Progress Report, Research Laboratory of Electronics, MIT.
↑ Parikh, Rohit J. (1966-10-01). "प्रसंग-मुक्त भाषाओं पर". Journal of the ACM. 13 (4): 570–581. doi:10.1145/321356.321364. ISSN 0004-5411. S2CID 12263468. Here: Theorem 3.
↑ Ogden, William (Sep 1968). "अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/bf01694004. ISSN 0025-5661. S2CID 13197551.
↑ p.99-103, Sect.4.7
↑ Fredérique Bassino and Cyril Nicaud (December 16, 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF). Archived (PDF) from the original on 2022-09-25.

Gross, Maurice (September 1964). "Inherent ambiguity of minimal linear grammars". Information and Control. 7 (3): 366–368. doi:10.1016/S0019-9958(64)90422-X.
Michael, Harrison (1978). Introduction to Formal Language Theory. Addison-Wesley. ISBN 0201029553.
Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 9780201029888.
Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to Automata Theory, Languages and Computation (2nd ed.). Addison Wesley. pp. 217. ISBN 9780201441246.
Brabrand, Claus; Giegerich, Robert; Møller, Anders (March 2010). "Analyzing Ambiguity of Context-Free Grammars". Science of Computer Programming. Elsevier. 75 (3): 176–191. CiteSeerX 10.1.1.86.3118. doi:10.1016/j.scico.2009.11.002.

बाहरी संबंध

dk.brics.grammar - a grammar ambiguity analyzer.
CFGAnalyzer - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.

[Levelt2008-1] Willem J. M. Levelt (2008). औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय. John Benjamins Publishing. ISBN 978-90-272-3250-2.

[2] Scott, Elizabeth (April 1, 2008). "प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.

[3] Tomita, Masaru. "An efficient augmented-context-free parsing algorithm." Computational linguistics 13.1-2 (1987): 31-46.

[5] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. Theorem 9.20, pp. 405–406. ISBN 0-201-44124-1.

[6] Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Lecture Notes in Computer Science. Vol. 5126. Springer-Verlag. pp. 410–422. doi:10.1007/978-3-540-70583-3_34. ISBN 978-3-540-70582-6.

[7] Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.

[8] Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. pp. 249–253. ISBN 0-201-44124-1.

[9] Book, R.; Even, S.; Greibach, S.; Ott, G. (Feb 1971). "रेखांकन और अभिव्यक्ति में अस्पष्टता". IEEE Transactions on Computers. C-20 (2): 149–153. doi:10.1109/t-c.1971.223204. ISSN 0018-9340. S2CID 20676251.

[10] "formal languages - Can regular expressions be made unambiguous?". MathOverflow (in English). Retrieved 2023-02-23.

[11] Parikh, Rohit (January 1961). भाषा उत्पन्न करने वाले उपकरण. Quarterly Progress Report, Research Laboratory of Electronics, MIT.

[12] Parikh, Rohit J. (1966-10-01). "प्रसंग-मुक्त भाषाओं पर". Journal of the ACM. 13 (4): 570–581. doi:10.1145/321356.321364. ISSN 0004-5411. S2CID 12263468. Here: Theorem 3.

[13] Ogden, William (Sep 1968). "अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/bf01694004. ISSN 0025-5661. S2CID 13197551.

[14] .99-103, Sect.4.7

[15] Fredérique Bassino and Cyril Nicaud (December 16, 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF). Archived (PDF) from the original on 2022-09-25.

[4] The following example uses Pascal syntax

[1]

[2]

[3]

[note 1]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 3: / Line 3: @@
 कंप्यूटर [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज के लिए, अन्य समस्या जैसे उद्देश्यों के कारण कांटेक्स्ट ग्रामर अधिकांशतः एम्बिगुयस होता है। यदि उपस्थित है, तो इन एम्बिगुयसओं को सामान्यतः प्राथमिकता नियमों या अन्य [[संदर्भ-संवेदनशील व्याकरण|कांटेक्स्ट-सेंसिटिव ग्रामर]] या कांटेक्स्ट-सेंसिटिव पार्सिंग नियमों को जोड़कर हल किया जाता है, इसलिए समग्र वाक्यांश ग्रामर स्पष्ट है। कुछ पार्सिंग एल्गोरिदम (जैसे कि ([[अर्ली पार्सर]]) <ref>{{cite journal|last1=Scott|first1=Elizabeth|title=प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग|journal=Electronic Notes in Theoretical Computer Science|date=April 1, 2008|volume=203|issue=2|pages=53–67|doi=10.1016/j.entcs.2008.03.044|doi-access=free}}</ref> या [[सामान्यीकृत एलआर पार्सर]]) उन स्ट्रिंग्स से पार्स ट्री (या पार्स फ़ॉरेस्ट) के सेट उत्पन्न कर सकते हैं जो [[वाक्यात्मक रूप से अस्पष्ट|सिंटेक्टिकली]] एम्बिगुयस हैं।<ref>Tomita, Masaru. "[http://anthology.aclweb.org/J/J87/J87-1004.pdf An efficient augmented-context-free parsing algorithm]." Computational linguistics 13.1-2 (1987): 31-46.</ref>
 ==उदाहरण==
@@ Line 12: / Line 10: @@
 जिसका अर्थ यह है कि नॉनटर्मिनल A को या तो स्वयं से, या रिक्त स्ट्रिंग से प्राप्त किया जा सकता है। इस प्रकार रिक्त स्ट्रिंग में लंबाई 1, 2, 3 और वास्तव में किसी भी लंबाई की सबसे बाईं व्युत्पत्ति होती है, यह इस पर निर्भर करता है कि नियम A → A का कितनी बार उपयोग किया जाता है।
-इस लैंग्वेज में स्पष्ट ग्रामर भी है, जिसमें एकल [[उत्पादन नियम (औपचारिक भाषाएँ)|प्रोडक्शन नियम (औपचारिक लैंग्वेज)]] सम्मिलित हैं:
+इस लैंग्वेज में स्पष्ट ग्रामर भी है, जिसमें एकल [[उत्पादन नियम (औपचारिक भाषाएँ)|प्रोडक्शन नियम (फॉर्मल लैंग्वेज)]] सम्मिलित हैं:
 :A → ε
 ...कारण कि अद्वितीय प्रोडक्शन केवल रिक्त स्ट्रिंग का प्रोडक्शन कर सकता है, जो लैंग्वेज में अद्वितीय स्ट्रिंग है।
@@ Line 25: / Line 23: @@
 यह दाएँ-साहचर्य ट्री (स्पष्ट ग्रामर के लिए) का निर्माण करने या बाएँ और दाएँ-दोनों-सहयोग की अनुमति देने के अनुरूप हैं। इसका विवरण नीचे दिया गया है।
-===जोड़ और घटाव===
+===जोड़ना और घटाना===
 कांटेक्स्ट फ्री ग्रामर
 :A → A + A | A - A | A
@@ Line 60: / Line 58: @@
 {{main|डैंगलिंग एल्स}}
-कंप्यूटर प्रोग्रामिंग लैंग्वेज में एम्बिगुयस का सामान्य उदाहरण डैंगलिंग हुई अन्य समस्या है। अनेक लैंग्वेज में, <code>else</code> कंडीशनल (कंप्यूटर प्रोग्रामिंग) में If–then(–else)  या If–then(–else) स्टेटमेंट वैकल्पिक है, जिसके परिणामस्वरूप नेस्टेड कंडीशनल को कांटेक्स्ट-फ्री ग्रामर के कांटेक्स्ट में पहचाने जाने के अनेक विधि होते हैं।
+कंप्यूटर प्रोग्रामिंग लैंग्वेज में एम्बिगुयस का सामान्य उदाहरण डैंगलिंग हुई अन्य समस्या है। अनेक लैंग्वेज में, <code>else</code> कंडीशनल (कंप्यूटर प्रोग्रामिंग) में If–then(–else) या If–then(–else) स्टेटमेंट वैकल्पिक है, जिसके परिणामस्वरूप नेस्टेड कंडीशनल को कांटेक्स्ट-फ्री ग्रामर के कांटेक्स्ट में पहचाने जाने के अनेक विधि होते हैं।
 सामान्यतः, अनेक लैंग्वेज में कोई नियमबद्ध को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है:<ref group=note>The following example uses [[Pascal (programming language)|Pascal]] syntax</ref>
@@ Line 93: / Line 91: @@
 ==एम्बिगुयस ग्रामर को पहचानना==
-एक अनैतिक ग्रामर एम्बिगुयस है या नहीं इसकी [[निर्णय समस्या]] [[अनिर्णीत समस्या]] है क्योंकि यह दिखाया जा सकता है कि यह [[पोस्ट पत्राचार समस्या|पोस्ट कॉरेस्पोंडेंस समस्या]] के सामान्य है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 | at = Theorem 9.20, pp. 405–406}}</ref> कम से कम, कांटेक्स्ट-फ्री ग्रामर की एम्बिगुयस का पता लगाने के लिए कुछ अर्ध-निर्णायक  या अर्ध-निर्णय प्रक्रिया को प्रयुक्त करने वाले उपकरण उपस्थित हैं।<ref>{{cite conference | last1 = Axelsson | first1 = Roland | last2 = Heljanko | first2 = Keijo | last3 = Lange | first3 = Martin | year = 2008 | title = वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण| book-title = Proceedings of the 35th [[International Colloquium on Automata, Languages and Programming]] (ICALP'08), Reykjavik, Iceland | series = [[Lecture Notes in Computer Science]] | volume = 5126 | pages = 410–422 | publisher = Springer-Verlag | doi = 10.1007/978-3-540-70583-3_34 | isbn = 978-3-540-70582-6 | url = http://www.tcs.hut.fi/~kepa/publications/AxelssonHeljankoLange-ICALP08.pdf }}</ref>
+एक अनैतिक ग्रामर एम्बिगुयस है या नहीं इसकी [[निर्णय समस्या]] [[अनिर्णीत समस्या]] है क्योंकि यह दिखाया जा सकता है कि यह [[पोस्ट पत्राचार समस्या|पोस्ट कॉरेस्पोंडेंस समस्या]] के सामान्य है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 | at = Theorem 9.20, pp. 405–406}}</ref> कम से कम, कांटेक्स्ट-फ्री ग्रामर की एम्बिगुयस का पता लगाने के लिए कुछ अर्ध-निर्णायक या अर्ध-निर्णय प्रक्रिया को प्रयुक्त करने वाले उपकरण उपस्थित हैं।<ref>{{cite conference | last1 = Axelsson | first1 = Roland | last2 = Heljanko | first2 = Keijo | last3 = Lange | first3 = Martin | year = 2008 | title = वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण| book-title = Proceedings of the 35th [[International Colloquium on Automata, Languages and Programming]] (ICALP'08), Reykjavik, Iceland | series = [[Lecture Notes in Computer Science]] | volume = 5126 | pages = 410–422 | publisher = Springer-Verlag | doi = 10.1007/978-3-540-70583-3_34 | isbn = 978-3-540-70582-6 | url = http://www.tcs.hut.fi/~kepa/publications/AxelssonHeljankoLange-ICALP08.pdf }}</ref>
 कांटेक्स्ट-फ्री ग्रामर को पार्स करने की दक्षता इसे स्वीकार करने वाले ऑटोमेटन द्वारा निर्धारित की जाती है। डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर [[नियतात्मक पुशडाउन ऑटोमेटा|डेटर्मिनिस्टिक पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किए जाते हैं और इन्हें रैखिक समय में पार्स किया जा सकता है, उदाहरण के लिए [[एलआर पार्सर]] द्वारा <ref>{{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access = free }}</ref> वह [[संदर्भ-मुक्त व्याकरण|कांटेक्स्ट-फ्री]] ग्रामर का सख्त उपसमूह हैं, जिन्हें [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किया जाता है और बहुपद समय में पार्स किया जा सकता है, उदाहरण के लिए CYK एल्गोरिदम द्वारा प्रयोग इया जाता है।
-अनएम्बिगुयस कांटेक्स्ट-फ्री ग्रामर नॉन-डेटर्मिनिस्टिक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले [[विलोमपद]] की लैंग्वेज में स्पष्ट कांटेक्स्ट-फ्री ग्रामर S → 0S0 1S1 ε. इस लैंग्वेज की अनैतिक स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करता है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 |pages=249–253}}</ref> फिर भी, [[ YACC | YACC]] रण की एम्बिगुयस को दूर करने से डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की एम्बिगुयस को हल करने की विशेषताएं सम्मिलित हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करता है।
+अनएम्बिगुयस कांटेक्स्ट-फ्री ग्रामर नॉन-डेटर्मिनिस्टिक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले [[विलोमपद]] की लैंग्वेज में स्पष्ट कांटेक्स्ट-फ्री ग्रामर S → 0S0 1S1 ε. इस लैंग्वेज की अनैतिक स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करता है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 |pages=249–253}}</ref> फिर भी, [[ YACC |YACC]] रण की एम्बिगुयस को दूर करने से डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की एम्बिगुयस को हल करने की विशेषताएं सम्मिलित हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करता है।
 ==स्वाभाविक रूप से एम्बिगुयस लैंग्वेज==
@@ Line 105: / Line 103: @@
 ओग्डेन की लेम्मा <ref>{{Cite journal |last=Ogden |first=William |date=Sep 1968 |title=अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम|url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661}}</ref> यह सिद्ध करने के लिए उपयोग किया जा सकता है कि कुछ कांटेक्स्ट-फ्री लैंग्वेज, जैसे कि <math>\{a^nb^mc^m | m, n \geq 1\} \cup \{a^mb^mc^n | m, n \geq 1\}</math>, स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए यह पृष्ठ देखें.
 यूनियन <math>\{a^n b^m c^m d^n \mid n, m > 0\}</math> साथ <math>\{a^n b^n c^m d^m \mid n, m > 0\}</math> स्वाभाविक रूप से एम्बिगुयस है. यह सेट कांटेक्स्ट-फ्री है, क्योंकि दो कांटेक्स्ट-फ्री लैंग्वेज का मिलन सदैव कांटेक्स्ट-फ्री होता है। किन्तु {{harvtxt|हॉपक्रॉफ्ट|उल्मन|1979}} इस बात का प्रमाण दें कि इस यूनियन लैंग्वेज के लिए कोई भी कांटेक्स्ट-फ्री ग्रामर रूप के तारों <math>a^n b^n c^n d^n, (n > 0)</math> को स्पष्ट रूप से पार्स नहीं कर सकता है.<ref>p.99-103, Sect.4.7</ref>
 अधिक उदाहरण, और कांटेक्स्ट-फ्री लैंग्वेज की अंतर्निहित एम्बिगुयस को सिद्ध करने के लिए तकनीकों की सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।<ref>{{Cite web |author=Fredérique Bassino and Cyril Nicaud |date=December 16, 2011 |title=Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages |url=https://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |url-status=live |archive-url=https://web.archive.org/web/20220925135141/http://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |archive-date=2022-09-25}}</ref>
 ==यह भी देखें==
 *[[जीएलआर पार्सर]], एम्बिगुयस और नॉन-डेटर्मिनिस्टिक ग्रामर के लिए एक प्रकार का पार्सर
@@ Line 169: / Line 163: @@
   }}
 * {{cite journal |last1=Brabrand |first1=Claus |last2=Giegerich |first2=Robert |last3=Møller |first3=Anders |date=March 2010 |title=Analyzing Ambiguity of Context-Free Grammars  |journal=Science of Computer Programming |volume=75 |issue=3 |pages=176–191 |publisher=Elsevier |doi=10.1016/j.scico.2009.11.002 |citeseerx=10.1.1.86.3118 }}
 ==टिप्पणियाँ==
 {{reflist|group=note}}
 ==बाहरी संबंध==
 *[http://www.brics.dk/grammar dk.brics.grammar] - a grammar ambiguity analyzer.
 *[https://web.archive.org/web/20110719055512/http://www2.tcs.ifi.lmu.de/~mlange/cfganalyzer/index.html CFGAnalyzer] - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.
-[[Category: औपचारिक भाषाएँ]] [[Category: अनिश्चितता]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
 [[Category:Created On 26/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Pages with syntax highlighting errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:अनिश्चितता]]
+[[Category:औपचारिक भाषाएँ]]

Anonymous

Search

अस्पष्ट व्याकरण: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:34, 12 August 2023

Contents

उदाहरण

सामान्य लैंग्वेज

यूनरी स्ट्रिंग

जोड़ना और घटाना

डैंगलिंग एल्स

अनेक व्युत्पत्तियों वाला स्पष्ट ग्रामर

एम्बिगुयस ग्रामर को पहचानना

स्वाभाविक रूप से एम्बिगुयस लैंग्वेज

यह भी देखें

कांटेक्स्ट

टिप्पणियाँ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

अस्पष्ट व्याकरण: Difference between revisions

Latest revision as of 10:34, 12 August 2023

उदाहरण

सामान्य लैंग्वेज

यूनरी स्ट्रिंग

जोड़ना और घटाना

डैंगलिंग एल्स

अनेक व्युत्पत्तियों वाला स्पष्ट ग्रामर

एम्बिगुयस ग्रामर को पहचानना

स्वाभाविक रूप से एम्बिगुयस लैंग्वेज

यह भी देखें

कांटेक्स्ट

टिप्पणियाँ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories