Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Total No. of Questions: 8
[2]
[Total No. of Printed Pages: 4
Roll No
CSIT (CI)-503 (A)/IT-503 (A) (GS)
B.Tech., V Semester
Examination, November 2022
Grading System (GS)
Theory of Computation
Time: Three Hours
B.Tech., V Semester
Examination, November 2022
Grading System (GS)
Theory of Computation
Time: Three Hours
Maximum Marks: 70
Note:
i) Attempt any five questions.
किन्हीं पाँच प्रश्नों को हल कीजिए।
ii) All questions carry equal marks.
सभी प्रश्नों के समान अंक हैं।
iii) In case of any doubt or dispute the English version question should be treated as final.
किसी भी ���्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
1.
a) Compute the Regular Expression for the DFA as shown below
नीचे दिखाए गए अनुसार DFA के लिए नियमित अभिव्यक्ति की गणना करें।
नीचे दिखाए गए अनुसार DFA के लिए नियमित अभिव्यक्ति की गणना करें।
b) Design DFA for detecting 1100 Sequence with Overlap over the alphabet Σ = {0, 1}.
वर्णमाला Σ = {0, 1} पर ओवरलैप के साथ 1100 क्रम का पता लगाने के लिए DFA डिज़ाइन करें।
वर्णमाला Σ = {0, 1} पर ओवरलैप के साथ 1100 क्रम का पता लगाने के लिए DFA डिज़ाइन करें।
2.
Design a NFA that accepts the language over the alphabet, Σ = {0, 1, 2} where the decimal equivalent of the language is divisible by 4
एक NFA डिजाइन करें जो वर्णमाला पर ��ाषा को स्वीकार करता है, Σ = {0, 1, 2} जहां भाषा का दशमलव समतुल्य 4 से विभाज्य है।
एक NFA डिजाइन करें जो वर्णमाला पर ��ाषा को स्वीकार करता है, Σ = {0, 1, 2} जहां भाषा का दशमलव समतुल्य 4 से विभाज्य है।
b) Identify the language, L generated by the following grammar, G
निम्नलिखित व्याकरण G द्वारा उत्पन्न भाषा L की पहचान करें।
निम्नलिखित व्याकरण G द्वारा उत्पन्न भाषा L की पहचान करें।
G = ({S, A, B}, {a, b}, {S → aA, A → a|b|B, B → bBB|bb}, S)
3.
a) Convert the following NFA to an equivalent DFA.
निम्नलिखित NFA को एक समतुल्य DFA में बदलिए।
निम्नलिखित NFA को एक समतुल्य DFA में बदलिए।
b) Find a regular grammar that generates the language on {a, b} consisting of all strings with at most one a's and more than two b's.
एक नियमित व्याकरण खोजें जो {a, b} पर भाषा उत्पन्न करता है जिसमें सभी स्ट्रिंग्स शामिल हैं जिनमें बिलकुल ��क a और दो से अधिक b नहीं है।
एक नियमित व्याकरण खोजें जो {a, b} पर भाषा उत्पन्न करता है जिसमें सभी स्ट्रिंग्स शामिल हैं जिनमें बिलकुल ��क a और दो से अधिक b नहीं है।
4.
a) Construct context free grammars to accept the language L(G) = {an bm cp dq | n ≥ 0, m > 0} over the alphabet, Σ = {a, b, c, d}
भाषा L(G) = {an bm cp dq | n ≥ 0, m > 0} वर्णमाला के ऊपर, Σ = {a, b, c, d} को स्वीकार करने के लिए संदर्भ मुक्त व्याकरण का निर्माण करें।
भाषा L(G) = {an bm cp dq | n ≥ 0, m > 0} वर्णमाला के ऊपर, Σ = {a, b, c, d} को स्वीकार करने के लिए संदर्भ मुक्त व्याकरण का निर्माण करें।
b) Construct Non-Deterministic Pushdown Automata (NPDA) to accept the language {w wR | w starts and ends with the same symbol} over the alphabet, Σ = {0, 1}
भाषा को स्वीकार करने के लिए गैर-नियतात्मक पुशडाउन ऑटोमेटा (NPDA) का निर्माण {w wR | w एक ही प्रतीक के साथ शुरू और समाप्त होता है} वर्णमाला Σ = {0, 1} पर।
भाषा को स्वीकार करने के लिए गैर-नियतात्मक पुशडाउन ऑटोमेटा (NPDA) का निर्माण {w wR | w एक ही प्रतीक के साथ शुरू और समाप्त होता है} वर्णमाला Σ = {0, 1} पर।
5.
a) Construct Turing Machine (TM) to accept the language L = {0n 12n | n >= 0} over the alphabet, Σ = {0, 1, 2}
L = {0n 12n | n >= 0} अक्षर, Σ = {0, 1, 2} भाषा को स्वीकार करने के लिए ट्यूरिंग मशीन (TM) का निर्माण करें।
L = {0n 12n | n >= 0} अक्षर, Σ = {0, 1, 2} भाषा को स्वीकार करने के लिए ट्यूरिंग मशीन (TM) का निर्माण करें।
b) Construct corresponding CFG for the following NPDA.
निम्नलिखित NPDA के लिए संबंधित CFG का निर्माण करें।
निम्नलिखित NPDA के लिए संबंधित CFG का निर्माण करें।
6.
a) Give a Deterministic PDA that accepts {an bm : m ≥ n + 2} over the alphabet, Σ = {a, b}
नियतात्मक PDA दें जो वर्णमाला Σ = {a, b} पर {an bm : m ≥ n + 2} को स्वीकार करता है।
नियतात्मक PDA दें जो वर्णमाला Σ = {a, b} पर {an bm : m ≥ n + 2} को स्वीकार करता है।
b) Give an NPDA that simulates the following grammar (S is start symbol):
एक NPDA दें जो निम्नलिखित व्याकरण का अनुकरण करता है (S प्रारंभ प्रतीक है):
एक NPDA दें जो निम्नलिखित व्याकरण का अनुकरण करता है (S प्रारंभ प्रतीक है):
S→aAB|AAA
A→ABBIa
B→BBBIa
7.
a) Prove that the problem of determining whether for a Turing machine M there is some input string for which M halts is undecidable.
सिद्ध करें कि ट्यूरिंग मशीन M के लिए यह निर्धारित करने की समस्या है कि क्या कुछ इनपुट स्ट्रिंग है जिसके लिए M रुकता है, यह अनिर्णीत है।
सिद्ध करें कि ट्यूरिंग मशीन M के लिए यह निर्धारित करने की समस्या है कि क्या कुछ इनपुट स्ट्रिंग है जिसके लिए M रुकता है, यह अनिर्णीत है।
b) Prove that the recursive languages are closed under union, intersection, and complement.
सिद्ध करें कि पुनरावर्ती भाषाएँ संघ, प्रतिच्छेदन और पूरक के अंतर्गत बंद हैं।
सिद्ध करें कि पुनरावर्ती भाषाएँ संघ, प्रतिच्छेदन और पूरक के अंतर्गत बंद हैं।
8.
Given the following ambiguous context free grammar
निम्नलिखित अस्पष्ट संदर्भ को देखते हुए मुक्त व्याकरण
निम्नलिखित अस्पष्ट संदर्भ को देखते हुए मुक्त व्याकरण
S→Ab | aaB
A→a | Aa
B→b
i) Find the string s generated by the grammar that has two leftmost derivations. Show the derivations.
व्याकरण द्वारा उत्पन्न स्ट्रिंग s ज्ञात करें जिसमें दो वाममुखी व्युत्पत्तियाँ हैं। व्युत्पत्ति दिखाइए।
व्याकरण द्वारा उत्पन्न स्ट्रिंग s ज्ञात करें जिसमें दो वाममुखी व्युत्पत्तियाँ हैं। व्युत्पत्ति दिखाइए।
ii) Show the two derivation trees for the string S.
स्ट्रिंग S के लिए दो व्युत्पत्ति ट्री दिखाएं।
स्ट्रिंग S के लिए दो व्युत्पत्ति ट्री दिखाएं।
iii) Find an equivalent unambiguous context-free grammar.
एक समतुल्य स्पष्ट संदर्भ-मुक्त व्याकरण खोजें।
एक समतुल्य स्पष्ट संदर्भ-मुक्त व्याकरण खोजें।
iv) Give the unique leftmost derivation and derivation tree for the string s generated from the unambiguous grammar above.
उपरोक्त स्पष्ट व्याकरण से उत्पन्न स्ट्रिंग s के लिए अद्वितीय वामपंथी व्युत्पत्ति और व्युत्पत्ति ट्री दें।
उपरोक्त स्पष्ट व्याकरण से उत्पन्न स्ट्रिंग s के लिए अद्वितीय वामपंथी व्युत्पत्ति और व्युत्पत्ति ट्री दें।
******