Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Total No. of Questions : 8
Total No. of Printed Pages : 4
Roll No.............
CS/SD-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) Assume missing data, if any, suitably.
यदि कोई डाटा निर्मित हो तो उपयुक्त मान लें।
iv) In case of any doubt or dispute the English version question should be treated as final.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जावेगा।
[2]
1.
a) What is a DFA machine? Design a deterministic finite automata machine over the alphabet set {0, 1}, accepting all strings starting and ending with different alphabet. 8
DFA मशीन क्या है? वर्णमाला सेट {0, 1} पर एक डेटरमिनिस्टिक फाइनाइट ऑटोमेटा मशीन डिजाइन करें, जो विभिन्न वर्णमाला के साथ शुरू और समाप्त होने वाली सभी स्ट्रिंग्स को स्वीकार करती है?
b) Define finite-automata machine mathematically and explain its types. 6
Finite-automata machine को गणितीय रूप से परिभाषित करें तथा इसके प्रकारों की व्याख्या करें।
2.
a) Consider the following grammar for list structures: 6
S → aλ/(T)
T → T,S/S
Find left most derivation, right most derivation and parse tree for the string ((a,a),a),a).
सूची संरचनाओं के लिए निम्नलिखित ग्रामर पर विचार करें:
S → aλ/(T)
T → T,S/S
दी गई स्ट्रिंग ((a,a),a),a) के लिए लेफ्ट मोस्ट डेरिवेशन, राइट मोस्ट डेरिवेशन और पार्स ट्री प्���ाप्त करें।
b) Write the differences between Mealy and Moore machine. Convert the given Moore machine into its equivalent Mealy machine. 8
मीली और मूर मशीन के बीच अंतर लिखिए। दी गई मूर मशीन को उसके समतुल्य मीली मशीन में परिवर्तित करें।
3.
a) Discuss about the Chomsky hierarchy of languages with their grammar constraints rules and corresponding automata for each class. 8
भाषाओं के चॉम्स्की पदानुक्रम के बारे में उनके व्याकरण संबंधी नियमों और प्रत्येक वर्ग के लिए संबंधित ऑटोमेटा के साथ चर्चा करें।
[3]
b) Define the regular expression. Find the regular expression for the given DFA machine. 6
रेगुलर एक्सप्��ेशन को परिभाषित करें। दी गई DFA मशीन के लिए रेगुलर एक्सप्रेशन खोजें।
4.
a) Find a reduced Grammar equivalent to Grammar G, having Production rules P? 8
P : {S→AC/B, A→a, C→c/BC, E→aA/c}
P उत्पादन नियमों वाले ग्रामर G के समतुल्य एक संक्षिप्त ग्रामर बनाएँ।
P : {S→AC/B, A→a, C→c/BC, E→aA/c}
b) Construct the PDA accepting the language { (ab)ⁿ : n≥1 } by empty stack. 6
खाली स्टैक द्वारा भाषा { (ab)ⁿ : n≥1 } को स्वीकार करते हुए PDA का निर्माण करें।
5.
a) Minimize the DFA using Myhill-Nerode Theorem. 8
Myhill-Nerode प्रमेय का उपयोग करके DFA को मिनिमाइज क��ें।
6.
a) Convert the grammar S→AB, A→BS/b, B→SA/a into Greibach normal form. 6
ग्रामर S→AB, A→BS/b, B→SA/a को ग्रेबैक सामान्य रूप में बदलें।
b) Explain the different models of the Turing machines. 6
ट्यूरिंग मशीनों के विभिन्न मॉडलों की व्याख्या करें।
Show that L = {aⁿbⁿcⁿ|n≥1} is not a context-free language. 8
दिखाएँ कि L = {aⁿbⁿcⁿ|n≥1} एक कॉन्टेक्स्ट-फ्री लैंग्वेज नहीं है।
7.
a) Explain the difference between tractable and intractable problems with examples. 7
उदाहरण सहित ट्रैक्टेबल और इंट्रैक्टेबल समस्याओं के बीच अंतर स्पष्ट करें।
b) Is NPDA (non-deterministic PDA) and DPDA (deterministic PDA) equivalent or not? Illustrate with an example. 7
क्या NPDA (नॉन-डिटरमिनिस्टिक PDA) और DPDA (डिटरमिनिस्टिक PDA) समकक्ष हैं? एक उदाहरण देकर स्पष्ट करें।
8.
a) Explain P and NP problems with examples. 4
P और NP समस्याओं को उदाहरण सहित समझाइए।
b) Write a short notes on the following: 10
निम्नलिखित पर संक्षिप्त नोट्स लिखें:
i) Universal Turing machine
ii) Post Correspondence Problem