Theory of Computation MCQ Quiz in हिन्दी - Objective Question with Answer for Theory of Computation - मुफ्त [PDF] डाउनलोड करें

विश्लेषिक इंजन: 

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

EDSAC:

• EDSAC का अर्थ इलेक्ट्रॉनिक डिले स्टोरेज ऑटोमेटिक कैलकुलेटर है।
• इसे दूसरा संग्रहित प्रोग्राम इलेक्ट्रॉनिक कंप्यूटर माना जाता है।
• इसे ग्राफिकल कंप्यूटर गेम चलाने वाला पहला कंप्यूटर भी माना जाता है।

ENIAC:

• ENIAC का अर्थ इलेक्ट्रॉनिक न्यूमेरिकल इंटीग्रेटर एंड कंप्यूटर होता है, यह पहला सामान्य उद्देश्य वाला इलेक्ट्रॉनिक कंप्यूटर था। यह पहला ट्यूरिंग-पूर्ण, डिजिटल कंप्यूटर था जो कंप्यूटिंग समस्याओं की एक पूरी श्रृंखला को हल करने के लिए रिप्रोग्राम करने में सक्षम था।

सही उत्तर विकल्प 1 है अर्थात्  विश्लेषिक इंजन

सही उत्तर आउटपुट टेप है।

Key Points 

• ट्यूरिंग मशीन एक सैद्धांतिक कम्प्यूटेशनल मॉडल है जिसमें कई प्रमुख घटक होते हैं।
• ट्यूरिंग मशीन के प्रमुख घटक हैं:
  • इनपुट टेप: एक टेप जो कोशिकाओं में विभाजित होता है, जिनमें से प्रत्येक एक सीमित वर्णमाला से एक प्रतीक रख सकता है। यह टेप इनपुट और आउटपुट दोनों के लिए उपयोग किया जाता है।
  • कण्ट्रोल यूनिट: एक सीमित अवस्था मशीन जो वर्तमान अवस्था और टेप हेड के नीचे वर्तमान प्रतीक के आधार पर ट्यूरिंग मशीन की क्रियाओं को नियंत्रित करती है।
• एक आउटपुट टेप ट्यूरिंग मशीन का एक मानक घटक नहीं है क्योंकि इनपुट टेप का उपयोग इनपुट और आउटपुट दोनों कार्यों के लिए किया जाता है।

Additional Information 

• विकल्प 1: इनपुट टेप - यह ट्यूरिंग मशीन का एक घटक है। इसका उपयोग इनपुट पढ़ने और आउटपुट लिखने दोनों के लिए किया जाता है।
• विकल्प 3: कण्ट्रोल यूनिट - यह भी ट्यूरिंग मशीन का एक घटक है। यह वर्तमान अवस्था और टेप से पढ़े जा रहे प्रतीक के आधार पर मशीन के संचालन को निर्देशित करता है।

सही उत्तर गणनीय नहीं है।

Key Points 

• हॉल्टिंग समस्या गणनीयता सिद्धांत में एक निर्णय समस्या है।
• यह पूछता है कि क्या कोई दिया गया प्रोग्राम किसी दिए गए इनपुट के लिए चलना समाप्त करेगा या हमेशा के लिए चलता रहेगा।
• एलन ट्यूरिंग ने 1936 में सिद्ध किया कि सभी संभावित प्रोग्राम-इनपुट जोड़ियों के लिए हॉल्टिंग समस्या को हल करने के लिए एक सामान्य एल्गोरिथम मौजूद नहीं हो सकता।
• नतीजतन, हॉल्टिंग समस्या गणनीय नहीं है, जिसका अर्थ है कि कोई एल्गोरिथम नहीं है जो सभी संभावित इनपुट के लिए समस्या को हल कर सकता है।

Additional Information 

• विकल्प 1: O(1) - यह स्थिर समय जटिलता को दर्शाता है, जिसका अर्थ है कि ऑपरेशन को इनपुट आकार की परवाह किए बिना समान समय लगेगा। हॉल्टिंग समस्या को स्थिर समय में हल नहीं किया जा सकता है।
• विकल्प 2: O(n) - यह रैखिक समय जटिलता को दर्शाता है, जिसका अर्थ है कि ऑपरेशन का समय इनपुट आकार के साथ रैखिक रूप से बढ़ेगा। हॉल्टिंग समस्या को रैखिक समय में हल नहीं किया जा सकता है।

