GATE Exam Papers - (computer science
) - Part 1

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