Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Roll No
AI/AL-601 (GS)
B.Tech., VI Semester
Examination, June 2025
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) In case of any doubt or dispute the English version question should be treated as final.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
1.
a)
Define finite automata and list the features of finite automata with an example.
परिमित ऑटोमेटा को परिभाषित करें और एक उदाहरण के साथ परिमित ऑटोमेटा की विशेषताओं को सूचीबद्ध करें।
7
b)
Design a finite automata with Sum = {0,1} accepts those strings which starts with 1 and ends with 0.
Sum = {0,1} के साथ एक परिमित ऑटोमेटा डिजाइन करें उन स्ट्रिंग को स्वीकार करता है जो 1 से शुरू होत�� है और 0 के साथ समाप्त होता है।
7
2.
a)
Differentiate between Mealy and Moore machines with a suitable example.
एक उपयुक्त उदाहरण के साथ मिली और मूर मशीनों के बीच अंतर करें।
7
b)
Design a regular expression for the following DFA.
नि���्नलिखित DFA के लिए एक नियमित अभिव्यक्ति डिजाइन करें।
7
3.
Consider the following NFA with epsilon:
निम्नलिखित NFA पर विचार करें।
i)
Compute the ε-closure of each state.
प्रत्येक स्थिति के ε-क्लोजर की गणना करें।
4
ii)
Give all the strings of length 4 or less accepted by the automation.
इस स्वचलन द्वारा स्वीकार किए गए लंबाई 4 या उससे कम के सभी तार दीजिए।
4
iii)
Convert the automation to DFA.
स्वचलन को DFA में बदलें।
6
4.
a)
Show that the languages L={0n1n | n ≥ 1} is deterministic context free language.
दिखाये कि भाषाएँ L={0n1n | n ≥ 1} नियतात्मक संदर्भ मुक्त भाषा है।
7
b)
Define parse tree and construct a parse tree for the string 'abaabb' from the following given grammar.
S→AS/B
A→aA/ε
B→bB/ε
पार्स ट्री को परिभाषित करें और निम्नलिखित दिए गए व्याकरण से स्ट्रिंग 'abaabb' के लिए एक पार्स ट्री का निर्माण करें।
7
5.
a)
Convert the given CFG into GNF:
S→AB/AAB/BA/AB
A→aA/a
B→bB/b
दिए गए CFG को GNF में परिवर्तित करें।
7
b)
Define pushdown automata and explain its model with a neat sketch.
पुशडाउन ऑटोमेटा को परिभाषित करें और एक साफ स्केच के साथ अपने मॉडल की व्याख्या करें।
7
6.
a)
Construct a PDA for the given language L={WWR | W ∈ {a,b}*}.
दी गई भाषा L={WWR | W ∈ {a,b}*} के लिए एक PDA का निर्माण करें।
7
b)
Convert the following grammar into PDA which accepts the same language by empty stack.
S→0S1/A
A→ε
निम्न व्याकरण को PDA में बदलें जो खाली स्टैक द्वारा ही भाषा को स्वीकार करता है।
7
7.
a)
Design a Turing machine over {0, 1} for the language L={W/W is a multiple of 3}.
भाषा L={W/W is a multiple of 3} के लिए {0, 1}पर एक ट्यूरिंग मशीन डिजाइन करें।
7
b)
Find whether the post correspondence problem P={{ba, bab}, {ab, bb}, {b, a}} has a match? Explain in detail.
पता करें कि पोस्ट कॉरेस्पोंडेंस प्रॉब्लम P={{ba, bab}, {ab, bb}, {b, a}} का मैच है? विस्तार से व्याख्या करें।
7
8.
Write a short note on any two of the following
14
a)
Arden's theorem
आर्डन का प्रमेय
b)
Chomsky hierarchy of the grammar
व्याकरण का चॉम्स्की पदानुक्रम
c)
NPDA
NPDA
d)
N-P Complete problem
N-P पूर्ण समस्या