संदर्भ-मुक्त व्याकरण, अधोकोश स्वचालित्र व पंपिंग लेम्मा

परिमित स्वचालित्र के पास नियत मात्रा की स्मृति है; अधोकोश स्वचालित्र एक स्टैक जोड़ता है, और इस अध्याय में सब कुछ इससे निकलता है कि एकल स्टैक क्या कर सकता है और क्या नहीं। वह चीज़ों का एक युग्म मिला सकता है: स्टैक ठीक वही है जो n a पुश करने और उन्हें n b के विरुद्ध पॉप करने हेतु चाहिए, इसीलिए {aⁿbⁿ} अ-नियमित होते हुए भी संदर्भ-मुक्त है। वह एक साथ दो युग्म नहीं मिला सकता, क्योंकि a की b से जाँच स्टैक खाली कर देती है और c की जाँच हेतु कुछ शेष नहीं रहता — इसीलिए {aⁿbⁿcⁿ} संदर्भ-मुक्त नहीं है। एक स्टैक के विषय में वही एक वाक्य इस विषय के अधिकांश उत्तरों की भविष्यवाणी करता है, संवृति गुणों सहित। महत्वपूर्ण, और जिस पर अधिकांश प्रश्न घूमते हैं, वह नियमित भाषाओं से असममिति है: नियमित भाषाएँ सर्वनिष्ठ व पूरक के अंतर्गत संवृत हैं, और संदर्भ-मुक्त भाषाएँ किसी के अंतर्गत नहीं। साक्षी समय के दबाव में व्युत्पन्न करने के बजाय जानने योग्य है। L₁ = {aⁿbⁿcᵐ} संदर्भ-मुक्त है — a को b से मिलाएँ, c की अवहेलना करें। L₂ = {aᵐbⁿcⁿ} संदर्भ-मुक्त है — a की अवहेलना करें, b को c से मिलाएँ। उनका सर्वनिष्ठ तीनों गणनाएँ बराबर बाध्य करता है, जिससे {aⁿbⁿcⁿ} मिलता है, जो संदर्भ-मुक्त नहीं। अतः दो CFL का सर्वनिष्ठ अ-CFL है, और चूँकि पूरक के अंतर्गत संवृति तथा सम्मिलन के अंतर्गत संवृति मिलकर डी मॉर्गन से सर्वनिष्ठ के अंतर्गत संवृति देतीं, CFL पूरक के अंतर्गत भी संवृत नहीं हो सकतीं। पंपिंग लेम्मा इन नकारात्मक बातों को सिद्ध करने के उपकरण हैं, और दोनों का वही तार्किक आकार है जिसके विषय में यथार्थ होना उपयोगी है: वे किसी वर्ग की सदस्यता का खंडन कर सकते हैं और उसकी पुष्टि कभी नहीं।

एक स्टैक क्या देता है, और क्या नहीं

वे चार भाषाएँ जो अधिकांश प्रश्न तय करती हैं
भाषावर्गक्यों
abनियमितकोई गणना ही नहीं — केवल क्रम महत्व रखता है
{aⁿbⁿ}संदर्भ-मुक्त, नियमित नहींमिलाने योग्य एक युग्म — ठीक एक स्टैक
{aⁿbⁿcⁿ}संदर्भ-मुक्त नहींएक साथ दो युग्म — स्टैक पहले पर व्यय हो जाता है
{ww : w ∈ {a,b}*}संदर्भ-मुक्त नहींस्टैक उलटता है, अतः वह wwᴿ मिलाता है, ww नहीं
🎯 {wwᴿ} संदर्भ-मुक्त क्यों और {ww} क्यों नहीं
स्टैक जो आप डालते हैं वही उलटे क्रम में लौटाता है। अतः यह जाँचने हेतु कि माला का दूसरा आधा पहले का प्रतिलोम है, पहला आधा पुश करें और उसे दूसरे आधे के विरुद्ध पॉप करें, प्रतीक-दर-प्रतीक तुलना करते हुए — जो ठीक {wwᴿ}, पैलिंड्रोमों का PDA है। यह जाँचने हेतु कि दूसरा आधा पहले के बराबर है, आपको प्रतीक उसी क्रम में वापस चाहिए जिसमें वे गए थे, और स्टैक वह नहीं कर सकता: दूसरे आधे तक पहुँचने तक आपका पुश किया पहला प्रतीक तल पर होता है। {ww} संदर्भ-मुक्त नहीं और {wwᴿ} है — इसका सम्पूर्ण कारण वही है, और प्रश्न इस भेद का लगातार दोहन करते हैं, क्योंकि लिखे जाने पर दोनों लगभग समान दिखते हैं। मिलान की दिशा हेतु पढ़ना — उलटा या वही क्रम — वही आदत है जो उन्हें तय करती है।