एक ट्यूरिंग मशीन में निम्न शामिल हैं:

- एक परिमित-अवस्था नियंत्रण जो अवस्थाओं के किसी भी परिमित समुच्चय में हो सकता है,

- प्रकोष्ठों में विभाजित एक अनंत टेप, जिनमें से प्रत्येक में एक टेप प्रतीक हो सकता है,

- टेप प्रकोष्ठों में से एक पर स्थित एक पठन/लेखन टेप शीर्ष।

• विराम की समस्या NP-हार्ड है, NP-पूर्ण नहीं है, लेकिन अनिर्णनीय है। अतः विकल्प 2 सही है।
• हैमिल्टनी परीपथ, बिन पैकिंग, विभाजन की समस्याएं NP-पूर्ण समस्याएं हैं।

व्याकरण:

S → XY

X → aX | a

Y → aYb | ϵ

वर्णन:

X कम से कम एक a उत्पादित करता है। प्रकार {a, aa, aaa, aaaa……} का एक श्रृंखला उत्पादित करता है।

a^mbⁿ, यदि n = 0 और m = 0 है,∴ श्रंखला = ϵ जिसे दिए गए व्याकरण से उत्पादित नहीं किया जा सकता है और इसलिए विकल्प 2 गलत है। 

Y, b से पहले आने वाले a के साथ a और b { ϵ, ab, aabb, ……} की बराबर संख्या उत्पादित करता है। 

चूँकि कम से कम एक a, X द्वारा उत्पादित होता है तथा a और b की बराबर संख्या Y द्वारा उत्पादित होती है ∴ m> n और इसलिए विकल्प 1 गलत है। 

Y द्वारा उत्पादित सबसे छोटी लम्बाई वाली श्रृंखला ϵ है। a^mbⁿ में, n ≥ 0 है और इसलिए विकल्प 4 गलत है। 

{ a, aab, aaabb,………….} जो निम्न के समकक्ष है:

L = {a^mbⁿ | m > n, n ≥ 0}

S → aS | bS | ϵ 

इस ग्रामर का (a + b)* में परिणाम है 

DFA इसके लिए ग्रामर है:

आरेख

अब, एक-एक करके विकल्पों पर विचार करें:

विकल्प 1:

{aⁿb^m | n, m ≥ 0}

यहां ऑर्डर स्थिर है, यानी पहले a की कोई भी संख्या आएगी फिर b की कोई भी संख्या। यह गलत है।

विकल्प 2: 

{w ϵ {a, b} * | w a और b की समान संख्या है}

जैसा कि दिया गया ग्रामर अभिव्यक्ति उत्पन्न नहीं कर रहा है जो केवल समान संख्या में a और b उत्पन्न करता है। इसलिए, गलत है।

विकल्प 3:

{aⁿ | n ≥ 0} {bⁿ | n ≥ 0} {aⁿbⁿ | n ≥ 0}

यहां भी ऑर्डर स्थिर है। तो, यह गलत है।

विकल्प 4:

{a, b}*

यह (a + b)* के बराबर है। तो, यह सही है।

• गैर-निर्धारक पुश डाउन ऑटोमेटा (NPDA) भाषा में स्ट्रिंग की मध्य स्थिति को निर्धारित करता है और तब तक पॉपिंग करना शुरू करता है जब तक कि Z (स्टैक तत्वों का अंत) इसकी स्वीकृति को बताने के लिए पूरा नहीं हो जाता है।
• चूंकि NPDA द्वारा स्वीकार की जाने वाली भाषा ww^R में मौजूद सभी स्ट्रिंग इसलिए यह एक संदर्भ मुक्त भाषा (CFL) है।
• नियमित भाषा के गुणों से: रिवर्स, प्रत्यय, उपसर्ग, नियमित भाषा का संयोजन नियमित है।
• हर नियमित भाषा संदर्भ मुक्त भाषा है, लेकिन हर संदर्भ मुक्त भाषा एक नियमित रूप से भाषा नहीं है साथ ही wwR यह DFA, NFA या ε-NFA स्वीकार भाषा को देने के लिए संभव नहीं है। इसलिए, यह नियमित भाषा नहीं है।

