This practice GATE test includes only theory of computation questions, which are part of the GATE computer science question papers. There are number of GATE exam papers to help you score good in GATE 2012.

End Test Now

L can be recognized by a multi tape with time complexity f, then L can be recognized by a one tape machine with time complexity

If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in…........

none of these

P

both

NP

The grammars G=<{S},{0,1},p,s> where is a….....

regular language

context-free language

recursively enumerable language

context-sensitive language

which sentence can be generated by

ababccd

bccddd

aabccd

abbbd

Let * be defined as xy= . let z=xy, value of z*x is ..

1

x

0

which of the following is most general phase-structured grammar ?

Context-Free

Context-sensitive

Regular

The number of auxiliary memory required for a push down machine(PDM) to behave like a finite state machine(FSM) is

4

2

can a DFA simulate NFA ?

yes

depends on NFA

no

sometimes

which of the following is not primitive recursive but partially recursive…

Carnot’s function

Ackermann’s function

Ricmann function

Bounded function

recursive enumerable language

The number of symbols necessary to simulate a turning machine with symbols and “n” states is

2m(n+m)

8mn+4m

4mn+m

mn

pumping lemma is generally used for proving..

a given number is regular

whether two given regular expressions are equivalent or not

a given number is not regular

The set can be generated by the CFG…

consider two regular languages L1=(a+b)a and L2=b(a+b). The intersection of L1 and L2 is given by

b(a+b)*a

ab(a+b)*

a(a+b)*b

(a+b)*ab

Every context-free grammar(CFG) can be transferred in to an equivalent…

GNP or CNF

Chomsky Normal Form(CNF)

Greiback Normal Form(GNP)

The number of external states of a UTM should be atleast..

3

The string 1101 does not belong to the set represented by..

1(0+1)*101

110*(0+1)

((11)+01)

(10)*(00+11)

Any given transition graph has an equivalent ….

regular expression

DFSM

all of these

NDFSM

which of the following statements is true ? 1. as the number of entries in a hash table increases, the number of collisions increases. 2.Recursive programs are efficient. 3. The worst case complexity for Quicksort is 4. Binary search using a linear linked list is efficient

1 and 3

2 and 3

1 and 4

1 and 2

which of the following instances of the post correspondence problem have a viable sequence ..?

{(ab,aba),(baa,aa)(aba,baa)}

{(b,bb),(bb,bab),(bab,abb)(abb,babb)}

{(ab,abb),(ba,aaa)(aa,a)}

When you are sure that you have answered as many questions as possible, click the ‘Done’ button below and view your results.