My Courses

1. Which of the given problems are NP-complete? a) Node cover problems b) Directed Hamilton Circuit Problem c) Both (a) and (b) d) None of the mentioned 2. Give a classic example of the concept of turing complete. a) lambda calculus b) C++ c) Lisp d) All of the mentioned 3. Which aong the following…

1. A language L is said to be Turing decidable if: a) recursive b) TM recognizes L c) TM accepts L d) None of the mentioned 2. State true or false: Statement: The operations of PDA never work on elements, other than the top. a) true b) false 3. Which among the following are true…

1. The use of variable dependency graph is in: a) Removal of useless variables b) Removal of null productions c) Removal of unit productions d) None of the mentioned 2. Given Grammar G: S->aA A->a| A B->B The number of productions to be removed immediately as Unit productions: a) 0 b) 1 c) 2 d)…

1. Which of the following is called Bar-Hillel lemma? a) Pumping lemma for regular language b) Pumping lemma for context free languages c) Pumping lemma for context sensitive languages d) None of the mentioned 2. Which of the following does not have left recursions? a) Chomsky Normal Form b) Greibach Normal Form c) Backus Naur…

1. Fill in the blank with an appropriate option. In automata theory, ___________ is said to be Computationally Universal if can be used to simulate any single taped Turing Machine. a) Computer’s instruction set b) A programming language c) Cellular Automaton d) All of the mentioned 2. Production Rule: aAb->agb belongs to which of the…

1. The decision problem is the function from string to ______________ a) char b) int c) boolean d) none of the mentioned 2. Diagonalization can be useful in: a) To find a non recursively ennumerable language b) To prove undecidablility of haltig problem c) Both (a) and (b) d) None of the mentioned 3. Instantaneous…

1.The given regular language corresponds to which of the given regular language e+1+(1+0)*0+(0+1)*11 a) The language of all strings that end with 11 or 00 b) The language of all strings that end with 0 or 1 c) The language of all strings which does not end with 01 d) None of the mentioned 2.…

1. A regular language over an alphabet a is one that can be obtained from a) union b) concatenation c) kleene d) All of the mentioned 2. Regular grammar is a) context free grammar b) non context free grammar c) english grammar d) none of the mentioned 3. Regular grammar is a) context free grammar…

1. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*? a) 7 b) 10 c) 12 d) 11 2. Which of the following regular expression is equivalent to R(1,0)? R(1,0)={111*}* a) (11+111)* b) (111+1111)* c) (111+11*)* d) All of the mentioned 3. Which of the following is/are…

1. The minimum length of a string {0,1}* not in the language corresponding to the given regular expression: (0*+1*)(0*+1*)(0*+1*) a) 3 b) 4 c) 5 d) 6 2. Which of the technique can be used to prove that a language is non regular? a) Ardens theorem b) Pumping Lemma c) Ogden’s Lemma d) None of…