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

Revision as of 23:05, 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\cup P$ एल और पी का^[5]
एल का उलटा होना^[6]
संयोजन $L\cdot P$ एल और पी का^[5]
क्लेन स्टार $L^{*}$ एल का^[5]
छवि $\varphi (L)$ स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का $\varphi$ ^[7]
छवि $\varphi ^{-1}(L)$ स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का $\varphi ^{-1}$ ^[8]
वृत्ताकार बदलाव#एल (भाषा) के अनुप्रयोग $\{vu:uv\in L\}$ )^[9]
एल का उपसर्ग समापन (एल से स्ट्रिंग के सभी उपसर्ग (कंप्यूटर विज्ञान) का सेट)^[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\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}$ . विशेष रूप से, संदर्भ-मुक्त भाषा को अंतर के अंतर्गत बंद नहीं किया जा सकता है, क्योंकि पूरक को अंतर द्वारा व्यक्त किया जा सकता है: ${\overline {L}}=\Sigma ^{*}\setminus L$ .^[12] हालाँकि, यदि L संदर्भ-मुक्त भाषा है और D नियमित भाषा है तो दोनों का प्रतिच्छेदन होता है $L\cap D$ और उनका अंतर $L\setminus D$ संदर्भ-मुक्त भाषाएँ हैं।^[13]

निर्णायकता

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

निम्नलिखित समस्याएँ मनमाने ढंग से दिए गए संदर्भ-मुक्त व्याकरण ए और बी के लिए अनिर्णीत समस्या हैं:

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

मनमानी संदर्भ-मुक्त भाषाओं के लिए निम्नलिखित समस्याएं निर्णय योग्य हैं:

शून्यता: संदर्भ-मुक्त व्याकरण ए दिया गया है $L(A)=\emptyset$ ?^[23]
परिमितता: संदर्भ-मुक्त व्याकरण ए दिया गया है $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: @@
-{{Short description|Formal language generated by context-free grammar}}
+[[औपचारिक भाषा]] सिद्धांत में, संदर्भ-मुक्त भाषा (सीएफएल) [[संदर्भ-मुक्त व्याकरण]] (सीएफजी) द्वारा उत्पन्न औपचारिक भाषा है।
-[[औपचारिक भाषा]] सिद्धांत में, एक संदर्भ-मुक्त भाषा (सीएफएल) एक [[संदर्भ-मुक्त व्याकरण]] (सीएफजी) द्वारा उत्पन्न एक औपचारिक भाषा है।
 [[प्रोग्रामिंग भाषा]]ओं में संदर्भ-मुक्त भाषाओं के कई अनुप्रयोग होते हैं, विशेष रूप से, अधिकांश अंकगणितीय अभिव्यक्तियाँ संदर्भ-मुक्त व्याकरणों द्वारा उत्पन्न होती हैं।
@@ Line 8: / Line 7: @@
 ===संदर्भ-मुक्त व्याकरण===
-विभिन्न संदर्भ-मुक्त व्याकरण एक ही संदर्भ-मुक्त भाषा उत्पन्न कर सकते हैं। भाषा का वर्णन करने वाले कई व्याकरणों की तुलना करके भाषा के आंतरिक गुणों को किसी विशेष व्याकरण के बाहरी गुणों से अलग किया जा सकता है।
+विभिन्न संदर्भ-मुक्त व्याकरण ही संदर्भ-मुक्त भाषा उत्पन्न कर सकते हैं। भाषा का वर्णन करने वाले कई व्याकरणों की तुलना करके भाषा के आंतरिक गुणों को किसी विशेष व्याकरण के बाहरी गुणों से अलग किया जा सकता है।
 ===ऑटोमेटा===
-सभी संदर्भ-मुक्त भाषाओं का सेट [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकृत भाषाओं के सेट के समान है, जो इन भाषाओं को पार्सिंग के लिए उत्तरदायी बनाता है। इसके अलावा, किसी दिए गए सीएफजी के लिए, व्याकरण (और इस प्रकार संबंधित भाषा) के लिए एक पुशडाउन ऑटोमेटन का उत्पादन करने का एक सीधा तरीका है, हालांकि दूसरे तरीके से जाना (एक ऑटोमेटन दिए गए व्याकरण का निर्माण करना) उतना सीधा नहीं है।
+सभी संदर्भ-मुक्त भाषाओं का सेट [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकृत भाषाओं के सेट के समान है, जो इन भाषाओं को पार्सिंग के लिए उत्तरदायी बनाता है। इसके अलावा, किसी दिए गए सीएफजी के लिए, व्याकरण (और इस प्रकार संबंधित भाषा) के लिए पुशडाउन ऑटोमेटन का उत्पादन करने का सीधा तरीका है, हालांकि दूसरे तरीके से जाना (एक ऑटोमेटन दिए गए व्याकरण का निर्माण करना) उतना सीधा नहीं है।
 ==उदाहरण==
-संदर्भ-मुक्त भाषा का एक उदाहरण है <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>
@@ Line 26: / 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}}
 ===[[डाइक भाषा]]===
@@ Line 39: / Line 38: @@
 भाषा की संदर्भ-मुक्त प्रकृति पुशडाउन ऑटोमेटन के साथ पार्स करना आसान बनाती है।
-[[सदस्यता समस्या]] का एक उदाहरण निर्धारित करना; यानी एक स्ट्रिंग दी गई है <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 एल्गोरिथ्म]] शामिल हैं।
-संदर्भ-मुक्त भाषाओं का एक विशेष उपवर्ग नियतात्मक संदर्भ-मुक्त भाषाएं हैं जिन्हें [[नियतात्मक पुशडाउन ऑटोमेटन]] द्वारा स्वीकृत भाषाओं के सेट के रूप में परिभाषित किया गया है और [[एलआर पार्सर]] | एलआर (के) पार्सर द्वारा पार्स किया जा सकता है।<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>
 व्याकरण और पार्सर के वैकल्पिक दृष्टिकोण के रूप में [[अभिव्यक्ति व्याकरण को पार्स करना]] भी देखें।
