 A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

 131. Consider the language L1,L2,L3 as given below. L1={0^p1^q | p,q ∈ N} L2={0^p1^q| p,q ∈ N and p=q} L3={0^p1^q0^r | p,q,r ∈N and p=q=r} Which of the following statements is NOT TRUE? a. Push Down Automata (PDA) can be used to recognize L1 and L2 b. L1 is a regular language c. All the three languages are context free d. Turing machine can be used to recognize all the three languages

 132. Definition of a language L with alphabet {a} is given as following. L= { a^(nk) | k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L? a. k+1 b. n+1 c. 2^(n+1) d. 2^(k+1)

 133. Which of the following pairs have DIFFERENT expressive power? a. Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA) b. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata c. Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine d. Single-tape Turing machine and multi-tape Turing machine

 134. Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L’ (complement of L) also context-free? 3) If L is a regular language, then is L’ also regular? 4) If L is a recursive language, then, is L’ also recursive? a. 1, 2, 3, 4 b. 1, 2 c. 2, 3, 4 d. 3, 4

 135. Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? a. ScT (S is a subset of T) b. TcS (T is a subset of S) c. S=T d. SnT=Ø