 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.

 21. Regular expression for the complement of language L = {a^n b^m I n ≥ 4, m ≤ 3} is a. (a + b)* ba(a + b)* b. a* bbbbb* c. (λ + a + aa + aaa)b* + (a + b)* ba(a + b)* d. None of the above

 22. We can show that the clique problem is NP-hard by proving that a. CLIQUE ≤ P 3-CNF SAT b. CLIQUE ≤ PVERTEX_COVER c. CLIQUE ≤  P SUBSET_SUM d. None of the above

 23. Given the recursively enumerable language (LRE), the context sensitive language (LCS) the recursive language (LREC) the context free language (LCF) and deterministic context free language (LDCF) The relationship between these families is given by a. LCF ⊆ LDCF ⊆ LCS ⊆ LRE ⊆ LREC b. LCF ⊆ LDCF ⊆ LCS ⊆ LREC ⊆ LRE c. LDCF ⊆ LCF ⊆ LCS ⊆ LRE ⊆ LREC d. LDCF ⊆ LCF ⊆ LCS ⊆ LREC ⊆ LRE

 24. Match the following:       List- I                                                List -IIa. Context free grammar               i. Linear bounded automatonb. Regular grammar                     ii. Pushdown automatonc. Context sensitive grammar     iii. Turing machined. Unrestricted grammar             iv. Deterministic finite automatoncode:a   b    c    d a. ii    iv   iii    i b. ii    iv    i    iii c. iv    i     ii    iii d. i    iv   iii    ii

 25. According to pumping lemma for context free languages:Let L be an infinite context free language, then there exists some positive integer m such that any w ∈ L with I w I ≥ m can be decomposed as w = u v x y z a. with I vxy I ≤ m such that uvi xyi z ∈ L for all i = 0,1,2 b. with I vxy I ≤ m and I vy I ≥ 1 such that uvi xyi z ∈ L for all i = 0,1,2,..... c. with I vxy I ≥ m and I vy I ≤ 1 such that uvi xyi z ∈ L for all i = 0,1,2,..... d. with I vxy I ≥ m and I vy I ≥ 1 such that uvi xyi z ∈ L for all i = 0,1,2,.....
 View Answer Report Discuss Too Difficult! Search Google Answer: (d).with I vxy I ≥ m and I vy I ≥ 1 such that uvi xyi z ∈ L for all i = 0,1,2,.....

 26. The equivalent production rules corresponding to the production rulesS → Sα1 | Sα2 | β1 | β2 a. S → β1 | β2 ,  A   → α1A | α2 A | λ b. S → β1 | β2  | β1 A | β2 A , A   → α1A | α2 A c. S → β1 | β2 ,  A   → α1A | α2 A d. S → β1 | β2  | β1A |  β2A , A   → α1A | α2 A  | λ

 27. If all the production rules have single non - terminal symbol on the left side, the grammar defined is : a. context free grammar b. context sensitive grammar c. unrestricted grammar d. phrase grammar