Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
Total No. of Questions: N
Total No. of Printed Pages: 4
Roll No. ........................................
IS-604 (B) (GS)
B.Tech. VI Semester
Examination, May 2023
Grading System (GS)
Theory of Computation
B.Tech. VI Semester
Examination, May 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) Define Moore machine. Describe the 6-tuple representation of Moore machine.
(7)
मूर मशीन को परिभाषित करें। मूर मशीन के 6-ट्यूपल प्रतिनिधित्व का वर्णन करें।
b) Consider the Moore machine shown in the below figure. Construct the transition table. What is the output for input 01010?
(7)
नीचे दी गई आकृति में दिखाई गई मूर मशीन का उपयोग करके ट्रांजिशन टेबल बनाइए। इनपु�� 01010 के लिए आउटपुट क्या होगा?
2.
a) Discuss the steps to convert the Moore machine to Mealy machine.
(7)
मूर मशीन को मीले मशीन में बदलने के चरणों की विवेचना कीजिए।
b) Construct DFA for L={w|w is in the form of 'x01y' for some strings x and y consisting of 0's and 1's}.
(7)
L={w|w के लिए DFA की रचना करें, कुछ स्ट्रिंग्स x और y के लिए 'x01y' के रूप में है जिसमें 0 और 1 हैं।}
3.
a) List out the differences between DFA and NFA.
(7)
DFA और NFA के बीच अंतर को सूचीबद्ध करें।
b) Find a DFA equivalent to NFA M=({A,B,C}, {0,1}, δ,A, {C}) δ is given by
(7)
NFA M=({A,B,C}, {0,1}, δ,A, {C}) के समतुल्य DFA ज्ञात कीजिए। δ दिया गया
| →A | {A,B} | {C} |
| B | {A} | {B} |
| © | -- | {A,B} |
4.
a) Construct a regular grammar corresponding to regular expression a(a+b)*ab.
(7)
रेगुलर एक्सप्रेशन a(a+b)*ab के अनुरूप नियमित व्याकरण का निर्माण करें।
b) Let us consider the grammar ({S,A,B}, {a,b}, P,S) that has the productions:
(7)
S→bA|aA
A→bA|a|S|a
B→aBB|bS|b
find an equivalent grammar in CNF.
A→bA|a|S|a
B→aBB|bS|b
व्याकरण ({S,A,B}, {a,b}, P,S) पर विचार करें जिसमें प्रस्तुतियाँ हैं:
S→bA|aB
A→bA|a|S|a
B→aBB|bS|b
CNF में समकक्ष व्याकरण खोजें।
A→bA|a|S|a
B→aBB|bS|b
5.
a) Consider the Context Free Grammar, G=(V,T,P,S) where V={S,A}, T={a,b}, P={S→aA, A→aA, A→a, A→bA, A→ab}. Check whether the given grammar is ambiguous or not.
(7)
प्रसंग मुक्त व्याकरण पर विचार करें, G=(V,T,P,S) जहाँ V={S,A}, T={a,b}, P={S→aA, A→aA, A→a, A→bA, A→ab} जाँचें कि दिया गया व्याकरण संदिग्ध है या नहीं।
b) Construct a PDA that accepts L={0ⁿ1²ⁿ}.
(7)
एक PDA का निर्माण करें जो L={0ⁿ1²ⁿ} को स्वीकार करता है।
6.
a) Write an algorithm to find CFG corresponding to a given PDA.
(7)
किसी दिए गए PDA क��� अनुरूप CFG खोजने के लिए एल्गोरिथम लिखें।
b) Construct CFG which accepts N(M), where M=({q₀,q₁}, {a,b}, {Z₀,Z₁}, δ,q₀,Z₀), δ is given by
(7)
CFG का निर्माण करें जो N(M) को स्वीकार करता है, जहाँ M=({q₀,q₁}, {a,b}, {Z₀,Z₁}, δ,q₀,Z₀), δ दिया गया है
δ(q₀,b,Z₀) = {(q₀,ZZ₀)}
δ(q₀,ε,Z₀) = {(q₀,ε)}
δ(q₀,b,Z₁) = {(q₀,ZZ₁)}
δ(q₁,b,Z₀) = {(q₁,ε)}
δ(q₁,a,Z₀) = {(q₀,Z₀)}
δ(q₀,ε,Z₀) = {(q₀,ε)}
δ(q₀,b,Z₁) = {(q₀,ZZ₁)}
δ(q₁,b,Z₀) = {(q₁,ε)}
δ(q₁,a,Z₀) = {(q₀,Z₀)}
7.
a) Design Turing machine to recognize the language L={0ⁿ1ⁿ0ⁿ|n >=1}.
(7)
L={0ⁿ1ⁿ0ⁿ|n >=1} भाषा को पहचानने के लिए ट्यूरिंग मशीन डिज़ाइन करें।
b) State and explain the post correspondence problem.
(7)
पोस्ट पत्राचार समस्या को बताइए और समझाइए।
8.
Write any two of the following:
(14)
a) Differences between Moore machine and Mealy machine
मूर और मीले मशीन के बीच अंतर करें।
b) Prove (1+00*1)+(1+00*1)(0+10*1)*(1+10*1) = 0*1((0+10*1)*)
सिद्ध कीजिए (1+00*1)+(1+00*1)(0+10*1)*(1+10*1) = 0*1((0+10*1)*)
c) Simplify the following grammar:
S→aA
A→$bbCC|DaA
C→abb|DD
E→aC
D→aDA
A→$bbCC|DaA
C→abb|DD
E→aC
D→aDA
निम्नलिखित व्याकरण को सरल कीजिए।
S→aA
A→$bbCC|DaA
C→abb|DD
E→aC
D→aDA
A→$bbCC|DaA
C→abb|DD
E→aC
D→aDA
d) Petrimet model
पेट्रीनेट मॉडल