Download Original PDF

Get the official Barkatullah University print version scanned document.

🤝 Help Your Juniors!

Have previous year question papers that aren't on our website? Help the next batch of students by sending them to us! With your consent, we will proudly feature your name as a Top Contributor on our platform.

Submit Papers 📩

ST-486

M.Sc. (REG./PVT./ATKT) Examination, 2025

(Second Semester)

MATHEMATICS

Paper-V(i)

Advanced Discrete Mathematics-II

Time : 3 Hours] [Maximum Marks :

Reg. : 85

Pvt. : 100

नोट : सभी तीनों खण्डों से प्रश्नों के निर्देशानुसार उत्तर दीजिए । अंकों का विभाजन खण्डों के साथ दिया गया है ।

Attempt questions of all three Sections as directed. Distribution of marks is given with Sections.

खण्ड 'अ'

Section A

(वस्तुनिष्ठ प्रश्न)

(Objective Type Questions)

नोट : सभी प्रश्नों के उत्तर दीजिए ।

Attempt all questions.

10×1½=15

सही उत्तर का चयन कीजिए :

Choose the correct answer :

(i)

निर्देशित द्री के मूल का स्तर है :

The level of the root of a directed tree is :

(अ) 1

(a) 1

(ब) 0

(b) 0

(स) 2

(द) उपयुक्त में से कोई नहीं

(d) None of the above

(ii)

यदि डायग्राफ के लिए आसन्नता आव्यूह है:

If the adjacency matrix for a digraph is :

तो कुल संख्या शीर्ष v₁ से v₂ तक के पथों की है :

Then total no. of paths from vertex v₁ to v₂ is :

(अ) 1

(a) 1

(ब) 2

(b) 2

(स) 3

(द) 0

(d) 0

(iii)

एक ग्रामर G जिसके प्रोडक्शन पर कोई प्रतिबंध न है, उसे कहा जाता है :

A grammar G which has no restriction on its production is called :

(अ) टाइप-शून्य ग्रामर

(a) Type-zero grammar

(ब) टाइप-1 ग्रामर

(b) Type-1 Grammar

(स) टाइप-2 ग्रामर

(द) उपयुक्त में से कोई नहीं

(d) None of the above

(iv)

यदि किसी निर्देशित वृक्ष में प्रत्येक नोड को आउट डिग्री m या o के बराबर है, तो वृक्ष को कहा जाता है :

If in a directed tree the out degree of every node is equally to m or o the tree is called :

(अ) m-रे वृक्ष

(a) m-ray tree

(ब) शून्य-रे वृक्ष

(b) zero-ray tree

(स) पूर्ण-m रे वृक्ष

(द) पूर्ण वृक्ष

(d) complete tree

(v)

एक स्ट्रिंग α को परिमित स्वचालित M = (Q, Σ, δ, q₀, F) द्वारा स्वीकार किया जाता है :

A string α is said to be accepted by a finite automation M = (Q, Σ, δ, q₀, F) :

(अ) δ(q₀, α) = α

(a) δ(q₀, α) = α

(ब) δ(q₀, α) = q₀

(b) δ(q₀, α) = q₀

(स) δ(q₀, α) = P

(द) उपयुक्त में से कोई नहीं

(d) None of the above

(vi)

मीले मशीन में यदि इनपुट स्ट्रिंग की लम्बाई n है तो आउटपुट स्ट्रिंग की लम्बाई होगी :

In a Mealy machine if the input string is of length n the output string is of the length :

(अ) n

(a) n

(ब) n + 1

(b) n + 1

(स) n - 1

(द) 2n

(d) 2n

(vii)

नियतात्मक और गैर-नियतात्मक ऑटोमेटा के बीच अंतर केवल निम्न में है :

The difference between the deterministic and non-deterministic automata is only in :

(अ) इनपुट का सेट

(a) Set of inputs

(ब) अवस्थाओं का सेट

(b) Set of states

(स) संक्रामक फंक्शन

(द) अंतिम अवस्थाओं का सेट

(d) Set of final states

(viii)

स्ट्रिंग aabbbcc की लम्बाई है :

The length of string aabbbcc is :

(अ) 3

(a) 3

(ब) 5

(b) 5

(स) 6

(द) 7

(d) 7

(ix)

यदि L = {a², ba}, तो L⁰ है :

If L = {a², ba}, then L⁰ is :

(अ) λ

(a) λ

(ब) a

(b) a

(स) b

(द) ab

(d) ab

(x)

बाइनरी में दशमलव 10 का मान है :

The value of decimal 10 in binary is :

(अ) 10

(a) 10

(ब) 1010

(b) 1010

(स) 0110

(द) 1001

(d) 1001

खण्ड 'ब'

Section B

(लघु उत्तरीय प्रश्न)

(Short Answer Type Questions)

नोट : सभी प्रश्नों के उत्तर दीजिए ।

Attempt all questions.

5×5=25

डायग्राफ के आपतन और आसन्नता आव्यूह को ज्ञात कीजिए ।

Find the incidence and adjacency matrix of the digraph :

अथवा (Or)

वृक्ष परिगमन की प्री-ऑर्डर और पोस्ट-ऑर्डर खोज को परिभाषित कीजिए ।

Define pre-order and post-order search of a tree traversals.

आरेख पर विचार कीजिए :

Consider the diagram :

Define finite automata, with next state function table and show that the automata accepts the input string 110101.

अगली स्थिति फलन तालिका के साथ परिमित ऑटोमेटा को परिभाषित कीजिए और दिखाइए कि ऑटोमेटा इनपुट स्ट्रिंग 110101 को स्वीकार करता है ।

अथवा (Or)

मूरे मशीन को परिभाषित कीजिए । यदि नीचे दी गई तालिका एक मूरे मशीन है और α = 1011 इनपुट स्ट्रिंग है, तो संक्रमण स्थिति और आउटपुट स्ट्रिंग को ज्ञात कीजिए :

Define Moore machine. If the table given below is a Moore machine and α = 1011 is the input string then find the transition state and output string :

वर्तमान स्थिति	नई स्थिति		आउटपुट
वर्तमान स्थिति	0	1	आउटपुट
S₀	S₃	S₁	0
S₁	S₁	S₂	1
S₂	S₂	S₃	0
S₃	S₃	S₂	0

Present state	New state		Output
Present state	0	1	Output
S₀	S₃	S₁	0
S₁	S₁	S₂	1
S₂	S₂	S₃	0
S₃	S₃	S₂	0

उदाहरण सहित समतुल्य मशीन को परिभाषित कीजिए ।

Define equivalent machine with example.

अथवा (Or)

उदाहरण सहित फिनिट स्टेट मशीन को परिभाषित कीजिए ।

Define finite state machine with example.

एक फिनिट स्टेट मशीन और स्टेट ग्राफ डिजाइन कीजिए जो समुच्चय {0, 1, 2} को इनपुट के रूप में प्राप्त करता है और एक आउटपुट उत्पन्न करता है जैसे कि आउटपुट इनपुट अनुक्रम में अंकों के मॉड्यूल 3 योग के समान होता है ।

Design a finite state machine & state graph that receives the set {0, 1, 2} as the input and produces an output such that the output is equal to the module 3 sum of the digits in the input sequence.

अथवा (Or)

मूरे और मीली मशीन में अंतर कीजिए ।

Differentiate Moore and Mealy machine.

क्लेन के प्रमेय को बताइए और सिद्ध कीजिए ।

State and prove Kleen's theorem.

अथवा (Or)

उदाहरण सहित गैर-नियतात्मक परिमित ऑटोमेटा को परिभाषित कीजिए ।

Define Non-deterministic finite automata with example.

खण्ड 'स'

Section C

(दीर्घ उत्तरीय प्रश्न)

(Long Answer Type Questions)

नोट : सभी प्रश्नों के उत्तर दीजिए ।

Attempt all questions.

5×9=45

पोलिश संकेतन को परिभाषित कीजिए । व्यंजक a + b - c.d(g³-f) को रूपांतरित कीजिए ।

Define Polish notation. Convert the expression a + b - c.d(g³-f)

अथवा (Or)

ट्यूरिंग मशीन को बताइए और सिद्ध कीजिए ।

State and prove Turing machine.

निम्नलिखित ग्राफ में a से z तक का सबसे छोटा पथ ज्ञात कीजिए :

Find the shortest path from a to z in the following graph :

अथवा (Or)

दिखाइए कि निम्नलिखित तालिकाओ में दर्शाई गई दो परिमित मशीने समतुल्य है :

Show that the two finite state machine shown in the following tables are equivalent :

(a)

States	Input		Output
	1	2
A	B	C	0
B	B	D	0
C	A	E	0
D	B	E	0
E	F	E	0
F	A	D	1
G	B	C	1

(b)

States	Input		Output
	1	2
A	H	C	0
B	G	B	0
C	A	B	0
D	C	C	0
E	H	B	0
F	D	E	1
G	H	C	1
H	A	E	0

नीचे दी गई आकृति द्वारा दर्शाई गई एक मीली मशीन पर विचार कीजिए । इस मीली मशीन के समतुल्य एक मूरे मशीन बनाइए और अवस्था आरेख भी बनाइए ।

Consider a Mealy machine represented by the figure given below. Construct a Moore machine equivalent to this Mealy machine and also construct the state diagram.

अथवा (Or)

दिखाइए कि भाषा L(G) = {anbncn : n ≥ 1} को G = (N, T, P, S) द्वारा उत्पन्न किया जा सकता है, जहाँ N(S, B, C), T = (a, b, c), P = (S → asBc, S → abc, cb → Bc, ab → ab, pB → bb, bc → bc, cc → cc).

Show that the language L(G) = {anbncn : n ≥ 1} can be generated by G = (N, T, P, S), where N(S, B, C), T = (a, b, c), P = (S → asBc, S → abc, cb → Bc, aB → aB, pB → bb, bc → bc, cc → cc).

10.

एक मीली मशीन डिजाइन कीजिए जो इनपुट स्ट्रिंग s ∈ Σ* में प्रतीक 'a' की दोहरी उपस्थिति को पहचानती है, जहाँ Σ = {a, b} ।

Design a Mealy machine that recognizes the double occurrence of symbol 'a' in input string s ∈ Σ*, where Σ = {a, b}.

अथवा (Or)

तालिका में दिए गए टर्निंग मशीन विवरण पर विचार कीजिए । इनपुट स्ट्रिंग 00 का कम्प्यूटेशन अनुक्रम बनाइए ।

Consider the turning machine description given in the table. Draw the computation sequence of the input string 00.

वर्तमान स्थिति	तालिका प्रतीक
वर्तमान स्थिति	b	0	1
→ q₁	1Lq₂	0Rq₁	1Lq₂
q₂	bRq₃	0Lq₂	1Lq₂
q₃		bRq₄	bRq₅
q₄	0Rq₅	0Rq₄	1Rq₄
q₅	0Lq₂

Present state	Table Symbol
Present state	b	0	1
→ q₁	1Lq₂	0Rq₁	1Lq₂
q₂	bRq₃	0Lq₂	1Lq₂
q₃		bRq₄	bRq₅
q₄	0Rq₅	0Rq₄	1Rq₄
q₅	0Lq₂

11.

निम्नलिखित को परिभाषित कीजिए :

(i)

चरण-संरचना ग्रामर

(ii)

चरण-संरचना भाषा

(iii)

संदर्भ संवेदनशिल ग्रामर

(iv)

संदर्भ मुक्त ग्रामर

(v)

निययित ग्रामर ।

Define the following :

(i)

Phase-structure Grammar

(ii)

Phase-structure language

(iii)

Context sensitive grammar

(iv)

Context free Grammar

(v)

Regular Grammar.

अथवा (Or)

डिजकस्ट्रा के एल्गोरिदम द्वारा सबसे छोटा पथ ज्ञात कीजिए ।

Final shortest path by Dijkstra's algorithm.