औपचारिक भाषा आधार व असुलझी समस्याएँ

यह इकाई 8 का एकमात्र नया अध्याय है, और यह जान-बूझकर वास्तव में पतला है: उधार लिए GATE अभिकलन सिद्धांत व संकलक अभिकल्प अध्याय नियमित/संदर्भ-मुक्त भाषाएँ, स्वचालित्र, ट्यूरिंग मशीन व अनिर्णेयता, वाक्य-रचना विश्लेषण, शब्दार्थ विश्लेषण, रनटाइम परिवेश, मध्यवर्ती कोड व अनुकूलन GATE की अपनी गहराई पर ढकते हैं, जो NET की इकाई 8 जो कुछ पूछती है उसका लगभग सम्पूर्ण, जाँचा हुआ मेल है। जो वस्तुतः उस उधार ली सामग्री से बाहर बैठता है वह इस इकाई का अपना आरंभिक प्रकरण है — किसी भी स्वचालित्र के प्रस्तुत होने से पहले विकर्णीकरण-तर्क/रसेल-विरोधाभास के रूप में कहा गया औपचारिक भाषा आधार, तथा चॉम्स्की पदानुक्रम व असुलझी-समस्या शब्दावली (हाल्टिंग समस्या, पोस्ट-संगति समस्या, साध्य/असाध्य) मान लेने के बजाय स्पष्ट रूप से नामित।

औपचारिक भाषाएँ, अ-अभिकलनात्मक समस्याएँ, विकर्णीकरण-तर्क व रसेल-विरोधाभास

किसी भी स्वचालित्र की परिभाषा से पहले, पाठ्यक्रम पूछता है कि 'अ-अभिकलनात्मक' (असुलझी) समस्याएँ बिल्कुल विद्यमान क्यों होनी चाहिए — एक शुद्ध रूप से गणना-तर्क, कैंटर के विकर्णीकरण-तर्क से आया। सभी संभव प्रोग्रामों (परिमित वर्णमाला पर परिमित स्ट्रिंग) का समुच्चय गणनीय अनंत है — इन्हें p₁, p₂, p₃, … सूचीबद्ध किया जा सकता है, क्योंकि प्रत्येक परिमित स्ट्रिंग है। पर प्राकृतिकों से प्राकृतिकों तक सभी संभव फलनों (समतुल्यतः, किसी प्रोग्राम को हल करने योग्य सभी संभव भाषाओं/समस्याओं) का समुच्चय अगणनीय अनंत है — कड़ाई से बड़ा, उसी विकर्णीकरण-तर्क से जिसे कैंटर ने वास्तविक संख्याओं को अगणनीय दिखाने हेतु प्रयोग किया। चूँकि उन्हें हल करने वाले प्रोग्रामों से कड़ाई से अधिक समस्याएँ हैं, अधिकांश समस्याओं का कोई हल करने वाला प्रोग्राम बिल्कुल नहीं — अनिर्णेय/असुलझी समस्याएँ चतुर रचना से खोजी जाने वाली विरल विकृति नहीं, वे भारी बहुमत हैं, और विकर्णीकरण-तर्क यह किसी विशिष्ट असुलझी समस्या (जैसे हाल्टिंग समस्या) के नामित होने से पहले ही सिद्ध कर देता है।

💡 रसेल-विरोधाभास समुच्चय-सिद्धांत में वही स्व-संदर्भ जाल है
समुच्चय R = {x : x ∉ x} लें — उन सभी समुच्चयों का समुच्चय जो स्वयं को नहीं रखते। 'क्या R ∈ R?' पूछना दोनों ओर सीधे विरोधाभास तक ले जाता है: यदि R ∈ R, तो R के अपने ही परिभाषा-नियम से R ∉ R; यदि R ∉ R, तो R नियम संतुष्ट करता है और अतः R ∈ R। यही रसेल-विरोधाभास है, और यह वही स्व-संदर्भ क्रियाविधि है जिसका विकर्णीकरण-तर्क व हाल्टिंग समस्या का अपना प्रमाण दोनों उपयोग करते हैं — ऐसा तंत्र जो स्वयं के विषय में बात करने योग्य पर्याप्त शक्तिशाली हो (ऐसा समुच्चय जो स्वयं को रख सके, ऐसा प्रोग्राम जिसे स्वयं का विवरण निवेश के रूप में दिया जा सके) ठीक यही विरोधाभास खोलता है, यही ठीक वह कारण है कि इसे विकर्णीकरण-तर्क के साथ इस पाठ्यक्रम-मद की साझा प्रत्ययात्मक जड़ के रूप में रखा गया है।

