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 : .............................
AL-601 (GS)
B.Tech. VI Semester
Examination, December 2024
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)
Design a Moore machine to determine the residue of mod 2 of the input treated as a binary string.
बाइनरी स्ट्रिंग के रूप में व्यवहार किए गए इनपुट के मॉड़ 2 के अवशेषों को निर्धारित करने के लिए एक नूर मशीन डिजाइन करें।
b)
Find an equivalent ε-NFA for the following regular expression (0 + 1)* 011.
निम्नलिखित रेगुलर एक्सप्रेशन (0 + 1)* 011 के लिए समतुल्य ε-NFA ज्ञात कीजिए।
2. a)
Convert the A-NFA to NFA.
A-NFA को NFA में बदलें।
b)
Convert the grammar {S → Abac/AbS, A → Aa/a, B → BaB/b, C → CC} Chomsky normal form.
व्याकरण {S → Abac/AbS, A → Aa/a, B → BaB/b, C → CC} को चोम्स्की normal रूप में बदलें।
3. a)
Define formally Type 0, Type 1, Type 2 and Type 3 grammar. Show the corresponding automata for each class.
औपचारिक रूप से टाइप 0, टाइप 1, टाइप 2 और टाइप 3 व्याकरण को परिभाषित करें। प्रत्येक वर्ग के लिए संबंधित ऑटोमेटा दिखाएं।
b)
Construct PDA for the language wcwᴿ where w is string of zeroes and ones.
भाषा wcwᴿ के लिए PDA की रचना करें जहाँ w शून्य और एक की श्रृंखला है।
4. a)
Derive regular expression from this Finite Automata.
इस परिनित ऑटोमेटा से रेगुलर एक्सप्��ेशन प्राप्त करें।
b)
Define regular language and regular expressions. Find regular expression for the following : Language of all string that do not end with 01.
नियमित भाषा और नियमित अभिव्यक्तियों को परिभाषित करें। निम्नलिखित के लिए रेगुलर ए��्सप्रेशन खोजें : सभी स्ट्रिंग की भाषा जो 01 पर समाप्त नहीं होती है।
5.
Construct a PDA by empty stack approach each of the following language.
निम्नलिखित में से प्रत्येक भाषा को खाली स्टैक द्वारा स्वीकार करते हुए एक PDA का निर्माण करें।
- dⁿbⁿc²ⁿ where n ≥ 1
- aⁿbᵐa where n ≠ m
6. a)
Convert to Greibach normal form. {S → AB, A → SA|AA|a, B → SB|b}
ग्रीबैक सामान्य रूप में परिवर्तित करें।
{S → AB, A → SA|AA|a, B → SB|b}
b)
Derive any two representative strings with minimum length 4 from following context free grammar.
निम्नलिखित संदर्भ मुक्त व्याकरण से न्यूनतम लंबाई 4 के साथ कोई भी दो प्रतिनिधि तार प्राप्त करें।
G = ({S, A, B}, {a, b}, P, S)
S → bA | aB
A → bAA | s | a
B → aBB | bS | b
7. a)
Design a Turing machine that accepts the language 1ⁿ 0ⁿ where n > 0.
एक ट्यूरिंग मशीन डिजाइन करें जो भाषा 1ⁿ 0ⁿ जहाँ n > 0 स्वीकार करती है।
b)
What is a Turing machine? Give the specification of a Turing machine and explain.
ट्यूरिंग मशीन क्या होती है? एक ट्यूरिंग मशीन का विवरण दीजिए तथा व्याख्या कीजिए।
8.
Write a short note (any three):
i) संक्षिप्त टिप्पणियाँ लिखें (कोई तीन)
- ii) Recursively Enumerable
- iii) GNF
- iv) Derivation Tree
- v) Mealy Machine