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
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).Both S1 and S2 are correct

32. Given the following grammars :

G1: S → AB|aaB

A → aA | ∈

B → bB | ∈

G2: S → A | B

A → a A b | ab

B → 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).both G1 and G2 are ambiguous 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Both even(L) and Chop(L) are regular

34. Given the following two grammars :

G1 :     S → AB | aaB

A → a | Aa

B → b

G2: 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).G1 is ambiguous and G2 is ambiguous

35. Match the following:

List-I                                                            List-II

a. Chomsky Normal form                       i.  S→ bSS|aS|c

b. Greibach Normal form                        ii.  S→ aSb|ab

c. S-grammar                                           iii. S→ AS|a

                                                                         A→ SA|b

d. |LL grammar                                        iv. S→ aBSB

                                                                         B→ b

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

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).O(n)

38. The number of strings of length 4 that are generated by the regular expression (0|?) 1+2* (3|?), where | is an alternation character, {+, *} are quantification characters, and ? is the null string, is:
a. 8
b. 10
c. 11
d. 12
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).12

39. Which of the following is FALSE ?
a. The grammar S ? aSb|bSa|SS|?, where S is the only non-terminal symbol and ? is the null string, is ambiguous
b. SLR is powerful than LALR
c. An LL(1) parser is a top-down parser
d. YACC tool is an LALR(1) parser generator
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).SLR is powerful than LALR

40. Consider the languages L1 = ϕ, and L2 = {1}. Which one of the following represents
L1* U L2* L1* ?
a. {ε}
b. {ε,1}
c. ϕ
d. 1*
View Answer Report Discuss Too Difficult!
Answer: (d).1*

Page 4 of 13