11)CFLs are not closed under
a) Union
b) Concatenation
c) Closure
d) Intersection
12) Which of the following strings will not be accepted by the given NFA?
a) 00 11 22
b) 11 22
c) 21
d) 22
13)A PDM behaves like a TM when the number of auxiliary memory it has, is
a) 0
b) 1 or more
c) 2 or more
d) none of these
14) A minimum state DFA accepting the same language has how many states?
a) 1
b) 2
c) 3
d) 4
15) A grammar that is both left and right recursive for a non-terminal, is
a)Ambiguous
b) Unambiguous
c) Information is not sufficient to decide
d) none of these
16) Given an arbitrary DFA with 2N states, what will be the number of states of the corresponding NFA?
a) N x N
b) 2N
c) 2N
d) N!
17) In a string of length n, how many proper prefixes can be generated
a) 2n
b) n
c) n(n+1)/2
d) n – 1
18) If there is an NP-complete language L whose complement is in NP, then the complement of any language in NP is in
a) NP
b) P
c) Both (a) and (b)
d) None of these
19) An FSM can be used to add two given integers,. This remark is
a) true
b) false
c) may be true
d) none of the above
20) Both P and NP are closed under operator of
a) union
b) intersection
d) concatenation and Kleene star
d) all of the above
Good news for students who are preparing for the exam for Banking Engineering or any other state level exam. We provide questions and answers for all states or all streams here.