Discrete Structures & Automata Theory M.Tech Question Paper : vardhaman.org
College : Vardhaman College Of Engineering
Degree : M.Tech
Department : Computer Science and Engineering
Semester : I
Subject : Discrete Structures & Automata Theory
Document type : Question Paper
Website : vardhaman.org
Download Previous / Old Question Papers :
April – 2012 :https://www.pdfquestion.in/uploads/vardhaman.org/6413-question%20papers%20of%20two%20year%20m.%20tech%20i%20semester%20regular%20examinations%20april%20-%202012.pdf
September – 2012 :https://www.pdfquestion.in/uploads/vardhaman.org/6413-question%20papers%20of%20two%20year%20m.%20tech%20i%20semester%20supplementary%20examinations%20september%20-%202012.pdf
April – 2013 :https://www.pdfquestion.in/uploads/vardhaman.org/6413-question%20papers%20of%20two%20year%20m.%20tech%20i%20semester%20regular%20examinations%20april%20-%202013.pdf
February – 2014 :https://www.pdfquestion.in/uploads/vardhaman.org/6413-MT1R13FEB-14.pdf
July – 2014 :https://www.pdfquestion.in/uploads/vardhaman.org/6413-MT1S%20JULY14.pdf
Discrete Structures & Automata Theory Question Paper :
Two Year M. Tech I Semester Regular Examinations February – 2014
(Regulations: VCE-R11)
(Computer Science and Engineering)
Date : 05 February, 2014
Time : 3 Hours
Max. Marks : 60
Answer any FIVE Questions.
All Questions carry equal marks
Related : Vardhaman College Of Engineering Fatigue & Fracture Mechanics B.Tech Question Paper : www.pdfquestion.in/6410.html
All parts of the question must be answered in one place only
1. a) Prove or disprove the validity of the following argument using the rules of inference.
i. Every living thing is a plant or an animal.
ii. David’s Dog is alive and it is not a plant.
iii. All animals have hearts
iv. Hence, David’s dog has a heart. 6M
b) Transform the following formula into CNF ( p->q)V (r->p) 6M
2. a) Let A {1,2,3,4 },B { a,b,c,d,} C {x, y, z} and let R {(1,a),(2,d ), (3,a), (3,b), (3,d) } and S {(b, x),(b, z),(c, y), (d, z)}. Give Pictorial representation of therelation and find 0 R S.6M
b) State whether or not each of the relations given below defines a function of
A {(a,b,c)} into B {(1,2,3)}
i. f {(a,2), (a,3), (b,3), (c,1)}
ii. f {(a,2), (b,3)}
iii. f {(a,1),(b,3), (c,1)} 6M
3. a) How many ways can we select a software development group of 1 project leader, 5 programmers and 6 data entry operators from a group of 5 project leaders, 20 programmers and 25 data entry operators ? 6M
b) How many permutations can be made out of the letter of word “COMPUTER” ? How many of these
i. begin with C ?
ii. end with R ?
iii. begin with C and end with R ?
4. a) Find the generating function for the sequence 1, a, a2, … where ‘a’ is a fixed constant. 6M
b) A box contains many identical blue, green and white marbles. Find the ordinary generating function corresponding to the problem of finding the number of ways of choosing r marble from the box such that the sample does not have more than 2 red, more than 3 blue, more than 4 white and more than 5 green. 6M
5. a) Convert the following NFA to DFA.6M
b) Minimize the following DFA using table filling Algorithm. 6M
States INPUT 0 1
->A B F
B G C
*C A C
D C G
E H F
F C G
G G E
H G C
6. a) Show that the regular languages are closed under union and intersection. 6M
b) Obtain the Regular Expression for the following DFA 6M
STATE Input W
q 0 1
-> q0 q1 q3 q
1 q 0 q 3 q
2 q 1 q 4 q
3 *q 5 q 5 q
4 q 3 q 1 q
5 *q 5 q 5 q
7. a) Consider the following grammar 6M
S -> 0A | 1B
A -> 0AA | 1S | 1
B -> 1BB | 0S | 0
Obtain the grammar in CNF.
b) Obtain a PDA to accept the language { 1? n n L ? a b n } by final state. 6M
8. a) Design the Turing Machine for the language ?0 1 1?. n n L ? n ? 8M
b) Write short note on Chomsky hierarchy.
M. Tech I Semester Supplementary Examinations July – 2014
(Regulations: VCE-R11)
DISCRETE STRUCTURES AND AUTOMATA THEORY
(Computer Science and Engineering)
Date: 22 July, 2014
Time: 3 hours
Max Marks: 60
Answer any Five Questions.
All Questions carry equal marks.
All parts of the question must be answered in one place only.
1. a) Show that: (P->Q)V(R->Q) =(P->R)->Q (P = Q)->(PVQ) =(P->Q) 6M
b) Show that (x)(P(x) VQ(x))V(x)P(x) V(x)Q(x) 6M
2 a) If A = {1, 2,3, 4} and B= {a,b, c, d} determine whether the following functions are one-to-one or onto.
f= (1,a ), (2,b ),(3,c ), (4,d ) (1,a ), (2,b ), (3,c ), (4,d ) 6M
b) Prove by pigeon hole principal that in a group of 61 people, at least 6 people were born in the same month.
3. a) Five persons entered the lift cabin on the ground floor of an 8 floor house. Suppose each of them can leave the cabin independently at any floor beginning with the first. Find the total number of ways in which each of the five persons can leave the cabin
i. At any one of the 7 floors
ii. At different floors 6M
b) Prove that the number of different permutations of n distinct objects Taken r at a time, r ?? is given by
4. a) Solve the recurrence relation: S(k) -10.S(k -1) + 9.S(k – 2) = 0, S(0) = 3, S(1) =11.
b) Solve the recurrence relation
5. a) Define the following terms with an example for each.
i. Alphabet
ii. String
iii. Language 6M
b) Construct an NFA that accepts all strings such that the fifth symbol from the left end is zero over the alphabet ?0,1?. 6M
6 a) Construct FA to accept the regular expression (0+1)*(00+11)(0+1)* 6M
b) Show that the language ? ? 2 L ? ai / i ?1 is not regular.
7. a) Eliminate the left recursion from the following grammar: 6M
E ? E ?T T
T ?T *F F
F ??E? id
b) What does each of the following transitions represent in PDA?
i. (p,a,Z ) (q, aZ ).
ii. (p,a,Z ) (q,).
iii. (p,a,Z) (q, r).
8. a) Design a Turing Machine that accepts the set of all even palindromes over ?0,1?. 6M
b) What is decidability? Explain any two undecidable problems. 6M