GATE Exam Papers - (Computer Science) - Part 1

Number Times Read : 673

Go To Article :

Categories


Air India (2)
Campus Interviews (505)
Career Helper (6)
Certification Dumps (10)
Code Samples (118)
Competitive Exams (163)
Interview Questions (4686)
Test Dev (0)
Test Director (25)
test... (0)
test_php (0)
Walkin Interviews (20)

Stats
Total Articles: 5572 Total Authors: 781 Total Downloads: 1183405 Newest Member sukhvir chahal

Question Popularity:
Submitted 2008-05-28 00:29:03

GATE Exam Papers - (Computer Science) - Part 1

More than one answer can be correct.

Que. 1 Context-free languages are closed under:
A Union , intersection
B Union , Kleene closure
C Intersection, complement
D Complement, Kleene Closure

Que. 2 Let L p be the set of all languages accepted by a PDA by final
state and L E the set of all languages accepted by empty stack.
Which of the following is true?
A L D = L E
B L D É L E
C L D = L E
D None of the above

Que. 3 A grammar that is both left and right recursive for anonterminal,
is
A Ambiguous
B Unambiguous
C Information is not sufficient to decide whether it is ambiguous or
(D)None of the above
D (C)Information is not sufficient to decide whether it is ambiguous or
None of the above

Que. 4 Let S and T be languages over S = {a, b} represented by the regular expressions (a + b *) * and (a + b) *, respectively. Which of the following is true?
A S Ì T
B T Ì S
C S = T
D S Ç T = f

Que. 5 Let L denotes the language generated by the grammar S->0S0/00.
Which of the following is true?
A L = 0 +
B L is regular but not 0 +
C L is context free but not regular
D L is not context free

Que. 6 Which of the following need not necessarily be saved on a context switch
between processes?
A General purpose registers
B Translation look aside buffer
C Program counter
D All of the above

Que. 7 Given an arbitrary non-deterministic finite automaton (NFA) with
N states, the maximum number of states in an equivalent minimized
DFA is at least
A N^2
B 2^N
C 2N
D N!

Que. 8 Which one of the following regular expression over {1,1} denotes the set of all strings not containing 100 as a substring?
A 0*(1+0)*
B 0*1010*
C 0*101
D 0*(10+1)*

Que. 9 Aliasing in the context of programming languages refers to
A multiple variables having the same memory location
B multiple variables having the same value
C multiple variables having the same identifier
D multiple uses of the same variable

Que. 10 Consider the following decision problems : (PI) Does a given finite
state machine accept a given string (P2) Does a given context free grammar
generate an infinite number of stings Which of the following statements
is true?
A Both (PI) and (P2) are decidable
B Neither (PI) nor (P2) are decidable
C Only (PI) is decidable
D Only (P2) is decidable

Que. 11 Given the following expression grammar:
E->E * F | F+E | F
F-> F-F | id
Which of the following is true?
A * has higher precedence than +
B - has higher precedence than *
C + and - have same precedence
D + has higher precedence than *

Que. 12 Consider the following two statements:
S1: {(O^2n) |n>/=1} is a regu1ar language
S2: {(O^m)(1^n)(O^m+n)|m>/=l and n>/=l} is a regu1ar language
Which of the following statements is correct?
A Only S1 is correct
B Only S2 is correct
C Both S1 and S2 are correct
D None of S1 andS2 is correct

Que. 13 Which of the following statements in true?
A If a language is context free it can always be accepted by a deterministic
push-down automaton
B The union of two context free languages is context free
C The intersection of two context free languages is context free
D The complement of a context free language is context free

Que. 14 Which of the following statements is false?
A An unambiguous grammar has same leftmost and rightmost derivation
B An LL(1) parser is a top-down parser
C LALR is more powerful than SLR
D An ambiguous grammar can never be LR(k) for any k

Que. 15 Consider the following languages:
L1={w w l w (belongs) to) {a,b}*}
L2={ww^R | w (belongs) {a, b}*, w R is the reverse of w}
L3 = { 0^2i | i is an integer}
L4 = {[(O)^i]^2| i is an integer}
Which of the languages are regular?
A Only L1 and L2
B Only L2, L3, and L4
C Only L3 and L4
D Only L3

Que. 16 Context free language are closed under
A union, intesection
B union,kleene closure
C intesection,complement
D complement,kleene closure

Que. 17 Context free languages are
A closed under union
B closed under complementation
C closed under intersection
D all of the above

Que. 18 Which one is equivalent (i) (00)*(e+0) (ii) (00)* (iii) 0* (iv)
0(00)*
A (i) and (ii)
B (ii) and (iii)
C (i) and (iii)
D (iii) and (iv)

Que. 19 Type O grammer is
A (C)both and (b) above
B (C)both (a) and above
C both (a) and (b) above
D none of these

