Save as PDF
Opens your browser print dialog — select "Save as PDF" to download.
CB-301 (GS)
B.Tech., III Semester
Examination, December 2023
Grading System (GS)
Formal Language & Automata Theory
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.
किसी भी प्रकार के संदेह अथवा विवाद की स्थिति में अंग्रेजी भाषा के प्रश्न को अंतिम माना जायेगा।
a) Find R* and R+ for the following Relation:
R = {(1, 2), (2, 3), (3, 3)}
निम्नलिखित संबंध के लिए R* और R+ ज्ञात कीजिए।
R = {(1, 2), (2, 3), (3, 3)}
b) Design the finite automata over alphabet {a, b} for the given language.
L = {w : na (w) <= 3 }
दी गई भाषा के लिए अक्षर {a, b} पर परिमित ऑटोमेटा डिजाइन करें।
L = {w : na (w) <= 3 }
a) Construct a Moore Machine that prints "a" whenever the sequence "01" is encountered in any input binary string.
एक मूर मशीन का निर्माण करें जो किसी भी इनपुट बाइनरी स्ट्रिंग में अनुक्रम "01" का सामना होने पर "a" प्रिंट करती है।
b) Check whether the given grammar is ambiguous or not. Justify your answer with examples.
S → a | abS | aAb
A → bS | aAb
जाँच करें कि दिया गया व्याकरण अस्पष्ट है या नहीं। उदाहरण सहित अपने उत्तर की पुष्टि करें।
S → a | abS | aAb
A → bS | aAb
Let G = (V, T, P, S) be a regular grammar, where
V = {S, A, B}
T = {0, 1}
S is the start symbol of grammar.
P is the set of production rules defined as:
S → 0A | 1B
A → 0A | 1
B → 1B | 0
मान लीजिए G = (V, T, P, S) एक नियमित व्याकरण है, जहाँ
V = {S, A, B}
T = {0, 1}
S व्याकरण का आरंभ सिम्बल है।
P उत्पादन नियमों का समूह है जिसे इस प्रकार परिभाषित किया गया है।
S → 0A | 1B
A → 0A | 1
B → 1B | 0
a) What is the language generated by the given grammar (L(G))?
अ) दिए गए व्याकरण (L(G)) द्वारा उत्पन्न भाषा क्या है?
b) Construct an equivalent Finite Automata for the grammar G.
ब) व्याकरण G के लिए समतुल्य परिमित ऑटोमेटा का निर्माण करें।
Convert the given grammar into Chomsky's Normal Form (CNF).
S → aXbY | ε
Y → X | ε
दिए गए व्याकरण को चॉम्स्की के सामान्य रूप (CNF) में परिवर्तित करें।
S → aXbY | ε
Y → X | ε
Write a CFG and Construct an equivalent PDA for the language:
L = {an bm cn ; where n > 0, m > 0}
also show two strings (one for accept and another one for reject case by stack operation)
एक CFG लिखें और भाषा के लिए समकक्ष PDA का निर्माण करें।
L = {an bm cn ; where n > 0, m > 0}
दो स्ट्रिंग भी दिखाएं (एक स्वीकार के लिए और दूसरा स्टैक ऑपरेशन द्वारा अस्वीकार मामले के लिए)
a) Construct a Turing Machine that accepts all combinations of a's and b's, where the number of a's in each string must be divisible by 3.
Sample Language = {aaa, bababa, bb, baabaabaa, .......}
एक ट्यूरिंग मशीन बनाइए जो a और b के सभी संयोजनो�� को स्वीकार करती है, जहाँ प्रत्येक स्ट्रिंग में a की संख्या 3 से विभाज्य होनी चाहिए।
Sample Language = {aaa, bababa, bb, baabaabaa, .......}
b) How Multi-tape Turing machine is different from Multi-head Turing Machines? Explain..
मल्टी-टेप ट्यूरिंग मशीन मल्टी-हेड ट्यूरिंग मशीनों से किस प्रकार भिन्न है? समझाइए।
a) Let A is an NP-complete (NPC) problem. B and C are two other problems known to be NP problems. If
B α A
A α C
Then, what is the C problem? (Justify your answer)
मान लीजिए A एक NP-पूर्ण (NPC) समस्या है। B और C दो अन्य समस्याएँ हैं जिन्हें NP समस्याएँ कहा जाता है। यदि
B α A
A α C
तब, फिर C समस्या क्या है? (अपने उत्तर का औचित्य सिद्ध करें)
b) How Linear Bounded Automata is different from Turing Machines? Explain with the help of a suitable example.
लीनियर बाउंडेड ऑटोमेटा ट्यूरिंग मशीनों से किस प्रक���र भिन्न है? उपयुक्त उदाहरण की सहायता से समझाइए।
Convert the given NFA to the given Epsilon-NFA.
समरुप्य DFA को दिए गए Epsilon-NFA में परिवर्तित करें।
