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]
[2]
Roll No .......................................
AL-601 (GS)
B.Tech. VI Semester
Examination, May 2023
Grading System (GS)
Theory of Computation
Time: Three Hours
Maximum Marks : 70
Note:
- Attempt any five questions. किन्हीं पाँच प्रश्नों को हल कीजिए।
- All questions carry equal marks. सभी प्रश्नों के समान अंक हैं।
- In case of any doubt or dispute the English version question should be treated as final. किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
1. a)
What is Moore Machine? How Moore machine can be converted into Mealy Machine? Explain with the help of an example.
मूर मशीन क्या है? मूर मशीन को मीली मशीन में कैसे बदला जा सकता है? एक उदाहरण की सहायता से समझाइए।
b)
Describe how Finite automata can be called a language acceptor?
वर्णन क��ें कि परिमित ऑटोमेटा को भाषा स्वीकारता कैसे कहा जा सकता है?
2. a)
Explain briefly about the composite machine with an example.
कंपोजिट मशीन के बारे में उदाहरण सहित संक्षेप में समझाइए।
b)
Find out the Regular Expression from given DFA.
दिए गए DFA से रेगुलर एक्सप्रेशन का पता लगाए।
3. a)
What do you mean by Closure properties of regular languages? Define some important closure properties.
नियमित भाषाओं के क्लोजर गुणों से आपका क्या मतलब है? कुछ महत्वपूर्ण क्लोजर गुणों को परिभाषित करें।
b)
Obtain the regular expression for the following set:
- Set of all strings over Σ = {a,b} with exactly two a.
- L = {ax | x is divisible by 3 or 5}.
- Σ = {a,b} पर सभी स्ट्रिंग्स का सेट ठीक दो a के साथ
- L = {ax | x 3 या 5 से विभाज्य है}
4. a)
Differentiate between Context-Free Grammar and Context-Sensitive Grammar.
संदर्भ-मुक्त व्याकरण और संदर्भ-संवेदनशील व्याकरण के बीच अंतर करें।
5. a)
Write CFG for regular expression (011 + 1)*(01)*.
रेगुलर एक्सप्रेशन (011 + 1)*(01)* के लिए CFG को लिखें।
b)
Design PDA to accept the language L(G) = {ambnam | m,n ≥ 1}
L(G) = {ambnam | m,n ≥ 1} भाषा को स्वीकार करने के लिए PDA डिजाइन करें।
6. a)
Design a PDA which recognizes the set of all even length palindromes over {a, b}.
एक PDA डिजाइन करे जो {a,b} पर सभी समान लंबाई के पैलिंड्रोम के सेट को पहचानता है।
b)
What is PDA? Explain instantaneous description of PDA.
PDA क्या है? PDA के तात्कालिक विवरण की व्याख्या करें।
7. a)
Design a Turing Machine for the language L(G) = anbn n ≥ 1
भाषा (L(G) = anbn n ≥ 1) के लिए ट्यूरिंग मशीन डिजाइन करें।
b)
Explain P class problems in detail.
P वर्ग की समस्याओं को विस्तार से समझाइए।
8.
Write short note on any two of the following:
निम्नलिखित में से किन्हीं दो पर संक्षिप्त टिप्पणी लिखिए।
- NP Hard
- Petri Net Model
- Halting problem of Turing machine
- 2-way DFA