Que. 20 Consider a DFA over S = {a, b} accepting all strings which have number of a's divisible by 6 and number of b's divisible by 8. What is the minimum number of states that the DFA will have?
A 8
B 14
C 15
D 48

Que. 21 The language L={(a^k)(b^k) | k>or= 1} is
A type 3 grammer
B type 2 grammer
C type 1 grammer
D type 0 grammer

Que. 22 Recursive languages are
A a proper superset of context free languages
B always recognizable by pushdown automata
C also called type zero lanugages
D all of these

Que. 23 A grammer that is both left and right recursive for a nopn-terminal is
A ambiguous
B unambiguous
C information is not sufficient to decide whether it is ambiguous or
unambiguous
D none of the above

Que. 24 For what values of n is 10*n*log2 (n) >2*(n^2)?
A only n>/= 32
B only 0
C only 20
D only n>/=0

Que. 25 Let * be defined as x*y = x' + y.Let z = x * y .Value of z*x is
A x' + y
B x
C 0
D 1

Que. 26 Which of the following regular expressions over {0,1} denotes the set of all strings not containing
100 as a substring
A 0*(1+0)*
B 0*1010*
C 0*1*01*
D 0*(10+1)*

Que. 27 Which of the following grammer rules violate the requirements of an operator
grammer? P,Q,R are nonterminals and r,s,t are terminals. (i)
P -> Q R (ii) P -> QsR (iii) P -> e (iv)P
->Qtpr
A (i) only
B (i) and (iii) only
C (ii) and (iii) only
D (iii) and (iv) only

Que. 28 indicate which ofthe following statments are true Recursive language
are
A A proper superset of context free languages
B always recognizable by pushdown automata
C recognizable by turing machine
D also called type-0 languages

Que. 29 Which of the following is not decidable?
A Given a Turing machine M,a string s and an integer k,M accepts s
within k steps
B Equivalence of two given Turing machines
C Language Accepted by a given finite state machine is not empty
D language generated by a context free grammer is not empty

Que. 30 Regarding the power of recognition of languages,Which of the following
statments is false?
A the non-deterministic finite-state automata are equivalent to deterministic
finite state automata.
B non-deterministic push down automata are equivalent to deterministic
push down automata.
C non-deterministic Turing machines are equivalent to deterministic
to push down automata.
D non-deterministic Turing machines are equivalent to deterministic
Turing machines

Que. 31 The string 1101 does not belong to the set represented by
A 110*(0+1)
B 1(0+1)*101
C (10)*(01)*(00+11)*
D (00+(11)*0)*

Que. 32 The following grammer S->bS S->b S->aA A->bA A->aB B->bB B->aS
B->a is
A type 3 grammer
B type 2 grammer
C type 1 grammer
D type 0 grammer

Que. 33 A language accepted by a pushdown Automaton in which the stack is limited
to 10 items is best described as
A Context free
B Regular
C Deterministic Context free
D Recursive

Que. 34 Aliasing in the context of programming languages refers to
A multiple variables having the same memory location
B multiple variables having the same value
C multiple variables having the same identifier
D multiple uses of the same variable

Que. 35 If L1 is context free language and L2 is aregular language which ofthe
followingi/are false
A L1-L2 is not context free
B L1 (intersection) L2 is context free
C ~L2 is context free
D ~L1 isregular

Que. 36 consider the following regular expression :
R=(ab|abb)*bbab
Which of the following strings is NOT in the set denoted by R?
A ababab
B abbbab
C abbabbbab
D ababbabbbab

Que. 37 The following grammar S->bS S->b S->aA A->bA is
A type-3 grammer
B type-2 grammer
C type-1 grammer
D type-0 grammer

Que. 38 The smallest finite aitomaton which accepts the language {x|length of x is divisible by 3} has
A 2 states
B 3 states
C 4 states
D 5 states

Que. 39 The following production A -> ab A -> aA aAb ->
aBCb is
A type-3 grammer
B type-2 grammer
C type-1 grammer
D type-0 grammer

Que. 40 Which of the following statment is false>
A every finite subset of an non-regular set is regular
B every subset of a regular set is regular
C every finite subset of an regular set is regular
D The intersection of two regular set is regular

Related Stuff

Answers

1.b 2.b 5.d 6.b 8.d 9.c
Submitted By:	sivaprasad	On:	20-12-2010

New Members
	Sign up
	learn more
	Affiliate Sign In


Nav Menu
	Home
	Login
	Submit Articles
	Submission Guidelines
	Top Articles
	Link Directory
	About Us
	Contact Us
	Privacy Policy
	RSS Feeds

Actions

Print This Article

Add To Favorites


Sponsors

Proudly associated with Job Interview Helper | Interviewhelper Articles

Question Popularity: Submitted 2008-05-28 00:29:03

Submitted By:

On:

Question Popularity:
Submitted 2008-05-28 00:29:03