संवृति असममिति, अपने साक्षी सहित

नियमित बनाम संदर्भ-मुक्त
संक्रियानियमितसंदर्भ-मुक्त
सम्मिलनसंवृतसंवृत
संयोजन, तारासंवृतसंवृत
सर्वनिष्ठसंवृतसंवृत नहीं
पूरकसंवृतसंवृत नहीं
नियमित भाषा से सर्वनिष्ठसंवृतसंवृत — उपयोगी अपवाद
🧠 एक साक्षी दो विफलताएँ सिद्ध करता है
L₁ = {aⁿbⁿcᵐ} व L₂ = {aᵐbⁿcⁿ} लें। प्रत्येक संदर्भ-मुक्त है: पहला a को b से मिलाता है व c को स्वतंत्र छोड़ता है, दूसरा a की अवहेलना करके b को c से मिलाता है, और प्रत्येक को केवल एक स्टैक चाहिए। उनका सर्वनिष्ठ तीनों गणनाएँ बराबर बाध्य करता है — {aⁿbⁿcⁿ} — जो संदर्भ-मुक्त नहीं। इससे सर्वनिष्ठ तय हो जाता है। तत्पश्चात् पूरक बिना नए उदाहरण निकलता है: यदि CFL पूरक के अंतर्गत संवृत होतीं, तो चूँकि वे सम्मिलन के अंतर्गत संवृत हैं, डी मॉर्गन सर्वनिष्ठ के अंतर्गत संवृति देता, और हमने अभी देखा कि वह विफल है। अतः एक प्रत्युदाहरण दोनों का खंडन करता है, और उसे पुनर्रचना करने के बजाय ठीक इसी रूप में साथ रखना उपयोगी है। तालिका की अंतिम पंक्ति वह अपवाद है जो रचनात्मक रूप से प्रयुक्त होता है: CFL ∩ नियमित सदा संदर्भ-मुक्त है, और व्यवहार में PDA को परिमित स्वचालित्र से इसी प्रकार संयोजित किया जाता है।

पंपिंग लेम्मा, तथा वे क्या सिद्ध कर सकते हैं

नियमित पंपिंग लेम्मा कहती है: यदि L नियमित है तो कोई लंबाई p है ऐसी कि L में प्रत्येक w जिसका |w| ≥ p हो वह xyz के रूप में विभाजित होती है जहाँ |xy| ≤ p, |y| ≥ 1, तथा प्रत्येक i ≥ 0 हेतु xyⁱz, L में हो। नियमितता का खंडन करने हेतु ऐसी w चुनें जो प्रत्येक वैध विभाजन को हरा दे। {aⁿbⁿ} हेतु w = aᵖbᵖ लें: प्रतिबंध |xy| ≤ p, y को पूर्णतः a-खंड के भीतर बाध्य करता है, अतः उसे पंप करना b के बिना a जोड़ता है और भाषा से बाहर ले जाता है। संदर्भ-मुक्त संस्करण uvxyz में विभाजित होता है जहाँ |vxy| ≤ p, और v व y साथ पंप होते हैं, तथा {aⁿbⁿcⁿ} हेतु खिड़की vxy तीनों खंडों को स्पर्श करने हेतु बहुत छोटी है, अतः पंपिंग उन दो को असंतुलित कर देती है जिन्हें वह छोड़ती है।

⚠️ पंपिंग लेम्मा खंडन कर सकती है, पुष्टि कभी नहीं
लेम्मा का रूप है "यदि L नियमित है तो L पंप होती है"। अतः जो भाषा पंप होने में विफल हो वह निश्चित रूप से नियमित नहीं है — वह वैध प्रतिलोम-कथन है और लेम्मा उसी हेतु है। परंतु जो भाषा पंप होती है उसने कुछ सिद्ध नहीं किया: विलोम असत्य है, और पंपिंग शर्त संतुष्ट करती अ-नियमित भाषाएँ विद्यमान हैं। अतः "मैंने उसे सफलतापूर्वक पंप किया, अतः वह नियमित है" अवैध है, और वह तर्क देता विकल्प, कितना ही विश्वसनीय पढ़ा जाए, गलत है। जब आप वस्तुतः नियमितता सिद्ध करना चाहें, तो DFA या नियमित व्यंजक बनाएँ, या मिहिल–नेरोड वर्ग गिनें और संख्या परिमित पाएँ। वही असममिति संदर्भ-मुक्त पंपिंग लेम्मा पर अक्षरशः लागू है। कोई उपकरण किस दिशा में काम करता है यह जानना यहाँ उसे लगाने की प्रवाहशीलता से अधिक मूल्यवान है।

