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