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 _________
CD-501 (GS)
B.Tech., V Semester
Examination, December 2024
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)
What do you mean by closure properties of regular language? Define some important Closure properties.
(नियमित भाषा के समापन गुणों से आपका क्या तात्पर्य है? कुछ महत्वपूर्ण समापन गुणों को परिभाषित करें।)
b)
State and prove the theorem of mathematical induction.
(गणितीय प्रेरण के प्रमेय को बताओ और सिद्ध करें।)
2.
a)
Minimize the following DFA.
(निम्नलिखित DFA को न्यूनतम करें।)
b)
Explain Arden's theorem. Construct a regular expression corresponding to the automata using Arden's theorem. Write the applications of Arden's Theorem.
(आर्डन प्रमेय को समझाइए। आर्डन के प्रमेय का उपयोग ��रके ऑटोमेटा के अनुरूप एक नियमित अभिव्यक्ति का निर्माण करें। आर्डन प्रमेय के अनुप्रयोग लिखिए।)
3.
a)
Discuss Normal forms-Chomsky and Greibach Normal forms with example.
(सामान्य रूप-चॉम्स्की और ग्रीबैक सामान्य रूपों पर उदाहरण सहित चर्चा करें।)
b)
Construct context free grammars to accept the language L(G) = {an bm cn dm | n≥0, m≥0}
(भाषा को स्वीकार करने के लिए संदर्भमुक्त व्याकरण का निर्माण करें। L(G) = {an bm cn dm | n≥0, m≥0})
4.
a)
What is PDA? What are its closure properties? Draw a PDA that accepts (0i 1n | n≥0)
(PDA क्या है? इसके समापन गुण क्या हैं? एक PDA बनाओ जो (0i 1n | n≥0) स्वीकार करता हो।)
b)
Write the procedure to convert CFG to PDA and also convert the following CFG to PDA.
(CFG को PDA में बदलने की प्रक्रिया लिखें और निम्नलिखित CFG को PDA में बदलें।)
S → aABB | aA
A → aBB | a
B → bBB | a
C → a
5.
a)
Prove that there is no algorithm that determines whether an arbitrary Turing Machine halts when run with the input string 101.
(सिद्ध करें कि ऐसा कोई एल्गोरिदम नहीं है जो यह निर्धारित करता हो कि इनपुट स्ट्रिंग [101] के साथ चलाए जाने पर एक मनमाना ट्यूरिंग मशीन रुकती है या नहीं।)
b)
Construct Turing Machine (TM) to accept the language L = {0n 1n 2n | n≥0} over the alphabet, Σ = {0, 1, 2}
(भाषा को स्वीकार करने के लिए ट्यूरिंग मशीन (TM) का निर्माण करें। L = {0n 1n 2n | n≥0} वर्णमाला के ऊपर, Σ = {0, 1, 2})
6.
a)
Convert the following Mealy machine into equivalent Moore machine.
(निम्नलिखित मीली मशीन को समरूप मूर मशीन में परिवर्तित करें।)
7.
a)
Construct a finite automata for the regular expression (0+1)*(00+1)*(0+1)*
(नियमित अभिव्यक्ति (0+1)*(00+1)*(0+1)* के लिए एक परिमित ऑटोमेटा का निर्माण करें।)
b)
Explain the terms P, NP, NP complete. Give suitable example.
(P, NP, NP शब्दों को पूर्ण रूप से समझाइए। उपयुक्त उदाहरण दीजिए।)
8.
Write the short note on any two :
a)
Undecidable problem
(अनिर्णीत समस्या)
b)
Two way finite automata
c)
NFA
(NFA)
d)
Properties of Context free grammar
(किसी दो पर संक्षिप्त टिप्पणी लिखिए।)