About this question paper
This is the previous year question paper of CS Theory of Computation and Compiler Design (MSc) (Semester 3) conducted by Atal Bihari Vajpayee Vishwavidyalaya, Bilaspur (Dec 2020). Practising it helps you understand the exam pattern, important questions and marks distribution of your university.
How to prepare with this paper
- पूरा पेपर एक बार पढ़ें और जो प्रश्न आपको आते हैं उन पर निशान लगाएँ।
- देखें कि हर प्रश्न सिलेबस की किस इकाई से है — जो इकाइयाँ बार-बार आती हैं, वही सबसे ज़रूरी हैं।
- बिना नोट्स देखे 3 घंटे में पेपर हल करें, फिर अपनी किताब से उत्तर मिलाएँ।
- इसी विषय के दूसरे वर्षों के पेपर भी डाउनलोड करें और दोहराए गए प्रश्न ढूँढें।
Questions in this paper (text version)
यह टेक्स्ट मूल PDF से लिया गया है ताकि आप इसे जल्दी पढ़ और खोज सकें। सूत्र, चित्र और हिंदी टेक्स्ट सही न दिखें तो ऊपर दी गई PDF देखें।
Paper-l
THEORY OF COMPUTATION AND COMPILER DESIGN
Time : Three Hoursl [Maximum Marks :80
Minimum Pass Marks : 29
Note : Answer from both the Sections as directed. The figures in the right-hand margin indicate marks.
l. Answer the
(a) Wtricn at the following Ianguage is not context free?
(b) Language accepted by a push down automata is.....'.'
(c) Recursive descant parser is a type at...".....
(d) Which at the following is not a part as 5 type finite automata?
(g) Which is the most suitable data structure to represent the derivation is compiler?
0 Post correspondence problem is.
(iii) Not a decision problem (iv) None at the mentioned
0 Which of the fotlowing does not belong to the closure properties as NP class?
(a) Write the formal definition at NFA.
(n) Write the process at converting finite automata to rcgular Grammar'
12x5=60
Ansrver all questions.
3. Construct the regular expres ion from the given automata.
Construct finite automata that accept binary number divisible by 3.
4. What is push down automata? Design the push down automata that accept the
following language,
OR > 1, n > 0} by final state.
5, Explain Turing machine in detail.
6. What is parser? Explain deferent types at parsing with suitable example.
What are LR parsers? Explain with suitable example.
7. What is peephole optimization? Explains its use with suitable example.
Explain the issue at designing the code generator.