Theory of Computation MCQs | Page - 5

Q. 41) Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

Q. 42) 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?

Q. 43) Which of the following pairs have DIFFERENT expressive power?

Q. 44) Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization

Q. 45) A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has

Q. 46) Any Language generated by an unrestricted grammar is:

Q. 47) The Family of recursive language is not closed under which of the following operations:

Q. 48) PCP is:

Q. 49) If PCP is decidable then MPCP is

Q. 50) Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?