जब हामीसँग गैर-निर्धारित मेसिनमा दुई वा बढी स्वीकार्य मार्गहरू हुन्छन्, हामी कुन छनौट गर्छौं र हामीले कुन मापदण्ड प्रयोग गर्न सक्छौं?
कम्प्युटेशनल जटिलता सिद्धान्तको दायरामा, विशेष गरी सीमित राज्य मेसिनहरूको अध्ययनमा, गैर-निर्धारणवादको अवधारणाले महत्त्वपूर्ण भूमिका खेल्छ।
गैर-निर्धारित सीमित राज्य मेसिनहरू (NFSMs) सैद्धान्तिक मोडेलहरू हुन् जसले कुनै पनि राज्यमा धेरै स्वीकार्य मार्गहरू लिन अनुमति दिन्छ। तर, यस्तो परिस्थितिको सामना गर्दा, प्रश्न उठ्छ: कुन बाटो रोज्नुपर्छ?
यो प्रश्नले NFSM मा "स्वीकृति" को धारणा र निर्णय गर्न प्रयोग गर्न सकिने मापदण्डलाई छुन्छ।
छनोट प्रक्रिया बुझ्नको लागि, हामी पहिले NFSMs मा गैर-निश्चयवाद को प्रकृति अन्वेषण गरौं। deterministic सीमित राज्य मेशिनहरू (DFSMs) को विपरीत, NFSMs सँग प्रत्येक राज्यमा प्रत्येक सम्भावित इनपुट प्रतीकको लागि एक अद्वितीय संक्रमण छैन। यसको सट्टा, तिनीहरूले एउटै इनपुट प्रतीकको लागि बहु ट्रान्जिसनहरूको अस्तित्वको लागि अनुमति दिन्छ। यो विशेषताले एउटै राज्यबाट पछ्याउनको लागि धेरै मार्गहरू हुने सम्भावनालाई निम्त्याउँछ, सम्भावित रूपमा विभिन्न परिणामहरू निम्त्याउँछ।
यस्तो अवस्थाको सामना गर्दा, NFSMs ले सबै सम्भावित मार्गहरू एकैसाथ अन्वेषण गर्न "शाखा" भनिने संयन्त्र प्रयोग गर्दछ। यसको मतलब मेसिनले आफैंको धेरै प्रतिलिपिहरू सिर्जना गर्दछ, प्रत्येकले फरक मार्ग पछ्याउँछ। नतिजाको रूपमा, NFSM लाई रूख जस्तो संरचनाको अन्वेषणको रूपमा देख्न सकिन्छ, जहाँ प्रत्येक शाखाले फरक गणना मार्ग प्रतिनिधित्व गर्दछ। यो शाखा प्रविधि NFSMs र तिनीहरूको कम्प्युटेसनल जटिलताको विश्लेषणमा आधारभूत छ।
अब, हामी मापदण्डलाई विचार गरौं जुन धेरै स्वीकार्य व्यक्तिहरू मध्ये एक विशेष मार्ग छनौट गर्न प्रयोग गर्न सकिन्छ। एक साझा दृष्टिकोण NFSM मा "स्वीकृति" को अवधारणालाई विचार गर्नु हो। स्वीकृति भनेको मेसिनद्वारा दिइएको इनपुटलाई मान्य मानिन्छ वा होइन भनेर निर्धारण गर्ने अवस्थालाई जनाउँछ। NFSMs मा, स्वीकृतिलाई दुई मुख्य तरिकामा परिभाषित गर्न सकिन्छ: "अन्तिम अवस्था द्वारा स्वीकृति" र "खाली स्ट्याक द्वारा स्वीकृति।"
अन्तिम अवस्थाद्वारा स्वीकृति तब हुन्छ जब, सम्पूर्ण इनपुट स्ट्रिङ उपभोग गर्दा, NFSM अन्तिम अवस्थाको रूपमा तोकिएको अवस्थामा समाप्त हुन्छ। यो मापदण्डले अन्तिम अवस्थातिर लैजाने कम्तिमा एउटा गणना मार्ग अवस्थित छ भने मेसिनले इनपुट स्वीकार गर्छ भन्ने संकेत गर्छ। यसको विपरित, यदि कुनै पनि मार्गले अन्तिम स्थितिमा पुग्दैन भने, इनपुट अस्वीकार गरिन्छ।
अर्कोतर्फ, एनएफएसएमहरूले स्ट्याकलाई अतिरिक्त कम्पोनेन्टको रूपमा समावेश गर्दा, खाली स्ट्याकद्वारा स्वीकृति सान्दर्भिक हुन्छ। यस परिदृश्यमा, स्वीकृति तब हुन्छ जब इनपुट स्ट्रिङ पूर्ण रूपमा प्रशोधन हुन्छ, र स्ट्याक खाली हुन्छ। अन्तिम अवस्था द्वारा स्वीकृति जस्तै, यदि त्यहाँ कम्तिमा एउटा गणना मार्ग छ जुन खाली स्ट्याकमा परिणाम हुन्छ, इनपुट स्वीकार गरिन्छ; अन्यथा, यो अस्वीकृत छ।
यी मापदण्डहरूलाई ध्यानमा राख्दै, एक गैर-निर्धारित मेसिनमा बहु स्वीकार्य व्यक्तिहरू बीचको विशिष्ट मार्गको चयनलाई स्वीकृति सर्तहरूलाई प्राथमिकता दिएर निर्धारण गर्न सकिन्छ। उदाहरणका लागि, यदि अन्तिम अवस्थाद्वारा स्वीकृति प्राथमिक मापदण्ड हो भने, मेसिनले अन्य सम्भावित मार्गहरूको पर्वाह नगरी अन्तिम अवस्थातर्फ लैजाने बाटो रोज्नेछ। यसको विपरित, यदि खाली स्ट्याक द्वारा स्वीकृति प्राथमिक मापदण्ड हो भने, मेसिनले खाली स्ट्याकमा परिणाम हुने मार्गलाई प्राथमिकता दिनेछ।
यो नोट गर्न महत्त्वपूर्ण छ कि NFSM मा मार्ग छनोटले मेसिनको कम्प्युटेसनल शक्तिलाई असर गर्दैन। छनौट गरिएको मार्गको बाबजुद, NFSM ले अझै पनि दिइएको इनपुटको लागि कुनै पनि अन्य NFSM जस्तै भाषाहरूको समान सेट पहिचान गर्न सक्छ। चयन प्रक्रियाले निर्दिष्ट मापदण्डको आधारमा इनपुटको स्वीकृति वा अस्वीकार मात्र निर्धारण गर्दछ।
जब एक गैर-निर्धारित मेसिनमा धेरै स्वीकार्य मार्गहरूको सामना गरिन्छ, मार्गको छनोट स्वीकृति अवस्थाहरूलाई प्राथमिकता दिएर निर्धारण गर्न सकिन्छ, जस्तै अन्तिम अवस्थाद्वारा स्वीकृति वा खाली स्ट्याकद्वारा स्वीकृति। छनोट प्रक्रियाले मेसिनको कम्प्युटेसनल शक्तिलाई असर गर्दैन तर इनपुट स्वीकृत वा अस्वीकार गरिएको छ कि छैन भनेर प्रभाव पार्छ।
अन्य भर्खरका प्रश्न र उत्तरहरू सम्बन्धमा EITC/IS/CCTF कम्प्युटेशनल जटिलता सिद्धान्त आधारभूत:
- ATM को अनिर्णयताको प्रदर्शनमा पुनरावृत्ति प्रमेयको भूमिका के हो?
- प्यालिन्ड्रोमहरू पढ्न सक्ने PDA लाई विचार गर्दा, के तपाईं स्ट्याकको विकासको बारेमा विस्तृत रूपमा बताउन सक्नुहुन्छ जब इनपुट, पहिलो, प्यालिन्ड्रोम हो, र दोस्रो, प्यालिन्ड्रोम होइन?
- गैर-निर्धारित PDA लाई विचार गर्दा, राज्यहरूको सुपरपोजिसन परिभाषाद्वारा सम्भव छ। यद्यपि, गैर-निर्धारित PDA सँग एउटा मात्र स्ट्याक छ जुन एकै पटक धेरै राज्यहरूमा हुन सक्दैन। यो कसरी सम्भव छ?
- नेटवर्क ट्राफिक विश्लेषण गर्न र सम्भावित सुरक्षा उल्लङ्घनहरू संकेत गर्ने ढाँचाहरू पहिचान गर्न प्रयोग गरिने PDAs को उदाहरण के हो?
- एउटा भाषाभन्दा अर्को भाषा बढी शक्तिशाली छ भन्ने अर्थ के हो?
- के सन्दर्भ-संवेदनशील भाषाहरू ट्युरिङ मेसिनद्वारा चिन्न सकिन्छ?
- भाषा U = 0^n1^n (n>=0) किन गैर-नियमित छ?
- कसरी '1' प्रतीकहरूको संख्याको साथ बाइनरी स्ट्रिङहरू पहिचान गर्ने FSM परिभाषित गर्ने र इनपुट स्ट्रिङ 1011 लाई प्रशोधन गर्दा के हुन्छ भनेर देखाउने?
- कसरी nondeterminism ले संक्रमण कार्यलाई असर गर्छ?
- के नियमित भाषाहरू परिमित राज्य मेसिनहरूसँग बराबर छन्?
EITC/IS/CCTF कम्प्युटेशनल जटिलता सिद्धान्त आधारभूत मा थप प्रश्न र उत्तरहरू हेर्नुहोस्