कांटैक्स्ट फ्री लैंग्वेज: Difference between revisions

Revision as of 23:36, 7 August 2023

औपचारिक लैंग्वेज के सिद्धांत में, कांटैक्स्ट फ्री लैंग्वेज (सीएफएल) कांटैक्स्ट फ्री ग्रामर (सीएफजी) द्वारा उत्पन्न होने वाली औपचारिक लैंग्वेज है।

प्रोग्रामिंग लैंग्वेज में कांटैक्स्ट फ्री लैंग्वेज के कई अनुप्रयोग होते हैं, विशेष रूप से अधिकांश अंकगणितीय अभिव्यक्तियाँ कांटैक्स्ट फ्री ग्रामर द्वारा उत्पन्न होती हैं।

पृष्ठभूमि

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

विभिन्न कांटैक्स्ट फ्री ग्रामर ही कांटैक्स्ट फ्री लैंग्वेज उत्पन्न कर सकते हैं। इस प्रकार की लैंग्वेज का वर्णन करने वाले कई व्याकरणों की तुलना करके लैंग्वेज के आंतरिक गुणों को किसी विशेष व्याकरण के बाहरी गुणों से अलग किया जा सकता है।

ऑटोमेटा

सभी कांटैक्स्ट फ्री लैंग्वेज का सेट पुशडाउन ऑटोमेटा द्वारा स्वीकृत लैंग्वेजेस के सेट के समान है, जो इन लैंग्वेजेस को पार्सिंग के लिए उत्तरदायी बनाता है। इसके अतिरिक्त किसी दिए गए सीएफजी के लिए, व्याकरण और इस प्रकार संबंधित लैंग्वेज के लिए पुशडाउन ऑटोमेटा का उत्पादन करने की सीधा विधि है, चूंकि दूसरे तरीके से जाना एक ऑटोमेटा दिए गए व्याकरण का निर्माण करना हैं जो उतना सरल नहीं है।

उदाहरण

$L=\{a^{n}b^{n}:n\geq 1\}$ कांटैक्स्ट फ्री लैंग्वेज का उदाहरण है, जिसमें सभी गैर-रिक्त सम-लंबाई वाले तारों की लैंग्वेज, जिनके पूरे $a$ 's का यह पहला भाग हैं, और जिसके पूरे दूसरे भाग $b$ 'एस हैं। यहाँ पर $L$ व्याकरण द्वारा $S\to aSb~|~ab$ उत्पन्न होता है,

यह लैंग्वेज रेगुलर लैंग्वेज नहीं है, इसे पुशडाउन ऑटोमेटा के आधार पर औपचारिक को-लैंग्वेज द्वारा स्वीकार किया जाता है, जिसके आधार पर $M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})$ के समान रखा जाता हैं, जहाँ $\delta$ को इस प्रकार परिभाषित किया गया है:^{[note 1]}

{\begin{aligned}\delta (q_{0},a,z)&=(q_{0},az)\\\delta (q_{0},a,a)&=(q_{0},aa)\\\delta (q_{0},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},\varepsilon ,z)&=(q_{f},\varepsilon )\end{aligned}}

असंदिग्ध सीएफएल सभी सीएफएल का उचित उपसमूह हैं: इसके आधार पर स्वाभाविक रूप से अस्पष्ट लैंग्वेज सीएफएल हैं। इसका स्वाभाविक रूप से अस्पष्ट सीएफएल का उदाहरण संघ $\{a^{n}b^{m}c^{m}d^{n}|n,m>0\}$ साथ $\{a^{n}b^{n}c^{m}d^{m}|n,m>0\}$ है, यह मुख्य रूप से सेट संदर्भ-मुक्त है, क्योंकि दो कांटैक्स्ट फ्री लैंग्वेज का मिलन सदैव संदर्भ-मुक्त होता है। अपितु (गैर-संदर्भ-मुक्त) उपसमुच्चय में स्ट्रिंग्स $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$ को स्पष्ट रूप से पार्स करने की कोई विधि नहीं है, जो इन दोनों लैंग्वेजेस का प्रतिच्छेदन करती है।^[1]

डाइक लैंग्वेज

डाइक लैंग्वेज व्याकरण $S\to SS~|~(S)~|~\varepsilon$ द्वारा उत्पन्न होती है।

गुण

कांटैक्स्ट फ्री पार्सिंग

लैंग्वेज की संदर्भ-मुक्त प्रकृति पुशडाउन ऑटोमेटा के साथ पार्स करना सरल बनाती है।

सदस्यता समस्या का उदाहरण निर्धारित करना अर्ताथ स्ट्रिंग $w$ दी गई है, जहाँ पता लगाया जाता हैं कि क्या $w\in L(G)$ के समान हैं। जहाँ $L$ किसी दिए गए व्याकरण द्वारा उत्पन्न होने वाले $G$ लैंग्वेज के समान है, इसे मान्यता के रूप में भी जाना जाता है। इसके आधार पर चॉम्स्की सामान्य रूप व्याकरण के लिए संदर्भ-मुक्त मान्यता लेस्ली वैलिएंट द्वारा दिखाई गई थी। इस प्रकार लेस्ली जी. वैलिएंट को बूलियन आव्यूह गुणन के लिए कम किया जा सकता है, इस प्रकार इसकी जटिलता बिग ओ नोटेशन की ऊपरी सीमा को विरासत में मिली है।^2.3728596).^[2]^{[note 2]}

इसके विपरीत, लिलियन ली (कंप्यूटर वैज्ञानिक) ने O(n)^3−ε दिखाया है, जिसके आधार पर बूलियन आव्यूह गुणन को O(n)^3−3ε तक कम किया जा सकता है, इसके फल्स्वरूप सीएफजी पार्सिंग के लिए इस प्रकार बाद के लिए कुछ प्रकार की निचली सीमा स्थापित करता है।^[3]

कांटैक्स्ट फ्री लैंग्वेज के व्यावहारिक उपयोग के लिए इनहैरिटेड ट्री तैयार करने की भी आवश्यकता होती है, जो उस संरचना को प्रदर्शित करता है जिसे व्याकरण दिए गए स्ट्रिंग के साथ जोड़ता है। इस ट्री के उत्पादन की प्रक्रिया को पदच्छेद कहा जाता है। इससे ज्ञात होने वाले पार्सर्स में समय जटिलता होती है जो पार्स की गई स्ट्रिंग के आकार में घन होती है।

औपचारिक रूप से, सभी कांटैक्स्ट फ्री लैंग्वेज का सेट पुशडाउन ऑटोमेटा (पीडीए) द्वारा स्वीकृत लैंग्वेजेस के सेट के समान है। कांटैक्स्ट फ्री लैंग्वेज के लिए पार्सर एल्गोरिदम में CYK एल्गोरिदम और अर्ली पार्सर या अर्ली CYK एल्गोरिथ्म उपस्थित होती हैं।

कांटैक्स्ट फ्री लैंग्वेज का विशेष उपवर्ग नियतात्मक कांटैक्स्ट फ्री लैंग्वेजएं हैं, जिन्हें नियतात्मक पुशडाउन ऑटोमेटा द्वारा स्वीकृत लैंग्वेजेस के सेट के रूप में परिभाषित किया गया है, और एलआर पार्सर या एलआर (के) पार्सर द्वारा पार्स किया जा सकता है।^[4]

व्याकरण और पार्सर के वैकल्पिक दृष्टिकोण के रूप में अभिव्यक्ति व्याकरण को पार्स करना भी देखें।

विवृत गुण

कांटैक्स्ट फ्री लैंग्वेज का वर्ग निम्नलिखित परिचालनों के अनुसार विवृत (गणित) है। अर्थात्, यदि L और पी कांटैक्स्ट फ्री लैंग्वेजएँ हैं, तो निम्नलिखित लैंग्वेजएँ भी संदर्भ-मुक्त हैं:

