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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).LCF ⊆ LDCF ⊆ LCS ⊆ LREC ⊆ LRE

24. Match the following:

       List- I                                                List -II
a. Context free grammar               i. Linear bounded automaton
b. Regular grammar                     ii. Pushdown automaton
c. Context sensitive grammar     iii. Turing machine
d. Unrestricted grammar             iv. Deterministic finite automaton

code:
a   b    c    d
a.  ii    iv   iii    i
b. ii    iv    i    iii
c. iv    i     ii    iii
d. i    iv   iii    ii
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).ii    iv    i    iii

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 rules

S → 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  | λ
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).context free grammar

28. Minimal deterministic finite automaton for the language L = {0n | n ≥ 0 , n ≠ 4} will have
a. 4 final states among 5 states
b. 1 final state among 6 states
c. 3 final state among 6 states
d. 5 final state among 6 states
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).5 final state among 6 states

29. The regular expression corresponding to the language L where L = { x ∈{0, 1}* | x ends with 1 and does not contain substring 00 } is :
a. (1 + 01)* (10 + 01)
b. (1 + 01)* 01
c. (1 + 01)* (1 + 01)
d. (10 + 01)* 01
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).(1 + 01)* (1 + 01)

30. A context free grammar for L = { w | n0 (w) > n1 (w)} is given by :
a. S → 0 | 0 S | 1 S S
b. S → 0 S | 1 S | 0 S S | 1 S S | 0 | 1
c. S → 0 | 0 S | 1 S S | S 1 S |S S 1
d. S → 0 S | 1 S | 0 | 1
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).S → 0 | 0 S | 1 S S | S 1 S |S S 1

Page 3 of 13