संकल्पना:

एक नियमित भाषा का यूनियन और एक नियतात्मक संदर्भ मुक्त भाषा (DCFL) एक DCFL है।

व्याख्या:

कथन I: सत्य।

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} एक नियमित भाषा है और {anbn| n ≥ 0} एक DCFL है और इसलिए, वहाँ एक DCFL होगा।

कथन II: असत्य।

L DCFL है तो यह CFL भी है।

कथन III: सत्य 

L किसी भी संख्या में लुक हेड के लिए LL(k) नहीं हो सकता है। LL(k) निर्णायक रूप से यह भेद नहीं कर सकता है कि पार्स की जाने वाली स्ट्रिंग aⁿ से है या anbn से है। दोनों का एक सामान्य उपसर्ग है।

कथन I: असत्य है

यदि L₁ ∪ L₂ नियमित है, तो न तो L₁ और न ही L₂ को नियमित होने की आवश्यकता है।

उदाहरण:

मान लें कि L1= {an bn, n ≥ 0} वर्णमाला {a, b} के ऊपर और L₂ L₁ के पूरक हैं।

न तो L₁ और न ही L₂ नियमित (दोनों DCFL हैं) है लेकिन L1 ∪ L2= {an bn} ∪ {an bn}c = (a + b)*  नियमित है।

कथन  II: असत्य है नियमित भाषाओं का अनंत यूनियन नियमित नहीं है।

उदाहरण:

दिए गए वर्णमाला {a, b}।

L₁= {ε}

L₂= {ab}

L₃= {aabb}

L₄= {aaabbb}

:

:

L = L₁ ∪ L₂ ∪ L₃ ∪ L₄ …

उपरोक्त में से प्रत्येक नियमित है लेकिन उनका अनंत यूनियन L1= {an bn, n ≥ 0} देता है जो नियमित नहीं बल्कि DCFL है।

नोट:

सभी विकल्पों पर एक-एक करके विचार करें:

1) (0 + 1) *0011 (0 + 1)* + (0 + 1) *1100 (0 + 1)*

यह केवल उन स्ट्रिंग पर विचार करता है जिनमें या तो 0011 या 1100 सबस्ट्रिंग के रूप में हैं। तो, यह गलत है।

2) (0 + 1) *(00(0 + 1)*11 + 11 (0 + 1)*00) (0 + 1)*

इसमें सभी बाइनरी स्ट्रिंग्स का सेट होता है जिसमें लगातार दो 0 और 1 होते हैं।

3) (0 + 1) *00 (0 + 1)* + (0 + 1) *11 (0 + 1)*

इस सेट में केवल वे स्ट्रिंग हैं जिनमें या तो 00 या 11 सबस्ट्रिंग के रूप में हैं, लेकिन सभी स्ट्रिंग्स शामिल नहीं हैं जिनमें लगातार दो 0 और 1 हैं।

4) 00 (0 + 1) *11 + 11 (0 + 1) *00

यह उन स्ट्रिंग्स का प्रतिनिधित्व करता है जो क्रमशः 00 या 11 से शुरू होती हैं और 11 या 00 के साथ समाप्त होती हैं। तो, यह गलत है।

विकल्प (2) में उल्लिखित समस्या संदर्भ-मुक्त व्याकरण (CFG_S) के लिए अस्पष्टता समस्या अनिर्णनीय है।

व्याख्या:-

व्याकरण की अस्पष्टता अनिर्णनीय है, अर्थात व्याकरण की अस्पष्टता को दूर करने के लिए कोई विशेष एल्गोरिथम नहीं है,  अस्पष्ट व्याकरण के कुछ उदाहरण यहां दिए गए हैं:

• S → aS | Sa | €
• E → E + E | E*E | id
• A → AA | (A) | a

 Additional Information

FSAS के लिए तुल्यता समस्या:- एक स्वचालन एक मशीन है जिसमें स्थितियों की एक सीमित संख्या होती है। किन्हीं दो स्वचालन को समतुल्य कहा जाता है यदि दोनों एक ही स्ट्रिंग के समान सेट को स्वीकार करते हैं।

FSAS के लिए परिमितता समस्या: - परिमितता समस्या (भी CFG_S के लिए) FSAs के लिए निर्णनीय है क्योंकि हमें केवल लूप DFA की जांच करने की आवश्यकता है।