संघ (सेट सिद्धांत) $L\cup P$ जिसमें L और P का संबंध हैं।^[5]
L का व्युत्क्रम होता हैं^[6]
संयोजन $L\cdot P$ जिसमें L और P का संबंध होता हैं।^[5]
क्लेन स्टार $L^{*}$ L का हैं।^[5]
छवि $\varphi (L)$ स्ट्रिंग ऑपरेशंस स्ट्रिंग होमोमोर्फिज्म के अनुसार L का $\varphi$ हैं।^[7]
छवि $\varphi ^{-1}(L)$ स्ट्रिंग ऑपरेशंस स्ट्रिंग होमोमोर्फिज्म के अनुसार L का $\varphi ^{-1}$ हैं।^[8]
वृत्ताकार परिवर्तन L (लैंग्वेज) के अनुप्रयोग $\{vu:uv\in L\}$ ) हैं।^[9]
L का उपसर्ग समापन (L से स्ट्रिंग के सभी उपसर्ग कंप्यूटर विज्ञान) का सेट हैं।^[10]
औपचारिक लैंग्वेज का भागफल L/R का L द्वारा नियमित लैंग्वेज R हैं।^[11]

प्रतिच्छेदन, पूरक और अंतर के अंतर्गत असंबद्धता

कांटैक्स्ट फ्री लैंग्वेजएँ प्रतिच्छेदन के अंतर्गत विवृत नहीं होती हैं। इसे लैंग्वेजेस को $A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}$ और $B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}$ से लेकर देखा जा सकता है, जो दोनों से संदर्भ-मुक्त हैं।^{[note 3]} उनका प्रतिच्छेदन $A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}$ है, जिसे कांटैक्स्ट फ्री लैंग्वेज के लिए पंपिंग लेम्मा द्वारा गैर-संदर्भ-मुक्त दिखाया जा सकता है। इसके परिणामस्वरूप कांटैक्स्ट फ्री लैंग्वेज को पूरकता के अनुसार विवृत नहीं किया जा सकता है, क्योंकि किसी भी लैंग्वेज A और B के लिए, उनके प्रतिच्छेदन को संघ और पूरक $A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}$ द्वारा व्यक्त किया जा सकता है। इस प्रकार विशेष रूप से, कांटैक्स्ट फ्री लैंग्वेज को अंतर के अंतर्गत विवृत नहीं किया जा सकता है, क्योंकि पूरक को अंतर ${\overline {L}}=\Sigma ^{*}\setminus L$ द्वारा व्यक्त किया जा सकता है।^[12]

चूंकि, यदि L कांटैक्स्ट फ्री लैंग्वेज है और D नियमित लैंग्वेज है तो दोनों का प्रतिच्छेदन $L\cap D$ होता है, और उनका अंतर $L\setminus D$ कांटैक्स्ट फ्री लैंग्वेजएँ हैं।^[13]

निर्णायकता

औपचारिक लैंग्वेज सिद्धांत में, नियमित लैंग्वेजेस के बारे में प्रश्न आमतौर पर निर्णय लेने योग्य होते हैं, अपितु कांटैक्स्ट फ्री लैंग्वेज के बारे में अक्सर नहीं होते हैं। यह तय करने योग्य है कि क्या ऐसी लैंग्वेज सीमित है, अपितु यह नहीं कि क्या इसमें हर संभव स्ट्रिंग उपस्थित होती है, नियमित है, इस प्रकार असंदिग्ध है, या अलग व्याकरण वाली लैंग्वेज के बराबर है।

निम्नलिखित समस्याएँ मनमाने ढंग से दिए गए कांटैक्स्ट फ्री ग्रामर A और B के लिए अनिर्णीत समस्या हैं:

समतुल्यता: $L(A)=L(B)$ ? है।^[14]
असंगति: $L(A)\cap L(B)=\emptyset$ ? है। ^[15] चूंकि इस प्रकार कांटैक्स्ट फ्री लैंग्वेज और नियमित लैंग्वेज का प्रतिच्छेदन संदर्भ-मुक्त होता है,^[16]^[17] इसलिए समस्या का वह प्रकार जहां B नियमित व्याकरण है, इसका निर्णय योग्य है जिसके लिए नीचे शून्यता को देख सकते हैं।
नियंत्रण: $L(A)\subseteq L(B)$ ? है।^[18] इसके आधार पर पुनः इस समस्या का वह प्रकार जहां B नियमित व्याकरण है, निर्णय योग्य है, जबकि जहां A नियमित है वह सामान्यतः नहीं है।^[19]
सार्वभौमिकता: $L(A)=\Sigma ^{*}$ ? है।^[20]
नियमितता: $L(A)$ नियमित लैंग्वेज? है^[21]
अस्पष्टता: $L(A)$ अस्पष्ट? प्रत्येक व्याकरण के लिए है। ^[22]

मनमानी कांटैक्स्ट फ्री लैंग्वेज के लिए निम्नलिखित समस्याएं निर्णय योग्य हैं:

शून्यता: कांटैक्स्ट फ्री ग्रामर A दिया गया है $L(A)=\emptyset$ ?^[23]
परिमितता: कांटैक्स्ट फ्री ग्रामर A दिया गया है $L(A)$ परिमित?^[24]
सदस्यता: कांटैक्स्ट फ्री ग्रामर जी, और शब्द दिया गया $w$ , $w\in L(G)$ ? करता है, इसके आधार पर सदस्यता समस्या के लिए कुशल बहुपद-समय एल्गोरिदम CYK एल्गोरिदम और इस प्रकार अर्ली पार्सर या अर्ली की एल्गोरिदम हैं।

होपक्रॉफ्ट, मोटवानी, उल्मन (2003) के अनुसार,^[25] येहोशुआ बार-हिलेल या बार-हिलेल, पर्ल्स और शमीर के 1961 के पेपर में कांटैक्स्ट फ्री लैंग्वेज के कई मौलिक समापन और (अन)निर्णय गुणों को दिखाया गया था।^[26]

ऐसी लैंग्वेजएँ जो संदर्भ-मुक्त नहीं हैं

सेट $\{a^{n}b^{n}c^{n}d^{n}|n>0\}$ संदर्भ-संवेदनशील लैंग्वेज है, अपितु इस लैंग्वेज को उत्पन्न करने वाला कोई कांटैक्स्ट फ्री ग्रामर सम्मिलित नहीं है।^[27] इसलिए संदर्भ-संवेदनशील लैंग्वेजएँ सम्मिलित हैं, जो इस प्रकार संदर्भ-मुक्त नहीं हैं। यह प्रमाणित करने के लिए कि कोई दी गई लैंग्वेज संदर्भ-मुक्त नहीं है, कोई कांटैक्स्ट फ्री लैंग्वेज के लिए पंपिंग लेम्मा का उपयोग कर सकता है,^[26] या कई अन्य विधियाँ, जैसे ओग्डेन की लेम्मा या पारिख की प्रमेय का उपयोग करते हैं।^[28]

↑ meaning of $\delta$ 's arguments and results: $\delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )$
↑ In Valiant's paper, O(n^2.81) was the then-best known upper bound. See Matrix multiplication#Computational complexity for bound improvements since then.
↑ A context-free grammar for the language A is given by the following production rules, taking S as the start symbol: S → Sc | aTb | ε; T → aTb | ε. The grammar for B is analogous.

संदर्भ