चॉम्स्की पदानुक्रम, स्पष्ट रूप से नामित

चार चॉम्स्की स्तर, कड़ाई से नेस्टेड
प्रकारभाषा वर्गपहचानने वाली मशीनव्याकरण-प्रतिबंध
प्रकार 3नियमितपरिमित स्वचालित्र (DFA/NFA)A → aB या A → a (दक्षिण/वाम-रैखिक)
प्रकार 2संदर्भ-मुक्तअधोकोश स्वचालित्रA → γ (बाईं ओर एकल गैर-अंतस्थ)
प्रकार 1संदर्भ-सुग्राहीरैखिक-परिबद्ध स्वचालित्रαAβ → αγβ (γ अरिक्त; लंबाई कभी नहीं घटती)
प्रकार 0पुनरावर्ती-गणनीय / अप्रतिबंधितट्यूरिंग मशीनउत्पादनों पर बिल्कुल कोई प्रतिबंध नहीं
⚠️ पदानुक्रम **कड़ा** समावेशन है, चार असंबद्ध वर्ग नहीं
नियमित ⊊ संदर्भ-मुक्त ⊊ संदर्भ-सुग्राही ⊊ पुनरावर्ती-गणनीय — प्रत्येक अगले का उचित उपसमुच्चय है, अर्थात् हर नियमित भाषा संदर्भ-मुक्त है, पर हर संदर्भ-मुक्त भाषा नियमित नहीं (उदा० {aⁿbⁿ : n ≥ 0} संदर्भ-मुक्त है, उधार लिए GATE अध्याय द्वारा ढके पंपिंग लेम्मा से सिद्ध रूप से नियमित नहीं)। भाषा का चॉम्स्की प्रकार वह सबसे छोटा वर्ग है जिसकी वह है — {aⁿbⁿ} को 'संदर्भ-सुग्राही' कहना तकनीकी रूप से सत्य है पर उसका कसौतम, व अतः सामान्यतः-अभिप्रेत, वर्गीकरण नहीं।

हाल्टिंग समस्या, पोस्ट-संगति समस्या व अन्य असुलझी समस्याएँ

हाल्टिंग समस्या पूछती है: प्रोग्राम P व निवेश x दिए, क्या P, x पर रुकता है, या अनंत काल चलता है? ट्यूरिंग ने इसे प्रत्यक्ष विकर्णीकरण/स्व-संदर्भ तर्क से अनिर्णेय सिद्ध किया: मान लें कोई काल्पनिक HALTS(P, x) निर्णायक विद्यमान है, एक नया प्रोग्राम D बनाएँ जो, किसी प्रोग्राम के अपने विवरण P को निवेश के रूप में दिए जाने पर, HALTS(P, P) चलाता है व फिर विपरीत करता है (यदि HALTS कहे कि P स्वयं पर रुकता है तो अनंत काल लूप करता है; यदि HALTS कहे कि P स्वयं पर लूप करता है तो रुकता है) — फिर पूछें कि D(D) क्या करता है, व कोई भी उत्तर उसका विरोधाभास करता है जो HALTS ने अभी निर्णीत किया। चूँकि निर्णायक की मान्यता विरोधाभास तक ले जाती है, ऐसा कोई निर्णायक विद्यमान नहीं हो सकता। पोस्ट-संगति समस्या (PCP) पूछती है: स्ट्रिंगों की दो सूचियाँ A = (a₁,…,aₙ) व B = (b₁,…,bₙ) दी हैं, क्या सूचकांकों i₁,…,iₖ का ऐसा अनुक्रम (दोहराव अनुमत) है कि ai1ai2…aik = bi1bi2…bik? PCP भी अनिर्णेय है, व इसका प्रयोग न्यूनन द्वारा अन्य अनेक अनिर्णेयता-परिणाम सिद्ध करने हेतु किया जाता है (दिखाते हुए कि किसी नई समस्या हेतु निर्णायक PCP हेतु निर्णायक दे देगा), ठीक वही न्यूनन-तकनीक जो निम्न सीमा सिद्धांत की है, यहाँ चलने-के-समय की निम्न सीमा के बजाय अनिर्णेयता पर लागू।

  • संदर्भ-मुक्त भाषाओं हेतु असुलझी समस्याएँ: कई स्वाभाविक प्रश्न जो नियमित भाषाओं हेतु निर्णेय हैं, संदर्भ-मुक्त व्याकरणों के विषय में पूछे जाने पर अनिर्णेय हो जाते हैं — क्या दो संदर्भ-मुक्त व्याकरण वही भाषा उत्पन्न करते हैं, क्या संदर्भ-मुक्त व्याकरण द्विअर्थी है, व क्या संदर्भ-मुक्त व्याकरण अपनी वर्णमाला पर सभी स्ट्रिंग उत्पन्न करता है, सभी अनिर्णेय हैं, नियमित भाषाओं/DFA हेतु संगत (निर्णेय) प्रश्नों के तीव्र विपरीत।
  • जटिलता की माप व वर्गीकरण: अभिकलन सिद्धांत की अनिर्णेयता-रेखा (क्या यह बिल्कुल हल हो सकता है) जटिलता सिद्धांत की साध्यता-रेखा (क्या यह दक्षतापूर्वक हल हो सकता है) से पृथक है — समस्या निर्णेय हो सकती है फिर भी असाध्य (हर NP-पूर्ण समस्या निर्णेय है, क्योंकि परिमित निवेश हेतु प्रत्यक्ष-बल परिगणना अंततः सदा समाप्त होती है, पर कोई भी दक्षतापूर्वक निर्णेय ज्ञात नहीं), व पूर्व अध्याय की साध्य/असाध्य शब्दावली ठीक वही दूसरा, महीन भेद है जो एक बार समस्या पहली, स्थूलतर निर्णेयता-सीमा पार कर चुके तब खींचा जाता है।

