कांटैक्स्ट फ्री लैंग्वेज

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

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

पृष्ठभूमि

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

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

ऑटोमेटा

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

उदाहरण

$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]

Anonymous

Search

कांटैक्स्ट फ्री लैंग्वेज

Namespaces

More

Page actions

Contents

पृष्ठभूमि

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

ऑटोमेटा

उदाहरण

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

गुण

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

विवृत गुण

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

निर्णायकता

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

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

कांटैक्स्ट फ्री लैंग्वेज

पृष्ठभूमि

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

ऑटोमेटा

उदाहरण

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

गुण

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

विवृत गुण

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

निर्णायकता

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

टिप्पणियाँ

संदर्भ

उद्धृत कार्य

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories