BC0052 – THEORY OF COMPUTER SCIENCE

Dear students get fully solved  SMU BBA Spring 2014 assignments
Send your semester & Specialization name to our mail id :

  “ help.mbaassignments@gmail.com ”
or
Call us at : 08263069601


SPRING 2014, ASSIGNMENT


PRIGRAM
BCA(REVISED 2007)
SEMESTER
5TH
SUBJECT CODE & NAME
BC0052 – THEORY OF COMPUTER SCIENCE
CREDIT
4
BK ID
B0972
MAX. MARKS
60



Note: Answer all questions. Kindly note that answers for 10 marks questions should be approximately of 400 words. Each question is followed by evaluation scheme.
                                                                                                                                                           


Q.1Define g.c.d. (m,n)
Solve recursively: (i) f(x, y) = x + y
(ii) g(x, 0) = 0, g(x, y + 1) = g(x, y) + x.

Answer:Define g.c.d. (m,n)
The greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4


Q.2 Obtain a DFA to accept strings of a’s and b’s starting with the string ab.

Answer: It is clear that the string should start with ab and so, the minimum string that can be accepted by the machine is ab.

To accept the string ab, we need three states and the machine can be written as


Q.3 Prove by mathematical induction.
          12 + 22 + 32+------+ n2 = (n(n+1)(2n+1))/6
Answer:- 12 + 22 + 32+------+ n2 = (n(n+1)(2n+1))/6
First of all Identify the general term and nth partial sum before beginning the problem

The general term, an, is the last term on the left hand side. an = n2
The nth partial sum, Sn, is the right hand side. Sn = n (n + 1) (2n + 1) / 6


Q.4 briefly describes Moore and Mealy machines.

Answer: -Describe Moore
An automation system in which the output depends only on the present input is called a Moore machine. Alternatively, an automaton system in which output depends both on the present input and the present state is called Mealy machine.

A Moore machine can be defined as a 6-tuple ( S, S0, Σ, Λ, T, G ) consisting of the following:
·         A finite set of states ( S )
·         A start state (also called initial state) S0 which is an element of (S)
·         A finite set called the input alphabet ( Σ )

Q.5 If G = ({ S }, { 0,1}, { S →0S1, S →Ʌ}, S ) then find L(G),
the language generated by G.

Answer:-
Since S → ^ is a production, S ^.  This implies that ^ L(G).
Now, for all n ≥ 1, we can write the following:
S 0S1 00S11 … 0nS1n 0n1n.

Q.6 Prove that “A tree G with n vertices has (n–1) edges”
Answer:-
We prove this theorem by induction on the number vertices n.
Basic step: If n = 1, then G contains only one vertex and no edge. So the number of edges in
G is n –1 = 1 – 1 = 0.

Induction hypothesis: The statement is true for all trees with less than ‘n’ vertices. Induction step: Now
let us consider a tree with ‘n’ vertices. Let ‘ek ’ be any edge in T whose end vertices are vi and v j.
Since T is a tree, by there is no other path between vI and v

Dear students get fully solved  SMU BBA Spring 2014 assignments
Send your semester & Specialization name to our mail id :

  “ help.mbaassignments@gmail.com ”
or
Call us at : 08263069601


No comments:

Post a Comment

Note: only a member of this blog may post a comment.