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.
