Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
CS-501 (GS)
B. Tech. V Semester
Examination, December 2025
Grading System (GS)
Theory of Computation
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.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
Explain finite automata as language acceptors and translators.
फाइनाइट ऑटोमेटा को भाषा स्वीकारक तथा अनुवादक के रूप में समझाइए।
Design a Mealy machine that outputs 1 whenever the input symbol is '1', otherwise outputs 0.
ऐसा Mealy मशीन डिज़ाइन करें जो इनपुट '1' होने पर आउटपुट 1 दे तथा अन्यथा 0 दे।
Explain deterministic and non-deterministic finite automata with examples.
उदाहरण सहित डिटरमिनिस्टिक तथा नॉन-डिटरमिनिस्टिक फाइनाइट ऑटोमेटा की व्याख्या करें।
Convert the given NDFA to an equivalent DFA:
States {q0, q1}, Alphabet {a, b}, Transitions:
δ(q0, a)={q0, q1}, δ(q0, b)={q0}, δ(q1, b)={q1}.
Final state= q1.
दिए गए NDFA को समतुल्य DFA में परिवर्तित करें:
स्टेट्स {q0, q1}, अल्फाबेट {a, b}, ट्रांजिशनः
δ(q0, a)={q0, q1}, δ(q0, b)={q0}, δ(q1, b)={q1}.
अंतिम स्टेट= q1
Explain regular expressions and Arden's theorem.
रेगुलर एक्सप्रेशन तथा आर्डन प्रमेय की व्याख्या करें।
Write a regular expression for the language over {a, b} that contains strings ending with "ab".
{a, b} पर आधारित उन सभी स्ट्रिंग्स के लिए रेगुलर एक्सप्रेशन लिखिए जो "ab" पर समाप्त होती हों।
Explain context free grammar and derivation trees.
कॉन्टेक्स्ट फ्री ग्रामर तथा डेरिवेशन ट्री की व्याख्या करें।
For the grammar S → aSb | ab, derive the string "aabb" and draw its parse tree.
ग्रामर S → aSb | ab के लिए स्ट्रिंग "aabb" व्युत्पन्न कीजिए तथा उसका पार्स ट्री बनाइए।
Explain ambiguity in grammar and methods to remove it.
ग्रामर में एम्बिगुइटी तथा उसे हटाने की विधियों की व्याख्या करें।
Convert the grammar into Chomsky Normal Form:
S → AB | a, A → a, B → b.
निम्न ग्रामर को चोम्स्की नॉर्मल फॉर्म में परिवर्तित करें:
S → AB | a, A → a, B → b
Explain pushdown automata and deterministic and non-deterministic PDAs.
पुशडाउन ऑटोमेटा तथा डिटरमिनिस्टिक एवं नॉन-डिटरमिनिस्टिक PDA की व्याख्या करें।
Design a PDA for the language L={aⁿbⁿ | n ≥ 1}.
भाषा L={aⁿbⁿ | n ≥ 1} के लिए एक PDA डिज़ाइन करें।
Explain Turing machines and techniques for their construction.
ट्यूरिंग मशीन तथा उनके निर्माण की तकनीकों की व्याख्या करें।
Design a Turing machine to accept strings over {0,1} having even number of 1's.
{0,1} पर आधारित उन सभी स्ट्रिंग्स को स्वीकार करने हेतु एक ट्यूरिंग मशीन बनाइए जिनमें 1 की संख्या सम हो।
Explain decidable, undecidable, recursive, and recursively enumerable languages.
डिसाइडेबल, अनडिसाइडेबल, रिकर्सिव तथा रिकर्सिवली एन्युमेरेबल भाषाओं की व्याख्या करें।
What is the halting problem? Explain why it is undecidable.
हॉल्टिंग समस्या क्या है? यह अनिर्णेय क्यों है, समझाइए।