Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
AD-501 (GS)
B.Tech., V Semester
Examination, November 2023
Grading System (GS)
Theory of Computation
Time : Three Hours
Maximum Marks : 70
Note: i)
Answer 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)
Prove that 12 + 22 + 32 + ... n2 = \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\) using mathematical induction.
गणितीय प्रेरण का उपयोग करना।
b)
Construct a regular expression corresponding to the automata using Arden's theorem. Write the applications of Arden's Theorem.
आर्डन के प्रमेय का उपयोग करके ऑटोमेटा के अनुरूप एक नियमित अभिव्यक्ति का निर्माण करें। आर्डन प्रमेय के अनुप्रयोग लिखिए।
2.
Explain the purpose of Mealy machine and Moore machine. Write application of Mealy and Moore machine. Convert the following Mealy machine into Moore Machine.
मीली मशीन एवं मूर मशीन का उद्देश्य समझाइए। मीली एवं मूर मशीन का अनुप्रयोग क्षेत्र लिखें। निम्नलिखित मीली मशीन को मूर मशीन में बदलें।
3.
Convert epsilon-NFA to NFA. Consider the example having states q0, q1, q2, q3 and q4.
q0, q1, q2, q3 और q4 अवस्थाओं वाले उदाहरण को लेकर एप्सिलॉन-NFA को NFA में बदलें।
3. a)
What do you mean by Parsing? How left most and right most derivation helps to find out the ambiguity in a grammar?
पार्सिंग से आप क्या समझते है? सबसे ब��एँ और सबसे दाएँ व्युत्पत्ति किस प्रकार व्याकरण में अस्पष्टता का पता लगाने में मदद करती है?
b)
Obtain DFAs to accept strings of a's and b's having exactly one a.
a और b के बिल्कुल एक a वाले स्ट्रिंग को स्वीकार करने के लिए DFAs प्राप्त करें।
4. a)
Explain the Patri nets model with example.
पेट्री नेट मॉडल को उदाहरण सहित समझाइये।
b)
Design a push down automata for language L = {an bn | n >= 1}. Also check the acceptability of string "aaaabbab".
भाषा L = {an bn | n >= 1} के लिए एक पुश डाउन ऑटोमेटा डिजाइन करें। स्ट्रिंग "aaaabbab" की स्वीकार्यता भी जाँचे।
5. a)
Explain the types of Automata and prove that the Finite Automata as a language acceptor and translator.
ऑटोमेटा के प्रकारों की व्याख्या करें और सिद्ध करें कि परिमित ऑटोमेटा एक भाषा स्वीकार्ता और अनुवादक हैं।
b)
Explain Greibach and Chomsky Normal Form.
ग्रीबाक और चॉम्स्की सामान्य रूप को समझाइये।
6. a)
Apply minimization of the following DFA using Equivalence theorem.
तुल्यताप्रमेय का उपयोग करके निम्नलिखित DFA का न्यूनतमकरण लागू करें।
b)
Write given CFG for R.E (011 + 1)* (01)*.
7.
Write the short notes on following : (any two)
निम्नलिखित पर संक्षिप्त नोट्स लिखें। (कोई दो)
- Variation of Turing Machine
- Two way finite automata
- Multitape
- Halting problem of Turing machine
- ट्यूरिंग मशीन की विविधता
- दो तरफा परिमित ऑटोमेटा
- मल्टीटेप
- ट्यूरिंग मशीन के रुकने की समस्या