↑ Hopcroft & Ullman 1979, p. 100, Theorem 4.7.
↑ Valiant, Leslie G. (April 1975). "घन समय से भी कम समय में सामान्य संदर्भ-मुक्त पहचान". Journal of Computer and System Sciences. 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8.
↑ Lee, Lillian (January 2002). "तेज़ संदर्भ-मुक्त व्याकरण पार्सिंग के लिए तेज़ बूलियन मैट्रिक्स गुणन की आवश्यकता होती है" (PDF). J ACM. 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242. S2CID 1243491. Archived (PDF) from the original on 2003-04-27.
↑ Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
↑ ^5.0 ^5.1 ^5.2 Hopcroft & Ullman 1979, p. 131, Corollary of Theorem 6.1.
↑ Hopcroft & Ullman 1979, p. 142, Exercise 6.4d.
↑ Hopcroft & Ullman 1979, p. 131-132, Corollary of Theorem 6.2.
↑ Hopcroft & Ullman 1979, p. 132, Theorem 6.3.
↑ Hopcroft & Ullman 1979, p. 142-144, Exercise 6.4c.
↑ Hopcroft & Ullman 1979, p. 142, Exercise 6.4b.
↑ Hopcroft & Ullman 1979, p. 142, Exercise 6.4a.
↑ Stephen Scheinberg (1960). "संदर्भ मुक्त भाषाओं के बूलियन गुणों पर ध्यान दें" (PDF). Information and Control. 3 (4): 372–375. doi:10.1016/s0019-9958(60)90965-7. Archived (PDF) from the original on 2018-11-26.
↑ Beigel, Richard; Gasarch, William. "A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's" (PDF). University of Maryland Department of Computer Science. Archived (PDF) from the original on 2014-12-12. Retrieved June 6, 2020.
↑ Hopcroft & Ullman 1979, p. 203, Theorem 8.12(1).
↑ Hopcroft & Ullman 1979, p. 202, Theorem 8.10.
↑ Salomaa (1973), p. 59, Theorem 6.7
↑ Hopcroft & Ullman 1979, p. 135, Theorem 6.5.
↑ Hopcroft & Ullman 1979, p. 203, Theorem 8.12(2).
↑ Hopcroft & Ullman 1979, p. 203, Theorem 8.12(4).
↑ Hopcroft & Ullman 1979, p. 203, Theorem 8.11.
↑ Hopcroft & Ullman 1979, p. 205, Theorem 8.15.
↑ Hopcroft & Ullman 1979, p. 206, Theorem 8.16.
↑ Hopcroft & Ullman 1979, p. 137, Theorem 6.6(a).
↑ Hopcroft & Ullman 1979, p. 137, Theorem 6.6(b).
↑ John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison Wesley. Here: Sect.7.6, p.304, and Sect.9.7, p.411
↑ ^26.0 ^26.1 Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). "सरल वाक्यांश-संरचना व्याकरण के औपचारिक गुणों पर". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung. 14 (2): 143–172.
↑ Hopcroft & Ullman 1979.
↑ "How to prove that a language is not context-free?".

उद्धृत कार्य

Hopcroft, John E.; Ullman, Jeffrey D. (1979). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय (1st ed.). Addison-Wesley. ISBN 9780201029888.
Salomaa, Arto (1973). औपचारिक भाषाएँ. ACM Monograph Series.

अग्रिम पठन

Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Context-Free Languages and Push-Down Automata". In G. Rozenberg; A. Salomaa (eds.). Handbook of Formal Languages (PDF). Vol. 1. Springer-Verlag. pp. 111–174. Archived (PDF) from the original on 2011-05-16.
Ginsburg, Seymour (1966). The Mathematical Theory of Context-Free Languages. New York, NY, USA: McGraw-Hill.
Sipser, Michael (1997). "2: Context-Free Languages". Introduction to the Theory of Computation. PWS Publishing. pp. 91–122. ISBN 0-534-94728-X.

[1] $\delta$ 's arguments and results: $\delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )$

[4] In Valiant's paper, O(n^2.81) was the then-best known upper bound. See Matrix multiplication#Computational complexity for bound improvements since then.

[14] A context-free grammar for the language A is given by the following production rules, taking S as the start symbol: S → Sc | aTb | ε; T → aTb | ε. The grammar for B is analogous.

[FOOTNOTEHopcroftUllman1979100Theorem_4.7-2] Hopcroft & Ullman 1979, p. 100, Theorem 4.7.

[3] Valiant, Leslie G. (April 1975). "घन समय से भी कम समय में सामान्य संदर्भ-मुक्त पहचान". Journal of Computer and System Sciences. 10 (2): 308–315. doi:10.1016/s0022-0000(75)80046-8.

[5] Lee, Lillian (January 2002). "तेज़ संदर्भ-मुक्त व्याकरण पार्सिंग के लिए तेज़ बूलियन मैट्रिक्स गुणन की आवश्यकता होती है" (PDF). J ACM. 49 (1): 1–15. arXiv:cs/0112018. doi:10.1145/505241.505242. S2CID 1243491. Archived (PDF) from the original on 2003-04-27.

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

[FOOTNOTEHopcroftUllman1979131Corollary_of_Theorem_6.1-7] 5.0 ^5.1 ^5.2 Hopcroft & Ullman 1979, p. 131, Corollary of Theorem 6.1.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4d-8] Hopcroft & Ullman 1979, p. 142, Exercise 6.4d.

[FOOTNOTEHopcroftUllman1979131-132Corollary_of_Theorem_6.2-9] Hopcroft & Ullman 1979, p. 131-132, Corollary of Theorem 6.2.

[FOOTNOTEHopcroftUllman1979132Theorem_6.3-10] Hopcroft & Ullman 1979, p. 132, Theorem 6.3.

[FOOTNOTEHopcroftUllman1979142-144Exercise_6.4c-11] Hopcroft & Ullman 1979, p. 142-144, Exercise 6.4c.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4b-12] Hopcroft & Ullman 1979, p. 142, Exercise 6.4b.

[FOOTNOTEHopcroftUllman1979142Exercise_6.4a-13] Hopcroft & Ullman 1979, p. 142, Exercise 6.4a.

[Scheinberg.1960-15] Stephen Scheinberg (1960). "संदर्भ मुक्त भाषाओं के बूलियन गुणों पर ध्यान दें" (PDF). Information and Control. 3 (4): 372–375. doi:10.1016/s0019-9958(60)90965-7. Archived (PDF) from the original on 2018-11-26.

[16] Beigel, Richard; Gasarch, William. "A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's" (PDF). University of Maryland Department of Computer Science. Archived (PDF) from the original on 2014-12-12. Retrieved June 6, 2020.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(1)-17] Hopcroft & Ullman 1979, p. 203, Theorem 8.12(1).

[FOOTNOTEHopcroftUllman1979202Theorem_8.10-18] Hopcroft & Ullman 1979, p. 202, Theorem 8.10.

[19] Salomaa (1973), p. 59, Theorem 6.7

[FOOTNOTEHopcroftUllman1979135Theorem_6.5-20] Hopcroft & Ullman 1979, p. 135, Theorem 6.5.

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(2)-21] Hopcroft & Ullman 1979, p. 203, Theorem 8.12(2).

[FOOTNOTEHopcroftUllman1979203Theorem_8.12(4)-22] Hopcroft & Ullman 1979, p. 203, Theorem 8.12(4).

[FOOTNOTEHopcroftUllman1979203Theorem_8.11-23] Hopcroft & Ullman 1979, p. 203, Theorem 8.11.

[FOOTNOTEHopcroftUllman1979205Theorem_8.15-24] Hopcroft & Ullman 1979, p. 205, Theorem 8.15.

[FOOTNOTEHopcroftUllman1979206Theorem_8.16-25] Hopcroft & Ullman 1979, p. 206, Theorem 8.16.

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(a)-26] Hopcroft & Ullman 1979, p. 137, Theorem 6.6(a).

[FOOTNOTEHopcroftUllman1979137Theorem_6.6(b)-27] Hopcroft & Ullman 1979, p. 137, Theorem 6.6(b).

[28] John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2003). ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय. Addison Wesley. Here: Sect.7.6, p.304, and Sect.9.7, p.411

[Bar-Hillel.Perles.Shamir.1961-29] 26.0 ^26.1 Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). "सरल वाक्यांश-संरचना व्याकरण के औपचारिक गुणों पर". Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung. 14 (2): 143–172.