@@ Line 55: / Line 54: @@
 *[[क्लेन स्टार]] <math>L^*</math> एल का{{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^{-1}(L)</math> एक स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का <math>\varphi^{-1}</math>{{sfn|Hopcroft|Ullman|1979|p=132|loc=Theorem 6.3}}
+*छवि <math>\varphi^{-1}(L)</math> स्ट्रिंग ऑपरेशंस#स्ट्रिंग होमोमोर्फिज्म के तहत एल का <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}}
 *एल का उपसर्ग समापन (एल से स्ट्रिंग के सभी [[उपसर्ग (कंप्यूटर विज्ञान)]] का सेट){{sfn|Hopcroft|Ullman|1979|p=142|loc=Exercise 6.4b}}
@@ Line 61: / Line 60: @@
 ====प्रतिच्छेदन, पूरक और अंतर के अंतर्गत असंबद्धता====
-संदर्भ-मुक्त भाषाएँ प्रतिच्छेदन के अंतर्गत बंद नहीं होती हैं। इसे भाषाओं को लेकर देखा जा सकता है <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>, जिसे संदर्भ-मुक्त भाषाओं के लिए पंपिंग लेम्मा द्वारा गैर-संदर्भ-मुक्त दिखाया जा सकता है। परिणामस्वरूप, संदर्भ-मुक्त भाषाओं को पूरकता के तहत बंद नहीं किया जा सकता है, क्योंकि किसी भी भाषा ए और बी के लिए, उनके प्रतिच्छेदन को संघ और पूरक द्वारा व्यक्त किया जा सकता है: <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>
 ===निर्णायकता===
-औपचारिक भाषा सिद्धांत में, नियमित भाषाओं के बारे में प्रश्न आमतौर पर निर्णय लेने योग्य होते हैं, लेकिन संदर्भ-मुक्त भाषाओं के बारे में अक्सर नहीं होते हैं। यह तय करने योग्य है कि क्या ऐसी भाषा सीमित है, लेकिन यह नहीं कि क्या इसमें हर संभव स्ट्रिंग शामिल है, नियमित है, असंदिग्ध है, या एक अलग व्याकरण वाली भाषा के बराबर है।
+औपचारिक भाषा सिद्धांत में, नियमित भाषाओं के बारे में प्रश्न आमतौर पर निर्णय लेने योग्य होते हैं, लेकिन संदर्भ-मुक्त भाषाओं के बारे में अक्सर नहीं होते हैं। यह तय करने योग्य है कि क्या ऐसी भाषा सीमित है, लेकिन यह नहीं कि क्या इसमें हर संभव स्ट्रिंग शामिल है, नियमित है, असंदिग्ध है, या अलग व्याकरण वाली भाषा के बराबर है।
 निम्नलिखित समस्याएँ मनमाने ढंग से दिए गए संदर्भ-मुक्त व्याकरण ए और बी के लिए [[अनिर्णीत समस्या]] हैं:
 *समतुल्यता: है <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}} इसलिए समस्या का वह प्रकार जहां बी नियमित व्याकरण है, निर्णय योग्य है (नीचे शून्यता देखें)।
-*नियंत्रण: है <math>L(A) \subseteq L(B)</math> ?{{sfn|Hopcroft|Ullman|1979|p=203|loc=Theorem 8.12(2)}} फिर, समस्या का वह प्रकार जहां बी एक नियमित व्याकरण है, निर्णय योग्य है,{{citation needed|date=December 2015}} जबकि जहां ए नियमित है वह आम तौर पर नहीं है।{{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)}} फिर, समस्या का वह प्रकार जहां बी नियमित व्याकरण है, निर्णय योग्य है, जबकि जहां ए नियमित है वह आम तौर पर नहीं है।{{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)</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) = \emptyset</math> ?{{sfn|Hopcroft|Ullman|1979|p=137|loc=Theorem 6.6(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)}}
+*परिमितता: संदर्भ-मुक्त व्याकरण ए दिया गया है <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>
 ===ऐसी भाषाएँ जो संदर्भ-मुक्त नहीं हैं===
-सेट <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}}
 ==संदर्भ==
 {{Reflist}}
 === उद्धृत कार्य ===
 {{Refbegin}}
@@ Line 109: / Line 96: @@
 * {{cite book|first=Seymour |last=Ginsburg |author-link=Seymour Ginsburg | title = The Mathematical Theory of Context-Free Languages | year = 1966 | publisher = McGraw-Hill | location = New York, NY, USA}}
 * {{cite book |first=Michael |last=Sipser |author-link=Michael Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips |pages=91–122 |chapter=2: Context-Free Languages}}
-{{Formal languages and grammars}}
 [[Category: औपचारिक भाषाएँ]] [[Category: वाक्य - विन्यास]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:05, 7 August 2023

Contents

पृष्ठभूमि

संदर्भ-मुक्त व्याकरण

ऑटोमेटा

उदाहरण

डाइक भाषा

गुण

संदर्भ-मुक्त पार्सिंग

बंद गुण

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

निर्णायकता

ऐसी भाषाएँ जो संदर्भ-मुक्त नहीं हैं

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 23:05, 7 August 2023

पृष्ठभूमि

संदर्भ-मुक्त व्याकरण

ऑटोमेटा

उदाहरण

डाइक भाषा

गुण

संदर्भ-मुक्त पार्सिंग

बंद गुण

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

निर्णायकता

ऐसी भाषाएँ जो संदर्भ-मुक्त नहीं हैं

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories