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 📩GH-487
M.A./M.Sc. IInd Semester (Reg./Pvt./ATKT)
Examination, 2022
Maths
Paper - V (i)
Adv. Discrete Maths-II
Note- Attempt all the questions.
SECTION - 'A'
Objective Type Questions
1×15=15
1. Choose the correct answer -
(i) In a directed graph, which of the followin statement is correct about deree of pendant vertex :
(ii) In a path matrix, which of the following statements is not correct :
(iii) A diagragh in which for every edge (a, b) there is also an edge (b, a), is called as :
(iv) The generating function of the numeric function ar = 3.2r, r ≥ 0 is
(v) The discrete numeric function corresponding to the generating function
A(z) = (1+z)4⁄(1-z)4
(vi) The solution of the recurrence relation ar - 3ar-1 - 4ar-2 = 0, r ≥ 2, where a0 = 1, a1 = 2 is
(vii) A grammar G which has no restriction on its produc- tion is called :
(viii) In a finite machine S0 denotes :
(ix) A finite state language is called :
(x) The length of string aabbbcc is :
(xi) Two machines are equivalent if:
(xii) A state of a finite state machine M with output alphabet O = {0, 1} is said to be rejecting state if its output is :
(xiii) Which of the following turing machine does not con- sists of :
(xiv) Moore machine is an application of :
(xv) Which of the following statement is correct :
SECTION - 'B'
Short Answer Type Questions
2. Define incidence matrix with examples & explain its properties.
OR
Define following with an example -
(a) In degree
(b) Out degree
3. Determine numeric function corresponding to the following generating function.
A(z) = 1⁄1-z2
OR
Find the particular solution of ar - 4ar-1 = 2r.
4. Define regular grammar with example.
OR
Construct a grammar for the
L = {anbn | n ≥ 1}
5. Define finite state machine with an example.
OR
Design a finite state machine that performs serial binary addition.
SECTION - 'C'
Long Answer Type Questions
5×9=45
6. Define regular language with an example.
OR
Explain Moore machine with example.
7. Define Adjacency matrix and write adjacency matrix of the graph in the following figure -
OR
If B a circuit matrix of a connected graph G with e-edges & n-vertices, then show that the rank of B = e - n + 1
8. Solve the recurrence relation
ar - 5ar-1 + 6ar-2 = 2r + r.r ≥ 2
with boundary conditions a0 = 1 & a1 = 1.
OR
Find the discrete numeric function, if generating function:
A(z) = 7z3⁄(1-2z)(1+3z)
9. The language L (GS) = {anbn, n ≥ 1} is generated by the grammar GS = ({S, A, B, C}, {a, b}, S, φ) when the set of production is S → aS, S → aB, B → bC, C → a, then derive the sentense a3ba1.
OR
Construct grammar for the language of the following :
(a) L = {anbn | i, j ≥ 1, i ≠ j}
(b) L = {anbn : m > n > 0, m ≠ n}
10. Draw the state diagram of the finite state machine, the state table of which is given by the following table, show that this finite state machine is an finite state automata & redraw the transition diagram as the diagram of the finite state automata. What is the characteristic of the string accepted by the finite state automata ?
OR
Show that the two finite state machines shown in the following tables are equivalent.
11. Define a turing machine to recognize all strings consisting of even number of 1's.
OR
Define Mealy's machines. Construct a Mealy's machine which is equivalent to given Mooray's machine. Also draw state diagram.