Que. 1 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. 2 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. 3 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. 4 For what values of n is 10*n*log2 (n) >2*(n^2)?
A only n>/= 32
B only 0< font < ="20">
C only 20
D only n>/=0
Que. 5 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. 6 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. 7 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. 8 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. 9 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. 10 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
-------------
For more papers visit:
http://onestopgate.com/gate-preparation/ - http://onestopgate.com/gate-preparation/
|