CFGS के लिए सदस्यता समस्या: एक सेट के लिए सदस्यता समस्या यह तय करने की समस्या है कि दो संभावित तत्वों में से कौन सा उस सेट से संबंधित होने की अधिक संभावना है। दूसरे शब्दों में, सदस्य को गैर-सदस्य से अलग करने के लिए दो तत्व दिए गए हैं जिनमें से कम से कम एक सेट में है।

संकल्पना:

परिमित अवस्था स्वचलप्ररूप एक मशीन है जिसका उपयोग कंप्यूटर क्रमादेश और अन्य अनुक्रमिक तर्कों को हल करने के लिए किया जा सकता है और एक निश्चित समय में अवस्थाओं की सीमित संख्या होती है। एक परिमित अवस्था मशीन में 6 टपल होते हैं।

व्याख्या:

दो परिमित अवस्था मशीनों को समतुल्य कहा जाता है यदि वे टोकन के एक ही समुच्चय को पहचानते हैं।

दो स्वचलप्ररूप M1 और M2 पर विचार कीजिए, इन्हें एक निवेश अनुक्रम के लिए समतुल्य कहा जाता है यदि वे समान निर्गम परिणाम उत्पन्न करते हैं।

उदहारण:

नियमित व्यंजक: baa*b

NFA: M1

NFA में अवस्थाओं की संख्या: 4

DFA: M2

DFA में अवस्थाओं की संख्या: 5

दो परिमित स्वचलप्ररूपों के ऊपर विभिन्न अवस्थाओं और किनारों की संख्या होती है, लेकिन वे समकक्ष होते हैं।

उन्हें समकक्ष तभी कहा जाता है जब वे एक ही नियमित भाषा (टोकन का एक ही समुच्चय) स्वीकार करते हैं, चाहे उनके पास अलग-अलग अवस्थाओं या किनारों की संख्या हो।

संकल्पना:

S → aSa | bSb | a | b {a, b, aaa, bbb, aba, bab, abbba, ababa,….) जैसे स्ट्रिंग्स उत्पन्न करता है जो सभी विषम लंबाई वाले पैलिंड्रोम का सेट है।

विषम लंबाई के पैलिंड्रोम का उदाहरण.

स्ट्रिंग: ababa

विकल्प 1: गलत

स्ट्रिंग: "aa" (स्वीकृत नहीं)

एक ही प्रतीक के साथ शुरू और समाप्त होता है लेकिन दिए गए व्याकरण द्वारा स्वीकार नहीं किया जाता है

विकल्प 2 और 4: गलत

स्ट्रिंग: "aa" (स्वीकृत नहीं)

अवधारणाएं:

संचालन जिसके तहत प्रसंग मुक्त भाषा बंद नहीं है: प्रतिच्छेदन, पूरकता, सेट अंतर

संचालन जिसके तहत प्रसंग मुक्त भाषा बंद है: संघ, क्लेन क्लोजर और श्रृंखलन ।

नियमित भाषा के साथ प्रतिच्छेदन के तहत प्रसंग मुक्त भाषा बंद है।

व्याख्या:

L1 एक नियमित भाषा है और L2 एक प्रसंग-मुक्त भाषा है।
प्रत्येक नियमित भाषा प्रसंग-मुक्त भाषा है।

विकल्प 1: प्रसंग-मुक्त भाषा

\({L_1}.{L_2}\) यह प्रसंग-मुक्त भाषा है क्योंकि यह श्रृंखलन  के तहत बंद है।

विकल्प 2: प्रसंग-मुक्त भाषा

L1 ∪ L2 यह प्रसंग-मुक्त भाषा है क्योंकि यह संघ के तहत बंद है।

विकल्प 3:  प्रसंग मुक्त भाषा

\({L_1} \cap \;{L_2}\) यह प्रसंग-मुक्त भाषा है क्योंकि नियमित भाषा के साथ प्रतिच्छेदन के तहत प्रसंग-मुक्त भाषा बंद है।

विकल्प 4:   प्रसंग-मुक्त भाषा नहीं हो सकती है

L1 - L2 यह प्रसंग-मुक्त भाषा नहीं हो सकती है क्योंकि यह पूरक के तहत बंद नहीं है।