 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.

 31. Given the following two statements :S1: If L1 and L2 are recursively enumerable languages over Σ, then L1 ⋃ L2 and L1 ⌒ L2 are also recursively enumerable.S2: The set of recursively enumerable languages is countable.Which of the following is correct? a. S1 is correct and S2 is not correct b. S1 is not correct and S2 is correct c. Both S1 and S2 are not correct d. Both S1 and S2 are correct

 32. Given the following grammars :G1: S → AB|aaBA → aA | ∈B → bB | ∈G2: S → A | BA → a A b | abB → a b B | ∈Which of the following is correct? a. G1 is ambiguous and G2 is unambiguous grammars b. G1 is unambiguous and G2 is ambiguous grammars c. both G1 and G2 are ambiguous grammars d. both G1 and G2 are unambiguous grammars

 33. Let L be any language. Define even (W)  as the  strings  obtained by extracting from W the letters in the even-numbered positions and even (L) = {even (W) | W ԑ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | v W ԑ L,with | v | = 2}.If L is regular language then a. even (L) is regular and Chop(L) is not regular b. Both even(L) and Chop(L) are regular c. even(L) is not regular and Chop(L) is regular d. Both even (L) and Chop(L) are not regular

 34. Given the following two grammars :G1 :     S → AB | aaBA → a | AaB → bG2: S→ aSbS|bSaS|λWhich statement is correct ? a. G1 is unambiguous, and G2 is unambiguous b. G1 is unambiguous and G2 is ambiguous c. G1 is ambiguous and G2 is unambiguous d. G1 is ambiguous and G2 is ambiguous

 35. Match the following:List-I                                                            List-IIa. Chomsky Normal form                       i.  S→ bSS|aS|cb. Greibach Normal form                        ii.  S→ aSb|abc. S-grammar                                           iii. S→ AS|a                                                                         A→ SA|bd. |LL grammar                                        iv. S→ aBSB                                                                         B→ bCodes:a       b       c       d a. iv      iii       i       ii b. iv      iii       ii       i c. iii      iv       i       ii d. iii      iv       ii       i

 36. Given the following two languages :L1 = {anbn |n≥1} ∪ {a}L2= {w C wR|we {a,b}*}Which statement is correct ? a. Both L1 and L2 are not deterministic b. L1 not deterministic and L2 is deterministic c. L1 is deterministic and L2 is not deterministic d. Both L1 and L2 are deterministic

 37. The solution of the recurrence relation of T(n) = 3T ( floor (n/4) ) +  n is a. 0(n^2) b. O(n/gn) c. O(n) d. O(lgn)