उधार लिए संकलक-अभिकल्प अध्यायों के विरुद्ध NET की गहराई पढ़ना

मान लेने के बजाय कि उधार पूर्ण मेल है, दो जाँचें स्पष्ट रूप से करने योग्य हैं। पहला, LALR(1) पाठ्यक्रम में सामान्य LR पार्सिंग के साथ विशेष रूप से नामित है — उधार लिए GATE संकलक अभिकल्प अध्याय की अपनी LR-कुल सामग्री विहित LR(1) व उसकी सारणी-निर्माण यंत्रावली गहराई से ढकती है, व LALR(1) को मानक रूप से 'वही निर्माण, सारणी छोटी करने हेतु अवस्थाएँ विलीन करते हुए' के रूप में प्रस्तुत किया जाता है, पहले से ढके LR सिद्धांत के ऊपर वास्तविक पर तुलनात्मक रूप से छोटा जोड़, अपना पृथक अध्याय चाहने वाला भिन्न प्रकरण नहीं। दूसरा, पाठ्यक्रम का ट्यूरिंग-मशीन मद 'मानक ट्यूरिंग मशीन व उसके रूपांतर' व 'सरल समस्याओं हेतु TM का निर्माण' नामित करता है — दोनों उधार लिए GATE अभिकलन सिद्धांत अध्याय के अपने ट्यूरिंग-मशीन खंड के भीतर मानक सामग्री हैं। साथ लेने पर, यह उस निर्णय की पुष्टि करता है जो इस इकाई के तार जोड़ते समय लिया गया: इकाई 8 के भारी बहुमत हेतु छहों GATE अध्याय पूरे उधार लें, व केवल उनसे पहले के वास्तविक, गैर-तुच्छ अंतराल हेतु यह एक अध्याय ताज़ा लिखें।

मुख्य बिंदु

  • विकर्णीकरण-तर्क दिखाता है कि संभव प्रोग्रामों (गणनीय) से कड़ाई से अधिक संभव समस्याएँ (अगणनीय) हैं, अतः सिद्धांततः अधिकांश समस्याएँ असुलझी हैं — किसी विशिष्ट असुलझी समस्या के नामित होने से पहले ही।
  • रसेल-विरोधाभास व हाल्टिंग समस्या का प्रमाण दोनों वही स्व-संदर्भ क्रियाविधि उपयोग करते हैं।
  • चॉम्स्की पदानुक्रम (नियमित ⊊ संदर्भ-मुक्त ⊊ संदर्भ-सुग्राही ⊊ पुनरावर्ती-गणनीय) कड़ा समावेशन है; भाषा का प्रकार वह सबसे छोटा वर्ग है जिसकी वह है।
  • हाल्टिंग समस्या व पोस्ट-संगति समस्या दोनों अनिर्णेय हैं; PCP का स्वयं प्रयोग न्यूनन द्वारा अनेक अन्य अनिर्णेयता-परिणाम सिद्ध करने हेतु किया जाता है।
  • अनिर्णेयता (क्या यह बिल्कुल हल हो सकता है) व असाध्यता (क्या यह दक्षतापूर्वक हल हो सकता है) पृथक रेखाएँ हैं — हर NP-पूर्ण समस्या निर्णेय है, बस दक्षतापूर्वक निर्णेय ज्ञात नहीं।

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

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

  1. विकर्णीकरण-तर्क दिखाता है कि असुलझी समस्याएँ विद्यमान होनी ही चाहिए क्योंकि:

    1. सभी संभव समस्याओं का समुच्चय अगणनीय है, जबकि सभी संभव प्रोग्रामों का समुच्चय गणनीय है
    2. समस्याओं से अधिक प्रोग्राम हैं
    3. हर समस्या के इसे हल करते अनंत प्रोग्राम हैं
    4. प्रोग्राम परिमित स्ट्रिंग के रूप में नहीं लिखे जा सकते
    उत्तर देखें

    उत्तर: A — सभी संभव समस्याओं का समुच्चय अगणनीय है, जबकि सभी संभव प्रोग्रामों का समुच्चय गणनीय है

    चूँकि प्रोग्राम (परिमित स्ट्रिंग) गणनीय हैं पर फलन/समस्याएँ अगणनीय हैं, कभी हो सकने वाले प्रोग्रामों से कड़ाई से अधिक समस्याएँ हैं, अतः अधिकांश समस्याओं का कोई हल करने वाला प्रोग्राम बिल्कुल नहीं होता।

  2. रसेल-विरोधाभास व हाल्टिंग समस्या की अनिर्णेयता का मानक प्रमाण यह साझा करते हैं:

    1. वही स्व-संदर्भ क्रियाविधि
    2. बिल्कुल कोई संबंध नहीं
    3. दोनों केवल परिमित स्वचालित्र के विषय में हैं
    4. दोनों बाद में असत्य सिद्ध हुए
    उत्तर देखें

    उत्तर: A — वही स्व-संदर्भ क्रियाविधि

    दोनों रचनाएँ किसी वस्तु को स्वयं पर लागू (या स्वयं के विषय में पूछते) हुए विचारती हैं व किसी भी संभव उत्तर से सीधा विरोधाभास निकालती हैं, जो दोनों प्रमाणों में प्रयुक्त स्व-संदर्भ की परिभाषित युक्ति है।

  3. चॉम्स्की पदानुक्रम में, भाषा {aⁿbⁿ : n ≥ 0} सही ढंग से इस प्रकार वर्गीकृत है:

    1. संदर्भ-मुक्त (इसका सबसे छोटा/कसा वर्ग), नियमित नहीं
    2. नियमित
    3. बिल्कुल भाषा नहीं
    4. पुनरावर्ती-गणनीय पर संदर्भ-सुग्राही नहीं
    उत्तर देखें

    उत्तर: A — संदर्भ-मुक्त (इसका सबसे छोटा/कसा वर्ग), नियमित नहीं

    {aⁿbⁿ} संदर्भ-मुक्त व्याकरण से उत्पन्न होती है पर नियमित भाषाओं हेतु पंपिंग लेम्मा में सिद्ध रूप से विफल होती है, अतः संदर्भ-मुक्त इसका कसा (व अतः सही) वर्गीकरण है, भले ही यह तकनीकी रूप से संदर्भ-सुग्राही व पुनरावर्ती-गणनीय भी हो।

  4. पोस्ट-संगति समस्या (PCP) मुख्यतः इसलिए महत्वपूर्ण है कि यह:

    1. स्वयं अनिर्णेय है व न्यूनन द्वारा अनेक अन्य अनिर्णेयता-परिणाम सिद्ध करने हेतु प्रयुक्त होती है
    2. सदा स्थिर समय में हल-योग्य है
    3. स्ट्रिंगों से इसका कोई लेना-देना नहीं
    4. 1990 में निर्णेय सिद्ध हुई
    उत्तर देखें

    उत्तर: A — स्वयं अनिर्णेय है व न्यूनन द्वारा अनेक अन्य अनिर्णेयता-परिणाम सिद्ध करने हेतु प्रयुक्त होती है

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

  5. क्या दो दिए संदर्भ-मुक्त व्याकरण वही भाषा उत्पन्न करते हैं यह है:

    1. अनिर्णेय
    2. स्थिर समय में निर्णेय
    3. यह वही प्रश्न है जो DFA व NFA की समतुल्यता पूछना है
    4. केवल ट्यूरिंग मशीनों से संबद्ध
    उत्तर देखें

    उत्तर: A — अनिर्णेय

    संदर्भ-मुक्त व्याकरणों हेतु भाषा-समतुल्यता अनिर्णेय है, नियमित भाषाओं/DFA हेतु संगत प्रश्न (DFA/NFA समतुल्यता का निर्णय निर्णेय है, उधार लिए GATE अभिकलन सिद्धांत अध्याय में ढका) के तीव्र विपरीत।

  6. निर्णेयता व साध्यता के बीच संबंध के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. हर NP-पूर्ण समस्या निर्णेय है
    2. किसी भी NP-पूर्ण समस्या को दक्षतापूर्वक (बहुपद-समय) निर्णेय ज्ञात नहीं है
    3. निर्णेयता व साध्यता ठीक वही गुण हैं
    4. हाल्टिंग समस्या ठीक उसी अर्थ में असाध्य है जिस अर्थ में कोई NP-पूर्ण समस्या है
    उत्तर देखें

    उत्तर: A — हर NP-पूर्ण समस्या निर्णेय है; B — किसी भी NP-पूर्ण समस्या को दक्षतापूर्वक (बहुपद-समय) निर्णेय ज्ञात नहीं है

    निर्णेयता (बिल्कुल हल-योग्य, चाहे कितना धीमे) व साध्यता (दक्षतापूर्वक हल-योग्य) पृथक रेखाएँ हैं; NP-पूर्ण समस्या प्रत्यक्ष-बल से निर्णेय है पर दक्षतापूर्वक निर्णेय ज्ञात नहीं, जबकि हाल्टिंग समस्या बिल्कुल निर्णेय ही नहीं, जो NP-पूर्णता से कड़ाई से भिन्न (व प्रबलतर) प्रकार की कठिनता है।

  7. उस गणितज्ञ का नाम बताइए जिसका विकर्णीकरण-तर्क (मूलतः वास्तविक संख्याओं को अगणनीय सिद्ध करने हेतु प्रयुक्त) संभव प्रोग्रामों से अधिक संभव समस्याएँ सिद्ध करने हेतु अनुकूलित किया गया है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: Cantor

    कैंटर का विकर्णीकरण-तर्क, मूलतः वास्तविक संख्याओं की अगणनीयता संबंधी समुच्चय-सिद्धांत परिणाम, सीधे सामान्यीकृत होकर दिखाता है कि सभी फलनों/समस्याओं का समुच्चय अगणनीय है जबकि प्रोग्राम गणनीय ही रहते हैं।

  8. विहित LR(1) पार्सिंग की तुलना में, LALR(1) पार्सिंग का सर्वोत्तम वर्णन है:

    1. वही निर्माण जिसमें सारणी छोटी करने हेतु संगत अवस्थाएँ विलीन की गई हों
    2. बिल्कुल भिन्न सिद्धांत से पूर्णतः असंबद्ध पार्सिंग तकनीक
    3. केवल नियमित भाषाओं हेतु प्रयोग करने योग्य, संदर्भ-मुक्त व्याकरणों हेतु कभी नहीं
    4. बिल्कुल कोई सारणी न रखने वाली तकनीक
    उत्तर देखें

    उत्तर: A — वही निर्माण जिसमें सारणी छोटी करने हेतु संगत अवस्थाएँ विलीन की गई हों

    LALR(1) उधार लिए GATE संकलक अभिकल्प अध्याय द्वारा पहले से गहराई से ढकी वही विहित-LR(1) यंत्रावली पर बनता है, समान क्रोड वाली अवस्थाएँ विलीन कर पार्सिंग-शक्ति में छोटी लागत पर छोटी सारणी उत्पन्न करते हुए।