मुख्य बिंदु

  • PDA परिमित स्वचालित्र तथा एक स्टैक है, और एक स्टैक ठीक एक गणना-युग्म मिलाता है।
  • {aⁿbⁿ} संदर्भ-मुक्त व अ-नियमित है; {aⁿbⁿcⁿ} संदर्भ-मुक्त नहीं — दो युग्म, एक स्टैक।
  • स्टैक प्रतीक उलटे लौटाता है, अतः {wwᴿ} संदर्भ-मुक्त है और {ww} नहीं।
  • CFL सम्मिलन, संयोजन व तारा के अंतर्गत संवृत हैं पर सर्वनिष्ठ या पूरक के अंतर्गत नहीं।
  • साक्षी: {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ}, और तत्पश्चात् पूरक डी मॉर्गन से विफल।
  • CFL ∩ नियमित संदर्भ-मुक्त है — वह अपवाद जो रचनात्मक रूप से प्रयुक्त होता है।
  • {aⁿbⁿ} हेतु w = aᵖbᵖ पंप करें: |xy| ≤ p, y को a-खंड के भीतर बाध्य करता है।
  • पंपिंग लेम्मा किसी वर्ग की सदस्यता का खंडन करती है, पुष्टि कभी नहीं — विलोम असत्य है।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. संदर्भ-मुक्त भाषाओं के किस युग्म का सर्वनिष्ठ संदर्भ-मुक्त नहीं है?

    1. {aⁿbⁿ} तथा {aⁿbⁿ}
    2. {aⁿbⁿcᵐ} तथा {aᵐbⁿcⁿ}
    3. ab तथा ba
    4. {aⁿbⁿ} तथा ab
    उत्तर देखें

    उत्तर: B — {aⁿbⁿcᵐ} तथा {aᵐbⁿcⁿ}

    {aⁿbⁿcᵐ} व {aᵐbⁿcⁿ} में प्रत्येक को एक स्टैक चाहिए — पहला a को b से मिलाता है, दूसरा b को c से — अतः दोनों संदर्भ-मुक्त हैं। उनके सर्वनिष्ठ को तीनों गणनाएँ बराबर चाहिए, जिससे {aⁿbⁿcⁿ} मिलता है, जो संदर्भ-मुक्त नहीं क्योंकि एक स्टैक दो युग्म नहीं जाँच सकता। विकल्प D, CFL का नियमित भाषा से सर्वनिष्ठ है, और वह सदा संदर्भ-मुक्त है — वही एक संवृति जो टिकती है। विकल्प C दो नियमित भाषाओं का सर्वनिष्ठ है, जो नियमित है। यही एक उदाहरण पूरक भी तय करता है: पूरक के अंतर्गत संवृति तथा CFL के पास जो सम्मिलन-संवृति है वे मिलकर डी मॉर्गन से सर्वनिष्ठ-संवृति देतीं, अतः पूरक भी विफल है।

  2. {wwᴿ : w ∈ {a,b}} संदर्भ-मुक्त क्यों है जबकि {ww : w ∈ {a,b}} नहीं?

    1. क्योंकि wwᴿ छोटा है
    2. क्योंकि स्टैक प्रतीक उलटे क्रम में लौटाता है
    3. क्योंकि wwᴿ नियमित है
    4. क्योंकि ww को वर्णमाला पहचानने हेतु दो स्टैक चाहिए
    उत्तर देखें

    उत्तर: B — क्योंकि स्टैक प्रतीक उलटे क्रम में लौटाता है

    स्टैक अंतिम-में-प्रथम-बाहर है, अतः पहला आधा पुश करके उसे दूसरे आधे के विरुद्ध पॉप करना उनकी तुलना विपरीत क्रम में करता है — ठीक वही जो wwᴿ को चाहिए। ww मिलाने हेतु पुश किए प्रतीक उसी क्रम में वापस चाहिए जिसमें वे गए, जो स्टैक नहीं दे सकता: पुश किया पहला प्रतीक अंत में उपलब्ध होता है। विकल्प C असत्य है — {wwᴿ} संदर्भ-मुक्त है और नियमित नहीं, और जो अभ्यर्थी उसे नियमित मानता है वह उस पर लगी पंपिंग लेम्मा के प्रश्नों का उत्तर भी गलत देगा। दोनों भाषाएँ कागज़ पर लगभग समान दिखती हैं, अतः मिलान की दिशा हेतु पढ़ना वही आदत है जो उन्हें पृथक् करती है।

  3. संदर्भ-मुक्त भाषाएँ निम्नलिखित में किसके अंतर्गत संवृत हैं? (एक से अधिक सही हो सकते हैं।)

    1. सम्मिलन
    2. नियमित भाषा से सर्वनिष्ठ
    3. किसी अन्य संदर्भ-मुक्त भाषा से सर्वनिष्ठ
    4. पूरक
    उत्तर देखें

    उत्तर: A — सम्मिलन; B — नियमित भाषा से सर्वनिष्ठ

    A व B। सम्मिलन सरल है — नया आरंभ प्रतीक जोड़ें जो किसी भी व्याकरण का आरंभ प्रतीक व्युत्पन्न करे। नियमित भाषा से सर्वनिष्ठ उपयोगी अपवाद है: PDA व परिमित स्वचालित्र को गुणन रचना में साथ चलाएँ, और चूँकि DFA को स्टैक नहीं चाहिए, परिणाम फिर भी PDA है। C असत्य है, साक्षी {aⁿbⁿcᵐ} ∩ {aᵐbⁿcⁿ} = {aⁿbⁿcⁿ} से। D असत्य है और C से निकलता है बिना नए उदाहरण, क्योंकि सम्मिलन-संवृति तथा पूरक-संवृति मिलकर डी मॉर्गन से सर्वनिष्ठ-संवृति देतीं। नियमित भाषाओं से विरोध — जो चारों के अंतर्गत संवृत हैं — इन्हें एक-एक के बजाय समुच्चय के रूप में सीखने का सम्पूर्ण अभिप्राय वही है।

  4. कोई भाषा नियमित पंपिंग लेम्मा की शर्तें संतुष्ट करती है। इससे निकलता है कि वह भाषा:

    1. नियमित है
    2. नियमित हो भी सकती है और नहीं भी
    3. संदर्भ-मुक्त है पर नियमित नहीं
    4. नियमित नहीं है
    उत्तर देखें

    उत्तर: B — नियमित हो भी सकती है और नहीं भी

    लेम्मा कहती है "यदि L नियमित है तो L पंप होती है"। उसका वैध प्रयोग प्रतिलोम-कथन है: जो भाषा पंप होने में विफल हो वह निश्चित रूप से नियमित नहीं। विलोम प्रमेय नहीं है, और पंपिंग शर्त संतुष्ट करती अ-नियमित भाषाएँ विद्यमान हैं — अतः सफलतापूर्वक पंप होना कुछ भी स्थापित नहीं करता, और ईमानदार उत्तर B है। यह प्रिय प्रश्न है क्योंकि विकल्प A किसी सोपाधिक कथन का स्वाभाविक भ्रम-पाठ है, और इसे सही करना लेम्मा में कौशल का विषय नहीं अपितु यह जानने का है कि वह किस दिशा में चलती है। किसी भाषा को वस्तुतः नियमित सिद्ध करने हेतु DFA या नियमित व्यंजक दिखाएँ, या मिहिल–नेरोड वर्ग संख्या में परिमित दिखाएँ।

  5. पंपिंग लंबाई p सहित पंपिंग लेम्मा से {aⁿbⁿ : n ≥ 0} अ-नियमित दिखाने हेतु चुनने योग्य माला है:

    1. aᵖbᵖ
    2. aᵖ
    3. ab
    4. bᵖaᵖ
    उत्तर देखें

    उत्तर: A — aᵖbᵖ

    aᵖbᵖ। वह भाषा में है और पर्याप्त लंबी, और प्रतिबंध |xy| ≤ p पंप होते खंड y को पूर्णतः a-क्षेत्र के भीतर बाध्य करता है — अतः पंपिंग मिलान करते b के बिना a जोड़ती है और भाषा से बाहर ले जाती है, एक साथ प्रत्येक वैध विभाजन को हराते हुए। विकल्प B भाषा में ही नहीं है, अतः वह कुछ सिद्ध नहीं करता। विकल्प C लेम्मा लागू होने हेतु बहुत छोटा है। विकल्प D भी भाषा में नहीं — b पहले आते हैं। सामान्य शिक्षा यह है कि साक्षी माला चुनना ही सम्पूर्ण काम है: ऐसी चुनें जहाँ |xy| ≤ p खिड़की उस क्षेत्र में फँसी हो जिसे संतुलित रहना ही है।

  6. भाषा {aⁿbⁿcⁿ : n ≥ 1} है:

    1. नियमित
    2. संदर्भ-मुक्त पर नियमित नहीं
    3. संदर्भ-मुक्त नहीं
    4. किसी ट्यूरिंग मशीन से अपहचानीय
    उत्तर देखें

    उत्तर: C — संदर्भ-मुक्त नहीं

    संदर्भ-मुक्त नहीं। PDA के पास एक स्टैक है, और a की b से जाँच उसे पूर्णतः खर्च कर देती है — c की जाँच हेतु कुछ न छोड़ते हुए। संदर्भ-मुक्त पंपिंग लेम्मा उसे औपचारिक बनाती है: खिड़की |vxy| ≤ p तीनों खंडों पर नहीं फैल सकती, अतः पंपिंग उन्हें असंतुलित करती है जिन्हें वह छोड़ती है। विकल्प D गलत है और स्पष्ट रखने योग्य: भाषा ट्यूरिंग मशीन से सहज निर्णेय है, जो टेप पर जितनी बार चाहे आगे-पीछे चल सकती है, अतः वह संदर्भ-मुक्त से ऊपर के वर्ग में आराम से बैठती है। "एक स्टैक" व "एक टेप" का वही अंतर अगले अध्याय का विषय है।

  7. संदर्भ-मुक्त भाषा का नियमित भाषा से सर्वनिष्ठ है:

    1. सदा नियमित
    2. सदा संदर्भ-मुक्त
    3. कभी संदर्भ-मुक्त नहीं
    4. सदा परिमित
    उत्तर देखें

    उत्तर: B — सदा संदर्भ-मुक्त

    सदा संदर्भ-मुक्त, और यही वह अपवाद है जो संवृति-तालिका को केवल चेतावनी के बजाय उपयोगी बनाता है। PDA व DFA को गुणन मशीन के रूप में साथ-साथ चलाएँ: DFA अवस्थाएँ देता है पर उसे स्टैक नहीं चाहिए, अतः संयोजन फिर भी एक-स्टैक मशीन है। विकल्प A अधिक दावा करता है — {aⁿbⁿ} ∩ ab स्वयं {aⁿbⁿ} है, जो नियमित नहीं। व्यावहारिक मूल्य यह है कि CFL को प्रतिबंधित करने का मानक तरीका यही है: नियमित भाषा से सर्वनिष्ठ लेना आपको वर्ग छोड़े बिना कोई स्थिति काटने देता है, और CFL के विषय में तर्क को प्रायः ठीक वही चाहिए।

  8. निर्धारणवादी PDA अनिर्धारणवादी से कठोरतः कम शक्तिशाली है। कौन-सी भाषा यह दिखाती है?

    1. {aⁿbⁿ}
    2. {a, b} पर सम-लंबाई पैलिंड्रोम
    3. ab
    4. {aⁿbⁿcⁿ}
    उत्तर देखें

    उत्तर: B — {a, b} पर सम-लंबाई पैलिंड्रोम

    पैलिंड्रोम। अनिर्धारणवादी PDA अनुमान लगाता है कि मध्य-बिंदु कहाँ है, पहला आधा पुश करता है व दूसरे के विरुद्ध पॉप करता है; निर्धारणवादी मशीन के पास यह जानने का कोई मार्ग नहीं कि मध्य कब आ गया, और कोई DPDA उस भाषा को नहीं पहचानता। परिमित स्वचालित्रों से यह तीव्र विरोध है, जहाँ निर्धारणवाद केवल आकार की कीमत लेता है: यहाँ वह शक्ति की कीमत लेता है, और दोनों मॉडलों का वह अंतर प्रिय परीक्षा-बिंदु है। {aⁿbⁿ} का पूर्णतः अच्छा DPDA है — पहला b आने पर पुश से पॉप पर जाएँ — अतः विकल्प A साक्षी नहीं, और {aⁿbⁿcⁿ} दोनों वर्गों के बाहर है।