[FOOTNOTEHopcroftUllman1979-30] Hopcroft & Ullman 1979.

[31] "How to prove that a language is not context-free?".

[note 1]

[1]

[2]

[note 2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[note 3]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

@@ Line 1: / Line 1: @@
-[[औपचारिक भाषा]] सिद्धांत में, संदर्भ-मुक्त भाषा (सीएफएल) [[संदर्भ-मुक्त व्याकरण]] (सीएफजी) द्वारा उत्पन्न औपचारिक भाषा है।
+[[औपचारिक भाषा|औपचारिक लैंग्वेज]] के सिद्धांत में, कांटैक्स्ट फ्री लैंग्वेज (सीएफएल) [[संदर्भ-मुक्त व्याकरण|कांटैक्स्ट फ्री ग्रामर]] (सीएफजी) द्वारा उत्पन्न होने वाली औपचारिक लैंग्वेज है।
-[[प्रोग्रामिंग भाषा]]ओं में संदर्भ-मुक्त भाषाओं के कई अनुप्रयोग होते हैं, विशेष रूप से, अधिकांश अंकगणितीय अभिव्यक्तियाँ संदर्भ-मुक्त व्याकरणों द्वारा उत्पन्न होती हैं।
+[[प्रोग्रामिंग भाषा|प्रोग्रामिंग लैंग्वेज]]  में कांटैक्स्ट फ्री लैंग्वेज के कई अनुप्रयोग होते हैं, विशेष रूप से अधिकांश अंकगणितीय अभिव्यक्तियाँ कांटैक्स्ट फ्री ग्रामर द्वारा उत्पन्न होती हैं।
 ==पृष्ठभूमि==
-===संदर्भ-मुक्त व्याकरण===
+===कांटैक्स्ट फ्री ग्रामर===
-विभिन्न संदर्भ-मुक्त व्याकरण ही संदर्भ-मुक्त भाषा उत्पन्न कर सकते हैं। भाषा का वर्णन करने वाले कई व्याकरणों की तुलना करके भाषा के आंतरिक गुणों को किसी विशेष व्याकरण के बाहरी गुणों से अलग किया जा सकता है।
+विभिन्न कांटैक्स्ट फ्री ग्रामर ही कांटैक्स्ट फ्री लैंग्वेज उत्पन्न कर सकते हैं। इस प्रकार की लैंग्वेज का वर्णन करने वाले कई व्याकरणों की तुलना करके लैंग्वेज के आंतरिक गुणों को किसी विशेष व्याकरण के बाहरी गुणों से अलग किया जा सकता है।
 ===ऑटोमेटा===
-सभी संदर्भ-मुक्त भाषाओं का सेट [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकृत भाषाओं के सेट के समान है, जो इन भाषाओं को पार्सिंग के लिए उत्तरदायी बनाता है। इसके अलावा, किसी दिए गए सीएफजी के लिए, व्याकरण (और इस प्रकार संबंधित भाषा) के लिए पुशडाउन ऑटोमेटन का उत्पादन करने का सीधा तरीका है, हालांकि दूसरे तरीके से जाना (एक ऑटोमेटन दिए गए व्याकरण का निर्माण करना) उतना सीधा नहीं है।
+सभी कांटैक्स्ट फ्री लैंग्वेज का सेट [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकृत लैंग्वेजेस के सेट के समान है, जो इन लैंग्वेजेस को पार्सिंग के लिए उत्तरदायी बनाता है। इसके अतिरिक्त किसी दिए गए सीएफजी के लिए, व्याकरण और इस प्रकार संबंधित लैंग्वेज के लिए पुशडाउन ऑटोमेटा का उत्पादन करने की सीधा विधि है, चूंकि दूसरे तरीके से जाना एक ऑटोमेटा दिए गए व्याकरण का निर्माण करना हैं जो उतना सरल नहीं है।
 ==उदाहरण==
-संदर्भ-मुक्त भाषा का उदाहरण है <math>L = \{a^nb^n:n\geq1\}</math>, सभी गैर-रिक्त सम-लंबाई वाले तारों की भाषा, जिनके पूरे पहले भाग हैं {{mvar|a}}'s, और जिसके पूरे दूसरे भाग हैं {{mvar|b}}'एस। {{mvar|L}} व्याकरण द्वारा उत्पन्न होता है <math>S\to aSb ~|~ ab</math>.
+<math>L = \{a^nb^n:n\geq1\}</math> कांटैक्स्ट फ्री लैंग्वेज का उदाहरण है, जिसमें सभी गैर-रिक्त सम-लंबाई वाले तारों की लैंग्वेज, जिनके पूरे {{mvar|a}}'s का यह पहला भाग हैं, और जिसके पूरे दूसरे भाग {{mvar|b}}'एस हैं। यहाँ पर {{mvar|L}} व्याकरण द्वारा <math>S\to aSb ~|~ ab</math> उत्पन्न होता है,
-यह भाषा [[नियमित भाषा]] नहीं है.
-इसे पुशडाउन ऑटोमेटन#औपचारिक परिभाषा द्वारा स्वीकार किया जाता है <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\})</math> कहाँ <math>\delta</math> को इस प्रकार परिभाषित किया गया है:<ref group="note">meaning of <math>\delta</math>'s arguments and results: <math>\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})</math></ref>
+यह लैंग्वेज [[नियमित भाषा|रेगुलर लैंग्वेज]] नहीं है, इसे पुशडाउन ऑटोमेटा के आधार पर औपचारिक को-लैंग्वेज द्वारा स्वीकार किया जाता है, जिसके आधार पर <math>M=(\{q_0,q_1,q_f\}, \{a,b\}, \{a,z\}, \delta, q_0, z, \{q_f\})</math> के समान रखा जाता हैं, जहाँ <math>\delta</math> को इस प्रकार परिभाषित किया गया है:<ref group="note">meaning of <math>\delta</math>'s arguments and results: <math>\delta(\mathrm{state}_1, \mathrm{read}, \mathrm{pop}) = (\mathrm{state}_2, \mathrm{push})</math></ref>
 :<math>\begin{align}
 \delta(q_0, a, z) &= (q_0, az) \\
@@ Line 25: / Line 25: @@
 \delta(q_1, \varepsilon, z) &= (q_f, \varepsilon)
 \end{align}</math>
-असंदिग्ध सीएफएल सभी सीएफएल का उचित उपसमूह हैं: [[स्वाभाविक रूप से अस्पष्ट भाषा]] सीएफएल हैं। स्वाभाविक रूप से अस्पष्ट सीएफएल का उदाहरण संघ है <math>\{a^n b^m c^m d^n | n, m > 0\}</math> साथ <math>\{a^n b^n c^m d^m | n, m > 0\}</math>. यह सेट संदर्भ-मुक्त है, क्योंकि दो संदर्भ-मुक्त भाषाओं का मिलन हमेशा संदर्भ-मुक्त होता है। लेकिन (गैर-संदर्भ-मुक्त) उपसमुच्चय में स्ट्रिंग्स को स्पष्ट रूप से पार्स करने का कोई तरीका नहीं है <math>\{a^n b^n c^n d^n | n > 0\}</math> जो इन दोनों भाषाओं का प्रतिच्छेदन है।{{sfn|Hopcroft|Ullman|1979|p=100|loc=Theorem 4.7}}
+असंदिग्ध सीएफएल सभी सीएफएल का उचित उपसमूह हैं: इसके आधार पर [[स्वाभाविक रूप से अस्पष्ट भाषा|स्वाभाविक रूप से अस्पष्ट लैंग्वेज]] सीएफएल हैं। इसका स्वाभाविक रूप से अस्पष्ट सीएफएल का उदाहरण संघ <math>\{a^n b^m c^m d^n | n, m > 0\}</math> साथ <math>\{a^n b^n c^m d^m | n, m > 0\}</math> है, यह मुख्य रूप से सेट संदर्भ-मुक्त है, क्योंकि दो कांटैक्स्ट फ्री लैंग्वेज का मिलन सदैव संदर्भ-मुक्त होता है। अपितु (गैर-संदर्भ-मुक्त) उपसमुच्चय में स्ट्रिंग्स <math>\{a^n b^n c^n d^n | n > 0\}</math> को स्पष्ट रूप से पार्स करने की कोई विधि नहीं है, जो इन दोनों लैंग्वेजेस का प्रतिच्छेदन करती है।{{sfn|Hopcroft|Ullman|1979|p=100|loc=Theorem 4.7}}
-===[[डाइक भाषा]]===
+===[[डाइक भाषा|डाइक लैंग्वेज]]===
-डाइक भाषा व्याकरण द्वारा उत्पन्न होती है <math>S\to SS ~|~ (S) ~|~ \varepsilon</math>.
+डाइक लैंग्वेज व्याकरण <math>S\to SS ~|~ (S) ~|~ \varepsilon</math> द्वारा उत्पन्न होती है।
 ==गुण==
-===संदर्भ-मुक्त पार्सिंग===
+===कांटैक्स्ट फ्री पार्सिंग===
-{{main|Parsing}}
+{{main|पार्सिंग}}
-भाषा की संदर्भ-मुक्त प्रकृति पुशडाउन ऑटोमेटन के साथ पार्स करना आसान बनाती है।
+लैंग्वेज की संदर्भ-मुक्त प्रकृति पुशडाउन ऑटोमेटा के साथ पार्स करना सरल बनाती है।
-[[सदस्यता समस्या]] का उदाहरण निर्धारित करना; यानी स्ट्रिंग दी गई है <math>w</math>, पता लगाएं कि क्या <math>w \in L(G)</math> कहाँ <math>L</math> किसी दिए गए व्याकरण द्वारा उत्पन्न भाषा है <math>G</math>; मान्यता के रूप में भी जाना जाता है। [[चॉम्स्की सामान्य रूप]] व्याकरण के लिए संदर्भ-मुक्त मान्यता लेस्ली वैलिएंट द्वारा दिखाई गई थी|लेस्ली जी. वैलिएंट को बूलियन [[मैट्रिक्स गुणन]] के लिए कम किया जा सकता है, इस प्रकार इसकी जटिलता बिग ओ नोटेशन की ऊपरी सीमा को विरासत में मिली है।<sup>2.3728596</sup>).<ref>{{cite journal |first=Leslie G. |last=Valiant |title=घन समय से भी कम समय में सामान्य संदर्भ-मुक्त पहचान|journal=Journal of Computer and System Sciences |date=April 1975 |volume=10 |number=2 |pages=308–315 |doi=10.1016/s0022-0000(75)80046-8 |doi-access=free }}</ref><ref group=note>In Valiant's paper, ''O''(''n''<sup>2.81</sup>) was the then-best known upper bound. See [[Matrix multiplication#Computational complexity]] for bound improvements since then.</ref>
+[[सदस्यता समस्या]] का उदाहरण निर्धारित करना अर्ताथ स्ट्रिंग <math>w</math> दी गई है, जहाँ पता लगाया जाता हैं कि क्या <math>w \in L(G)</math> के समान हैं। जहाँ <math>L</math> किसी दिए गए व्याकरण द्वारा उत्पन्न होने वाले <math>G</math> लैंग्वेज के समान है, इसे मान्यता के रूप में भी जाना जाता है। इसके आधार पर [[चॉम्स्की सामान्य रूप]] व्याकरण के लिए संदर्भ-मुक्त मान्यता लेस्ली वैलिएंट द्वारा दिखाई गई थी। इस प्रकार लेस्ली जी. वैलिएंट को बूलियन [[मैट्रिक्स गुणन|आव्यूह गुणन]] के लिए कम किया जा सकता है, इस प्रकार इसकी जटिलता बिग ओ नोटेशन की ऊपरी सीमा को विरासत में मिली है।<sup>2.3728596</sup>).<ref>{{cite journal |first=Leslie G. |last=Valiant |title=घन समय से भी कम समय में सामान्य संदर्भ-मुक्त पहचान|journal=Journal of Computer and System Sciences |date=April 1975 |volume=10 |number=2 |pages=308–315 |doi=10.1016/s0022-0000(75)80046-8 |doi-access=free }}</ref><ref group=note>In Valiant's paper, ''O''(''n''<sup>2.81</sup>) was the then-best known upper bound. See [[Matrix multiplication#Computational complexity]] for bound improvements since then.</ref>
-इसके विपरीत, [[लिलियन ली (कंप्यूटर वैज्ञानिक)]] ने O(n) दिखाया है<sup>3−ε</sup>) बूलियन मैट्रिक्स गुणन को O(n) तक कम किया जा सकता है<sup>3−3ε</sup>) सीएफजी पार्सिंग, इस प्रकार बाद के लिए कुछ प्रकार की निचली सीमा स्थापित करता है।<ref>{{cite journal |first=Lillian |last=Lee |author-link=Lillian Lee (computer scientist) |title=तेज़ संदर्भ-मुक्त व्याकरण पार्सिंग के लिए तेज़ बूलियन मैट्रिक्स गुणन की आवश्यकता होती है|journal=J ACM |date=January 2002 |volume=49 |number=1 |pages=1–15 |url=http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-url=https://web.archive.org/web/20030427152836/http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-date=2003-04-27 |url-status=live |doi=10.1145/505241.505242 |arxiv=cs/0112018|s2cid=1243491 }}</ref>
-संदर्भ-मुक्त भाषाओं के व्यावहारिक उपयोग के लिए व्युत्पत्ति वृक्ष तैयार करने की भी आवश्यकता होती है जो उस संरचना को प्रदर्शित करता है जिसे व्याकरण दिए गए स्ट्रिंग के साथ जोड़ता है। इस पेड़ के उत्पादन की प्रक्रिया को [[ पदच्छेद |पदच्छेद]] कहा जाता है। ज्ञात पार्सर्स में समय जटिलता होती है जो पार्स की गई स्ट्रिंग के आकार में घन होती है।
-औपचारिक रूप से, सभी संदर्भ-मुक्त भाषाओं का सेट पुशडाउन ऑटोमेटा (पीडीए) द्वारा स्वीकृत भाषाओं के सेट के समान है। संदर्भ-मुक्त भाषाओं के लिए पार्सर एल्गोरिदम में CYK एल्गोरिदम और अर्ली पार्सर|अर्ली [[CYK एल्गोरिथ्म]] शामिल हैं।
+इसके विपरीत, [[लिलियन ली (कंप्यूटर वैज्ञानिक)]] ने O(n)<sup>3−ε</sup> दिखाया है, जिसके आधार पर बूलियन आव्यूह गुणन को O(n)<sup>3−3ε</sup> तक कम किया जा सकता है, इसके फल्स्वरूप सीएफजी पार्सिंग के लिए इस प्रकार बाद के लिए कुछ प्रकार की निचली सीमा स्थापित करता है।<ref>{{cite journal |first=Lillian |last=Lee |author-link=Lillian Lee (computer scientist) |title=तेज़ संदर्भ-मुक्त व्याकरण पार्सिंग के लिए तेज़ बूलियन मैट्रिक्स गुणन की आवश्यकता होती है|journal=J ACM |date=January 2002 |volume=49 |number=1 |pages=1–15 |url=http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-url=https://web.archive.org/web/20030427152836/http://www.cs.cornell.edu/home/llee/papers/bmmcfl-jacm.pdf |archive-date=2003-04-27 |url-status=live |doi=10.1145/505241.505242 |arxiv=cs/0112018|s2cid=1243491 }}</ref>
+कांटैक्स्ट फ्री लैंग्वेज के व्यावहारिक उपयोग के लिए इनहैरिटेड ट्री तैयार करने की भी आवश्यकता होती है, जो उस संरचना को प्रदर्शित करता है जिसे व्याकरण दिए गए स्ट्रिंग के साथ जोड़ता है। इस ट्री के उत्पादन की प्रक्रिया को [[ पदच्छेद |पदच्छेद]] कहा जाता है। इससे ज्ञात होने वाले पार्सर्स में समय जटिलता होती है जो पार्स की गई स्ट्रिंग के आकार में घन होती है।
+औपचारिक रूप से, सभी कांटैक्स्ट फ्री लैंग्वेज का सेट पुशडाउन ऑटोमेटा (पीडीए) द्वारा स्वीकृत लैंग्वेजेस के सेट के समान है। कांटैक्स्ट फ्री लैंग्वेज के लिए पार्सर एल्गोरिदम में CYK एल्गोरिदम और अर्ली पार्सर या अर्ली [[CYK एल्गोरिथ्म]] उपस्थित होती हैं।
+कांटैक्स्ट फ्री लैंग्वेज का विशेष उपवर्ग नियतात्मक कांटैक्स्ट फ्री लैंग्वेजएं हैं, जिन्हें [[नियतात्मक पुशडाउन ऑटोमेटन|नियतात्मक पुशडाउन ऑटोमेटा]] द्वारा स्वीकृत लैंग्वेजेस के सेट के रूप में परिभाषित किया गया है, और [[एलआर पार्सर]] या एलआर (के) पार्सर द्वारा पार्स किया जा सकता है।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = 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>
-संदर्भ-मुक्त भाषाओं का विशेष उपवर्ग नियतात्मक संदर्भ-मुक्त भाषाएं हैं जिन्हें [[नियतात्मक पुशडाउन ऑटोमेटन]] द्वारा स्वीकृत भाषाओं के सेट के रूप में परिभाषित किया गया है और [[एलआर पार्सर]] | एलआर (के) पार्सर द्वारा पार्स किया जा सकता है।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | author-link = 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>
 व्याकरण और पार्सर के वैकल्पिक दृष्टिकोण के रूप में [[अभिव्यक्ति व्याकरण को पार्स करना]] भी देखें।
-===बंद गुण===
+===विवृत गुण===
-संदर्भ-मुक्त भाषाओं का वर्ग निम्नलिखित परिचालनों के तहत बंद (गणित) है। अर्थात्, यदि एल और पी संदर्भ-मुक्त भाषाएँ हैं, तो निम्नलिखित भाषाएँ भी संदर्भ-मुक्त हैं:
+कांटैक्स्ट फ्री लैंग्वेज का वर्ग निम्नलिखित परिचालनों के अनुसार विवृत (गणित) है। अर्थात्, यदि L और पी कांटैक्स्ट फ्री लैंग्वेजएँ हैं, तो निम्नलिखित लैंग्वेजएँ भी संदर्भ-मुक्त हैं:
-*[[संघ (सेट सिद्धांत)]] <math>L \cup P</math> एल और पी का{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
+*[[संघ (सेट सिद्धांत)]] <math>L \cup P</math> जिसमें L और P का संबंध हैं।{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
-*एल का उलटा होना{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4d}}
+*L का व्युत्क्रम होता हैं{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4d}}
-*संयोजन <math>L \cdot P</math> एल और पी का{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
+*संयोजन <math>L \cdot P</math> जिसमें L और P का संबंध होता हैं।{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
-*[[क्लेन स्टार]] <math>L^*</math> एल का{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
+*[[क्लेन स्टार]] <math>L^*</math> L का हैं।{{sfn|Hopcroft|Ullman|1979|p=131|loc=Corollary of Theorem 6.1}}
-*छवि <math>\varphi(L)</math> स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का <math>\varphi</math>{{sfn|Hopcroft|Ullman|1979|p=131-132|loc=Corollary of Theorem 6.2}}
+*छवि <math>\varphi(L)</math> स्ट्रिंग ऑपरेशंस स्ट्रिंग होमोमोर्फिज्म के अनुसार L का <math>\varphi</math> हैं।{{sfn|Hopcroft|Ullman|1979|p=131-132|loc=Corollary of Theorem 6.2}}
-*छवि <math>\varphi^{-1}(L)</math> स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का <math>\varphi^{-1}</math>{{sfn|Hopcroft|Ullman|1979|p=132|loc=Theorem 6.3}}
+*छवि <math>\varphi^{-1}(L)</math> स्ट्रिंग ऑपरेशंस स्ट्रिंग होमोमोर्फिज्म के अनुसार L का <math>\varphi^{-1}</math>हैं।{{sfn|Hopcroft|Ullman|1979|p=132|loc=Theorem 6.3}}
-*वृत्ताकार बदलाव#एल (भाषा) के अनुप्रयोग <math>\{vu : uv \in L \}</math>){{sfn|Hopcroft|Ullman|1979|p=142-144|loc=Exercise 6.4c}}
+*वृत्ताकार परिवर्तन L (लैंग्वेज) के अनुप्रयोग <math>\{vu : uv \in L \}</math>) हैं।{{sfn|Hopcroft|Ullman|1979|p=142-144|loc=Exercise 6.4c}}
-*एल का उपसर्ग समापन (एल से स्ट्रिंग के सभी [[उपसर्ग (कंप्यूटर विज्ञान)]] का सेट){{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4b}}
+*L का उपसर्ग समापन (L से स्ट्रिंग के सभी [[उपसर्ग (कंप्यूटर विज्ञान)|उपसर्ग कंप्यूटर विज्ञान)]] का सेट हैं।{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4b}}
-*[[औपचारिक भाषा का भागफल]] L/R का L द्वारा नियमित भाषा R{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4a}}
+*[[औपचारिक भाषा का भागफल|औपचारिक लैंग्वेज का भागफल]] L/R का L द्वारा नियमित लैंग्वेज R हैं।{{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4a}}
 ====प्रतिच्छेदन, पूरक और अंतर के अंतर्गत असंबद्धता====
-संदर्भ-मुक्त भाषाएँ प्रतिच्छेदन के अंतर्गत बंद नहीं होती हैं। इसे भाषाओं को लेकर देखा जा सकता है <math>A = \{a^n b^n c^m \mid m, n \geq 0 \}</math> और <math>B = \{a^m b^n c^n \mid m,n \geq 0\}</math>, जो दोनों संदर्भ-मुक्त हैं।<ref group=note>A context-free grammar for the language ''A'' is given by the following production rules, taking ''S'' as the start symbol: ''S'' → ''Sc'' | ''aTb'' | ''ε''; ''T'' → ''aTb'' | ''ε''. The grammar for ''B'' is analogous.</ref> उनका चौराहा है <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math>, जिसे संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा द्वारा गैर-संदर्भ-मुक्त दिखाया जा सकता है। परिणामस्वरूप, संदर्भ-मुक्त भाषाओं को पूरकता के तहत बंद नहीं किया जा सकता है, क्योंकि किसी भी भाषा ए और बी के लिए, उनके प्रतिच्छेदन को संघ और पूरक द्वारा व्यक्त किया जा सकता है: <math>A \cap B = \overline{\overline{A} \cup \overline{B}} </math>. विशेष रूप से, संदर्भ-मुक्त भाषा को अंतर के अंतर्गत बंद नहीं किया जा सकता है, क्योंकि पूरक को अंतर द्वारा व्यक्त किया जा सकता है: <math>\overline{L} = \Sigma^* \setminus L</math>.<ref name="Scheinberg.1960">{{cite journal | url=https://core.ac.uk/download/pdf/82210847.pdf |archive-url=https://web.archive.org/web/20181126005901/https://core.ac.uk/download/pdf/82210847.pdf |archive-date=2018-11-26 |url-status=live | author=Stephen Scheinberg | title=संदर्भ मुक्त भाषाओं के बूलियन गुणों पर ध्यान दें| journal=Information and Control | volume=3 | pages=372&ndash;375 | year=1960 | issue=4 | doi=10.1016/s0019-9958(60)90965-7| doi-access=free }}</ref>
+कांटैक्स्ट फ्री लैंग्वेजएँ प्रतिच्छेदन के अंतर्गत विवृत नहीं होती हैं। इसे लैंग्वेजेस को <math>A = \{a^n b^n c^m \mid m, n \geq 0 \}</math>  और <math>B = \{a^m b^n c^n \mid m,n \geq 0\}</math> से लेकर देखा जा सकता है, जो दोनों से संदर्भ-मुक्त हैं।<ref group=note>A context-free grammar for the language ''A'' is given by the following production rules, taking ''S'' as the start symbol: ''S'' → ''Sc'' | ''aTb'' | ''ε''; ''T'' → ''aTb'' | ''ε''. The grammar for ''B'' is analogous.</ref> उनका प्रतिच्छेदन <math>A \cap B = \{ a^n b^n c^n \mid n \geq 0\}</math> है, जिसे कांटैक्स्ट फ्री लैंग्वेज के लिए पंपिंग लेम्मा द्वारा गैर-संदर्भ-मुक्त दिखाया जा सकता है। इसके परिणामस्वरूप कांटैक्स्ट फ्री लैंग्वेज को पूरकता के अनुसार विवृत नहीं किया जा सकता है, क्योंकि किसी भी लैंग्वेज A और B के लिए, उनके प्रतिच्छेदन को संघ और पूरक <math>A \cap B = \overline{\overline{A} \cup \overline{B}} </math> द्वारा व्यक्त किया जा सकता है। इस प्रकार विशेष रूप से, कांटैक्स्ट फ्री लैंग्वेज को अंतर के अंतर्गत विवृत नहीं किया जा सकता है, क्योंकि पूरक को अंतर <math>\overline{L} = \Sigma^* \setminus L</math> द्वारा व्यक्त किया जा सकता है।<ref name="Scheinberg.1960">{{cite journal | url=https://core.ac.uk/download/pdf/82210847.pdf |archive-url=https://web.archive.org/web/20181126005901/https://core.ac.uk/download/pdf/82210847.pdf |archive-date=2018-11-26 |url-status=live | author=Stephen Scheinberg | title=संदर्भ मुक्त भाषाओं के बूलियन गुणों पर ध्यान दें| journal=Information and Control | volume=3 | pages=372&ndash;375 | year=1960 | issue=4 | doi=10.1016/s0019-9958(60)90965-7| doi-access=free }}</ref>
-हालाँकि, यदि L संदर्भ-मुक्त भाषा है और D नियमित भाषा है तो दोनों का प्रतिच्छेदन होता है <math>L\cap D</math> और उनका अंतर <math>L\setminus D</math> संदर्भ-मुक्त भाषाएँ हैं।<ref>{{Cite web|last1=Beigel|first1=Richard|last2=Gasarch|first2=William|title=A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's|url=http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-url=https://web.archive.org/web/20141212060332/http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-date=2014-12-12 |url-status=live|access-date=June 6, 2020|website=University of Maryland Department of Computer Science}}</ref>
+चूंकि, यदि L कांटैक्स्ट फ्री लैंग्वेज है और D नियमित लैंग्वेज है तो दोनों का प्रतिच्छेदन <math>L\cap D</math> होता है, और उनका अंतर <math>L\setminus D</math> कांटैक्स्ट फ्री लैंग्वेजएँ हैं।<ref>{{Cite web|last1=Beigel|first1=Richard|last2=Gasarch|first2=William|title=A Proof that if L = L1 ∩ L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's|url=http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-url=https://web.archive.org/web/20141212060332/http://www.cs.umd.edu/~gasarch/BLOGPAPERS/cfg.pdf |archive-date=2014-12-12 |url-status=live|access-date=June 6, 2020|website=University of Maryland Department of Computer Science}}</ref>
 ===निर्णायकता===
-औपचारिक भाषा सिद्धांत में, नियमित भाषाओं के बारे में प्रश्न आमतौर पर निर्णय लेने योग्य होते हैं, लेकिन संदर्भ-मुक्त भाषाओं के बारे में अक्सर नहीं होते हैं। यह तय करने योग्य है कि क्या ऐसी भाषा सीमित है, लेकिन यह नहीं कि क्या इसमें हर संभव स्ट्रिंग शामिल है, नियमित है, असंदिग्ध है, या अलग व्याकरण वाली भाषा के बराबर है।
+औपचारिक लैंग्वेज सिद्धांत में, नियमित लैंग्वेजेस के बारे में प्रश्न आमतौर पर निर्णय लेने योग्य होते हैं, अपितु कांटैक्स्ट फ्री लैंग्वेज के बारे में अक्सर नहीं होते हैं। यह तय करने योग्य है कि क्या ऐसी लैंग्वेज सीमित है, अपितु यह नहीं कि क्या इसमें हर संभव स्ट्रिंग उपस्थित होती है, नियमित है, इस प्रकार असंदिग्ध है, या अलग व्याकरण वाली लैंग्वेज के बराबर है।
-निम्नलिखित समस्याएँ मनमाने ढंग से दिए गए संदर्भ-मुक्त व्याकरण ए और बी के लिए [[अनिर्णीत समस्या]] हैं:
+निम्नलिखित समस्याएँ मनमाने ढंग से दिए गए कांटैक्स्ट फ्री ग्रामर A और B के लिए [[अनिर्णीत समस्या]] हैं:
-*समतुल्यता: है <math>L(A)=L(B)</math>?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(1)}}
+*समतुल्यता: <math>L(A)=L(B)</math>? है।{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(1)}}
-*असंगति: है <math>L(A) \cap L(B) = \emptyset </math> ?{{sfn|Hopcroft|Ullman|1979|p=202|loc=Theorem 8.10}} हालाँकि, संदर्भ-मुक्त भाषा और नियमित भाषा का प्रतिच्छेदन संदर्भ-मुक्त होता है,<ref>{{harvtxt|Salomaa|1973}}, p. 59, Theorem 6.7</ref>{{sfn|Hopcroft|Ullman|1979|p=135|loc=Theorem 6.5}} इसलिए समस्या का वह प्रकार जहां बी नियमित व्याकरण है, निर्णय योग्य है (नीचे शून्यता देखें)।
+*असंगति: <math>L(A) \cap L(B) = \emptyset </math> ? है। {{sfn|Hopcroft|Ullman|1979|p=202|loc=Theorem 8.10}} चूंकि इस प्रकार कांटैक्स्ट फ्री लैंग्वेज और नियमित लैंग्वेज का प्रतिच्छेदन संदर्भ-मुक्त होता है,<ref>{{harvtxt|Salomaa|1973}}, p. 59, Theorem 6.7</ref>{{sfn|Hopcroft|Ullman|1979|p=135|loc=Theorem 6.5}} इसलिए समस्या का वह प्रकार जहां B नियमित व्याकरण है, इसका निर्णय योग्य है जिसके लिए नीचे शून्यता को देख सकते हैं।
-*नियंत्रण: है <math>L(A) \subseteq L(B)</math> ?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(2)}} फिर, समस्या का वह प्रकार जहां बी नियमित व्याकरण है, निर्णय योग्य है, जबकि जहां ए नियमित है वह आम तौर पर नहीं है।{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(4)}}
+*नियंत्रण: <math>L(A) \subseteq L(B)</math> ? है।{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(2)}} इसके आधार पर पुनः इस समस्या का वह प्रकार जहां B नियमित व्याकरण है, निर्णय योग्य है, जबकि जहां A नियमित है वह सामान्यतः नहीं है।{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(4)}}
-*सार्वभौमिकता: है <math>L(A)=\Sigma^*</math>?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.11}}
+*सार्वभौमिकता: <math>L(A)=\Sigma^*</math>? है।{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.11}}
-*नियमितता: है <math>L(A)</math> नियमित भाषा?{{sfn|Hopcroft|Ullman|1979|p=205|loc=Theorem 8.15}}
+*नियमितता: <math>L(A)</math> नियमित लैंग्वेज? है{{sfn|Hopcroft|Ullman|1979|p=205|loc=Theorem 8.15}}
-*अस्पष्टता: प्रत्येक व्याकरण के लिए है <math>L(A)</math> अस्पष्ट?{{sfn|Hopcroft|Ullman|1979|p=206|loc=Theorem 8.16}}
+*अस्पष्टता: <math>L(A)</math> अस्पष्ट? प्रत्येक व्याकरण के लिए है। {{sfn|Hopcroft|Ullman|1979|p=206|loc=Theorem 8.16}}
-मनमानी संदर्भ-मुक्त भाषाओं के लिए निम्नलिखित समस्याएं निर्णय योग्य हैं:
+मनमानी कांटैक्स्ट फ्री लैंग्वेज के लिए निम्नलिखित समस्याएं निर्णय योग्य हैं:
-*शून्यता: संदर्भ-मुक्त व्याकरण ए दिया गया है <math>L(A) = \emptyset</math> ?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(a)}}
+*शून्यता: कांटैक्स्ट फ्री ग्रामर A दिया गया है <math>L(A) = \emptyset</math> ?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(a)}}
-*परिमितता: संदर्भ-मुक्त व्याकरण ए दिया गया है <math>L(A)</math> परिमित?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(b)}}
+*परिमितता: कांटैक्स्ट फ्री ग्रामर A दिया गया है <math>L(A)</math> परिमित?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(b)}}
-*सदस्यता: संदर्भ-मुक्त व्याकरण जी, और शब्द दिया गया <math>w</math>, करता है <math>w \in L(G)</math> ? सदस्यता समस्या के लिए कुशल बहुपद-समय एल्गोरिदम CYK एल्गोरिदम और अर्ली पार्सर|अर्ली का एल्गोरिदम हैं।
+*सदस्यता: कांटैक्स्ट फ्री ग्रामर जी, और शब्द दिया गया <math>w</math>,  <math>w \in L(G)</math> ? करता है, इसके आधार पर सदस्यता समस्या के लिए कुशल बहुपद-समय एल्गोरिदम CYK एल्गोरिदम और इस प्रकार अर्ली पार्सर या अर्ली की एल्गोरिदम हैं।
-होपक्रॉफ्ट, मोटवानी, उल्मन (2003) के अनुसार,<ref>{{cite book|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| year=2003| publisher=Addison Wesley}} Here: Sect.7.6, p.304, and Sect.9.7, p.411</ref> [[येहोशुआ बार-हिलेल]]|बार-हिलेल, पर्ल्स और शमीर के 1961 के पेपर में संदर्भ-मुक्त भाषाओं के कई मौलिक समापन और (अन)निर्णय गुणों को दिखाया गया था।<ref name="Bar-Hillel.Perles.Shamir.1961">{{cite journal|author1=Yehoshua Bar-Hillel |author2=Micha Asher Perles |author3=Eli Shamir | title=सरल वाक्यांश-संरचना व्याकरण के औपचारिक गुणों पर| journal=Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung| year=1961| volume=14| number=2| pages=143–172}}</ref>
+होपक्रॉफ्ट, मोटवानी, उल्मन (2003) के अनुसार,<ref>{{cite book|author1=John E. Hopcroft |author2=Rajeev Motwani |author3=Jeffrey D. Ullman | title=ऑटोमेटा सिद्धांत, भाषाएँ और संगणना का परिचय| year=2003| publisher=Addison Wesley}} Here: Sect.7.6, p.304, and Sect.9.7, p.411</ref> [[येहोशुआ बार-हिलेल]] या बार-हिलेल, पर्ल्स और शमीर के 1961 के पेपर में कांटैक्स्ट फ्री लैंग्वेज के कई मौलिक समापन और (अन)निर्णय गुणों को दिखाया गया था।<ref name="Bar-Hillel.Perles.Shamir.1961">{{cite journal|author1=Yehoshua Bar-Hillel |author2=Micha Asher Perles |author3=Eli Shamir | title=सरल वाक्यांश-संरचना व्याकरण के औपचारिक गुणों पर| journal=Zeitschrift für Phonetik, Sprachwissenschaft und Kommunikationsforschung| year=1961| volume=14| number=2| pages=143–172}}</ref>
-===ऐसी भाषाएँ जो संदर्भ-मुक्त नहीं हैं===
+===ऐसी लैंग्वेजएँ जो संदर्भ-मुक्त नहीं हैं===
-सेट <math>\{a^n b^n c^n d^n | n > 0\}</math> [[संदर्भ-संवेदनशील भाषा]] है, लेकिन इस भाषा को उत्पन्न करने वाला कोई संदर्भ-मुक्त व्याकरण मौजूद नहीं है।{{sfn|Hopcroft|Ullman|1979}} इसलिए संदर्भ-संवेदनशील भाषाएँ मौजूद हैं जो संदर्भ-मुक्त नहीं हैं। यह साबित करने के लिए कि कोई दी गई भाषा संदर्भ-मुक्त नहीं है, कोई संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा का उपयोग कर सकता है<ref name="Bar-Hillel.Perles.Shamir.1961"/>या कई अन्य विधियाँ, जैसे ओग्डेन की लेम्मा या पारिख की प्रमेय।<ref>{{cite web| url = https://cs.stackexchange.com/q/265| title = How to prove that a language is not context-free?}}</ref>
+सेट <math>\{a^n b^n c^n d^n | n > 0\}</math> [[संदर्भ-संवेदनशील भाषा|संदर्भ-संवेदनशील लैंग्वेज]] है, अपितु इस लैंग्वेज को उत्पन्न करने वाला कोई कांटैक्स्ट फ्री ग्रामर सम्मिलित नहीं है।{{sfn|Hopcroft|Ullman|1979}} इसलिए संदर्भ-संवेदनशील लैंग्वेजएँ सम्मिलित हैं, जो इस प्रकार संदर्भ-मुक्त नहीं हैं। यह प्रमाणित करने के लिए कि कोई दी गई लैंग्वेज संदर्भ-मुक्त नहीं है, कोई कांटैक्स्ट फ्री लैंग्वेज के लिए पंपिंग लेम्मा का उपयोग कर सकता है,<ref name="Bar-Hillel.Perles.Shamir.1961"/> या कई अन्य विधियाँ, जैसे ओग्डेन की लेम्मा या पारिख की प्रमेय का उपयोग करते हैं।<ref>{{cite web| url = https://cs.stackexchange.com/q/265| title = How to prove that a language is not context-free?}}</ref>
 ==टिप्पणियाँ==
 {{Reflist|group=note}}

Anonymous

Search

कांटैक्स्ट फ्री लैंग्वेज: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:36, 7 August 2023

Contents

पृष्ठभूमि

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

ऑटोमेटा

उदाहरण

डाइक लैंग्वेज

गुण

कांटैक्स्ट फ्री पार्सिंग

विवृत गुण

प्रतिच्छेदन, पूरक और अंतर के अंतर्गत असंबद्धता

निर्णायकता

ऐसी लैंग्वेजएँ जो संदर्भ-मुक्त नहीं हैं

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कांटैक्स्ट फ्री लैंग्वेज: Difference between revisions

Revision as of 23:36, 7 August 2023

पृष्ठभूमि

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

ऑटोमेटा

उदाहरण

डाइक लैंग्वेज

गुण

कांटैक्स्ट फ्री पार्सिंग

विवृत गुण

प्रतिच्छेदन, पूरक और अंतर के अंतर्गत असंबद्धता

निर्णायकता

ऐसी लैंग्वेजएँ जो संदर्भ-मुक्त नहीं हैं

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories