नियमित व्यंजक, परिमित स्वचालित्र व नियमित भाषाएँ

कंप्यूटर विज्ञान पेपर का खंड 6, और खंड 2 से 5 की भाँति इसके लिए किसी अन्य सत्यापित पेपर का पाठ्यक्रम नहीं पढ़ा गया। यह पेपर का सर्वाधिक स्वतःपूर्ण खंड है: यह अन्य खंडों से कुछ नहीं मानता और उसके प्रश्न लगभग पूर्णतः तीन प्रकार के हैं। न्यूनतम DFA में कितनी अवस्थाएँ हैं? यह भाषा नियमित है क्या? ये दो व्यंजक वही भाषा हैं क्या? पहले हेतु सर्वाधिक उपयोगी विचार यह है कि DFA अवस्था ठीक उसकी स्मृति है जो अभी महत्व रखता है, और कुछ नहीं — अतः यदि कोई भाषा केवल a की गणना मॉड 2 तथा b की मॉड 3 की चिंता करे, तो न्यूनतम मशीन में 2 × 3 = 6 अवस्थाएँ हैं, और यदि वह यह चिंता करे कि तीन स्थान पीछे कौन-सा प्रतीक था, तो मशीन को अंतिम तीन प्रतीक याद रखने होंगे, जिससे 2³ = 8। अतः अवस्थाएँ गिनना विभेद्य स्थितियाँ गिनना है, और मिहिल–नेरोड प्रमेय उसे यथार्थ बनाती है: न्यूनतम DFA की अवस्थाओं की संख्या “कौन-से प्रत्यय इसे भाषा में पूर्ण करते हैं” के अंतर्गत मालाओं के तुल्यता-वर्गों की संख्या के बराबर है। वही प्रमेय दूसरे प्रश्न का ईमानदार उपकरण भी है, क्योंकि वह अनंत अनेक वर्ग दिखाकर सिद्ध करती है कि भाषा नियमित नहीं है — और वह पंपिंग लेम्मा से स्वच्छ उपकरण है, जो केवल खंडन ही कर सकता है। तीसरा प्रश्न दोनों मशीनें न्यूनीकृत करके तय होता है: दो नियमित व्यंजक ठीक तब तुल्य हैं जब उनके न्यूनतम DFA पुनर्नामकरण तक समान हों, जो व्यंजकों को ताकने के बजाय यांत्रिक जाँच है। अंततः, एक तथ्य तैयार रखने योग्य: NFA, DFA से अधिक शक्तिशाली नहीं हैं पर चरघातांकी रूप से छोटे हो सकते हैं, और अंत-से-तीसरा भाषा उसे प्रदर्शित करती है — NFA के रूप में चार अवस्थाएँ, न्यूनतम DFA के रूप में आठ।

अवस्था वह स्मृति है जो अभी महत्व रखता है

न्यूनतम DFA आकार, प्रत्येक मशीन न्यूनीकृत करके प्राप्त
दिए वर्णमाला पर भाषाक्या याद रखना होगान्यूनतम अवस्थाएँ
5 से विभाज्य द्विआधारी संख्याएँ, सर्वाधिक महत्वपूर्ण बिट पहलेअब तक का मान, मॉड 55
{a, b} पर: अंत से तीसरा प्रतीक a हैदेखे गए अंतिम तीन प्रतीक8 (= 2³)
{a, b} पर: a की सम संख्या तथा b की तीन का गुणजदो स्वतंत्र गणक, मॉड 2 व मॉड 36 (= 2 × 3)
{a, b} पर: 3 से विभाज्य लंबाई की मालाएँअब तक की लंबाई, मॉड 33
🧠 स्वतंत्र शर्तें गुणा होती हैं; वही शर्त नहीं
जब कोई भाषा दो ऐसी शर्तें लगाती है जो परस्पर क्रिया नहीं करतीं — a की गणना मॉड 2 तथा b की गणना मॉड 3 — तो मशीन को दोनों का अनुसरण करना पड़ता है, अतः अवस्था-गणना गुणा होती है: 6, 5 नहीं। वह गुणनफल अधिकांश अवस्था-गणना प्रश्नों के उत्तर का सबसे तेज़ मार्ग है, और वह सामान्यीकृत होता है: तीन स्वतंत्र मॉड्यूलर गणक तीन संख्याओं का गुणनफल देते हैं। परंतु नियम केवल तब टिकता है जब शर्तें वस्तुतः स्वतंत्र हों। "2 से विभाज्य तथा 3 से विभाज्य" प्रच्छन्न एकल शर्त है, 6 से विभाज्यता, और उसे 2 × 3 के बजाय 6 अवस्थाएँ उस कारण से चाहिए जो संयोगवश वही उत्तर देता है — जबकि "2 से विभाज्य तथा 4 से विभाज्य" को केवल 4 चाहिए, क्योंकि दूसरी शर्त पहली को समाहित कर लेती है। गुणा करने से पूर्व परस्पर क्रिया जाँचना ही अनुशासन है।
🎯 मिहिल–नेरोड: न्यूनतम DFA अद्वितीय क्यों है और उसे कैसे गिनें
दो मालाओं को तुल्य कहें जब कोई प्रत्यय उन्हें पृथक् न करे — प्रत्येक z हेतु xz व yz या दोनों भाषा में हों या दोनों बाहर। यह सभी मालाओं को वर्गों में विभाजित करता है, और प्रमेय कहती है कि न्यूनतम DFA में प्रति वर्ग ठीक एक अवस्था है। दो परिणाम काम करते हैं। अतः न्यूनतम DFA पुनर्नामकरण तक अद्वितीय है, और वही "ये दो व्यंजक तुल्य हैं क्या?" को यांत्रिक प्रश्न बनाता है: दोनों न्यूनीकृत करें व तुलना करें। तथा कोई भाषा नियमित है यदि और केवल यदि वर्गों की संख्या परिमित हो — अतः अनंत अनेक युग्मशः विभेद्य मालाएँ दिखाना अ-नियमितता सीधे सिद्ध करता है, बिना पंपिंग व बिना स्थिति-विश्लेषण। {aⁿbⁿ} हेतु मालाएँ a, aa, aaa, … युग्मशः अतुल्य हैं, क्योंकि aⁱ व aʲ को प्रत्यय bⁱ पृथक् करता है। वह एक पंक्ति में पूर्ण उपपत्ति है।

NFA: समान शक्ति, चरघातांकी रूप से कम स्थान

उपसमुच्चय रचना किसी भी n-अवस्था NFA को अधिकतम 2ⁿ अवस्थाओं के DFA में बदल देती है, अतः दोनों मॉडल ठीक वही भाषाएँ पहचानते हैं — अनिर्धारणवाद कोई शक्ति नहीं देता। वह आकार देता है। भाषा "अंत से तीसरा प्रतीक a है" का स्पष्ट 4-अवस्था NFA है: अनुमान लगाएँ कि वर्तमान प्रतीक वही है, फिर दो और गिनें। उसके न्यूनतम DFA को 8 अवस्थाएँ चाहिए, क्योंकि निर्धारणवादी मशीन अनुमान नहीं लगा सकती और उसे इसके बजाय अंतिम तीन प्रतीक याद रखने होंगे। यहाँ दोनों आँकड़े निकाले गए, और "अंत से k-वाँ" हेतु अंतर 2^k के रूप में बढ़ता है।

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

मुख्य बिंदु

  • DFA अवस्था ठीक उसकी स्मृति है जो अभी महत्व रखता है — विभेद्य स्थितियाँ गिनें।
  • स्वतंत्र शर्तें गुणा होती हैं: a मॉड 2 व b मॉड 3 से 6 अवस्थाएँ, 5 नहीं।
  • अंत से k-वें प्रतीक की चिंता 2^k अवस्थाएँ लेती है — तीसरे हेतु 8।
  • मिहिल–नेरोड: न्यूनतम DFA अवस्थाएँ = तुल्यता-वर्ग, अतः न्यूनतम DFA पुनर्नामकरण तक अद्वितीय है।
  • अनंत अनेक युग्मशः विभेद्य मालाएँ एक पंक्ति में अ-नियमितता सिद्ध करती हैं।
  • NFA ठीक नियमित भाषाएँ पहचानते हैं पर चरघातांकी रूप से छोटे हो सकते हैं — 8 के मुकाबले 4 अवस्थाएँ।
  • नियमित भाषाएँ सम्मिलन, संयोजन, तारा, पूरक, सर्वनिष्ठ व प्रतिलोमन के अंतर्गत संवृत हैं।
  • स्वीकारक अवस्थाएँ बदलना DFA का पूरक देता है, NFA का नहीं, क्योंकि NFA तब स्वीकार करता है जब कोई भी पथ करे।

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

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

  1. वर्णमाला {a, b} पर, उन सभी मालाओं को स्वीकारते न्यूनतम DFA में कितनी अवस्थाएँ हैं जिनका अंत से तीसरा प्रतीक a है?

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

    उत्तर देखें

    उत्तर: 8

    निर्धारणवादी मशीन नहीं जान सकती कि कौन-सा प्रतीक अंत से तीसरा निकलेगा, अतः उसे सदा अंतिम तीन प्रतीक याद रखने होंगे: 2³ = 8 अवस्थाएँ, और न्यूनीकरण पुष्टि करता है कि उनमें कोई विलीन नहीं होती। उसी भाषा का 4-अवस्था NFA है — अनुमान लगाएँ कि वर्तमान प्रतीक वही है और दो और गिनें — जो वह मानक प्रदर्शन है कि अनिर्धारणवाद शक्ति के बजाय आकार देता है। सामान्य आँकड़ा अंत से k-वें प्रतीक हेतु 2^k है, अतः पाँचवें के विषय में वही प्रश्न 32 उत्तर देगा।

  2. सर्वाधिक महत्वपूर्ण बिट पहले पढ़ते हुए, 5 से विभाज्य संख्याएँ निरूपित करती द्विआधारी मालाओं को स्वीकारते न्यूनतम DFA में कितनी अवस्थाएँ हैं?

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

    उत्तर देखें

    उत्तर: 5

    पाँच। याद रखने योग्य एकमात्र बात अब तक पढ़ा मान मॉड 5 है, क्योंकि एक और बिट पढ़ना चालू मान v को 2v या 2v + 1 कर देता है, और वह अद्यतन v पर केवल उसके शेषफल के माध्यम से निर्भर है। अतः अवस्थाएँ शेषफल 0 से 4 हैं, आरंभ व एकमात्र स्वीकारक अवस्था 0 है, और न्यूनीकरण दिखाता है कि कोई दो शेषफल विलीन नहीं होते। प्रतिरूप तुरंत सामान्यीकृत होता है: k से विभाज्यता को ठीक k अवस्थाएँ चाहिए, k कुछ भी हो, जो इसे बिना कुछ बनाए उत्तर देने योग्य प्रश्न बनाता है।

  3. {a, b} पर, a की सम संख्या तथा 3 से विभाज्य b की संख्या वाली मालाओं हेतु न्यूनतम DFA में हैं:

    1. 5 अवस्थाएँ
    2. 6 अवस्थाएँ
    3. 9 अवस्थाएँ
    4. 3 अवस्थाएँ
    उत्तर देखें

    उत्तर: B — 6 अवस्थाएँ

    दोनों शर्तें स्वतंत्र हैं — a-गणना, b-गणना के विषय में कुछ नहीं कहती — अतः मशीन को दोनों का अनुसरण करना होगा और अवस्था-गणना गुणनफल है: 2 × 3 = 6, न्यूनीकरण से पुष्ट। विकल्प A गुणा के बजाय मॉड्यूली जोड़ता है, जो सर्वाधिक सामान्य त्रुटि है। नियम साथ रखने योग्य है पर आँख मूँदकर नहीं: उसे शर्तों का वस्तुतः स्वतंत्र होना चाहिए। "लंबाई 2 से व 4 से विभाज्य" को केवल 4 अवस्थाएँ चाहिए, क्योंकि दूसरी शर्त पहली को पहले ही अंतर्निहित कर देती है, अतः गुणा करने से पूर्व परस्पर क्रिया जाँचना विधि का अंग है।

  4. n अवस्थाओं के NFA को तुल्य DFA में बदला जाता है। DFA अवस्थाओं की संख्या अधिकतम है:

    1. n
    2. n²
    3. 2ⁿ
    4. n!
    उत्तर देखें

    उत्तर: C — 2ⁿ

    2ⁿ। उपसमुच्चय रचना में DFA अवस्था NFA अवस्थाओं का समुच्चय है — वह समुच्चय जिसमें NFA वर्तमान में हो सकता है — और n-अवयवी समुच्चय के 2ⁿ उपसमुच्चय होते हैं। परिबंध केवल सैद्धांतिक नहीं, प्राप्त होता है: "अंत से तीसरा प्रतीक" भाषा का 4-अवस्था NFA है और न्यूनतम DFA 8 का, और अंत-से-k-वाँ संस्करण 2^k तक पहुँचता है। वैचारिक रूप से महत्वपूर्ण यह है कि यह केवल आकार के विषय में कथन है: दोनों मॉडल ठीक नियमित भाषाएँ पहचानते हैं, अतः अनिर्धारणवाद NFA को ऐसी भाषा कभी स्वीकारने नहीं देता जो कोई DFA न कर सके।

  5. NFA की भाषा का पूरक लेने हेतु सही प्रक्रिया है:

    1. उसकी स्वीकारक व अस्वीकारक अवस्थाएँ बदल दें
    2. DFA में बदलें, वहाँ बदलें, और आवश्यक हो तो वापस बदलें
    3. उसके सभी संक्रमण उलट दें
    4. असंभव है — NFA भाषाएँ पूरक के अंतर्गत संवृत नहीं
    उत्तर देखें

    उत्तर: B — DFA में बदलें, वहाँ बदलें, और आवश्यक हो तो वापस बदलें

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

  6. {aⁿbⁿ : n ≥ 0} नियमित नहीं है यह सिद्ध करने का सर्वाधिक स्वच्छ मार्ग यह देखना है कि:

    1. उसका कोई नियमित व्यंजक लिखा नहीं जा सकता
    2. मालाएँ a, aa, aaa, … युग्मशः विभेद्य हैं, अतः अनंत अनेक वर्ग हैं
    3. वह संदर्भ-मुक्त है
    4. वह अनंत है
    उत्तर देखें

    उत्तर: B — मालाएँ a, aa, aaa, … युग्मशः विभेद्य हैं, अतः अनंत अनेक वर्ग हैं

    मिहिल–नेरोड से कोई भाषा ठीक तब नियमित है जब तुल्यता-वर्गों की संख्या परिमित हो। यहाँ i ≠ j सहित aⁱ व aʲ को प्रत्यय bⁱ पृथक् करता है, जो पहली को भाषा में पूर्ण करता है और दूसरी को बाहर — अतः a, aa, aaa, … में प्रत्येक अपने वर्ग में है और अनंत अनेक वर्ग हैं। एक पंक्ति, कोई स्थिति-विश्लेषण नहीं। विकल्प A तर्क नहीं अपितु सिद्ध करने योग्य बात है। विकल्प C सत्य कथन है जो कुछ सिद्ध नहीं करता, क्योंकि प्रत्येक नियमित भाषा संदर्भ-मुक्त भी है। विकल्प D स्पष्टतः अपर्याप्त है — ab अनंत व पूर्णतः नियमित है।

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

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

    उत्तर: A — पूरक; B — सर्वनिष्ठ; C — क्लीन तारा; D — प्रतिलोमन

    सभी चार। सम्मिलन, संयोजन व तारा नियमित व्यंजक की परिभाषा से निःशुल्क मिलते हैं; पूरक DFA की स्वीकारक अवस्थाएँ बदलने से; सर्वनिष्ठ या गुणन रचना से या पहले दोनों पर लगे डी मॉर्गन से; और प्रतिलोमन NFA के प्रत्येक संक्रमण को उलटकर तथा आरंभ व स्वीकारक अवस्थाएँ बदलकर। यह संवृति असामान्य रूप से उदार है, और उसे देखने का कारण संदर्भ-मुक्त भाषाओं से विरोध है, जो सम्मिलन, संयोजन व तारा के अंतर्गत संवृत हैं पर सर्वनिष्ठ या पूरक के अंतर्गत नहीं। "उपरोक्त सभी" उत्तर यहाँ सही है और CFL हेतु गलत होता — वही असममिति है जिस पर अगला अध्याय बना है।

  8. दो नियमित व्यंजक तुल्य हैं यदि और केवल यदि:

    1. उनकी लंबाई समान हो
    2. उनके न्यूनतम DFA अवस्थाओं के पुनर्नामकरण तक समान हों
    3. वे वही वर्णमाला प्रयोग करें
    4. उनके NFA में अवस्थाओं की संख्या समान हो
    उत्तर देखें

    उत्तर: B — उनके न्यूनतम DFA अवस्थाओं के पुनर्नामकरण तक समान हों

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