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. Consider the following two statements:

I. If all states of an NFA are accepting
states then the language accepted by
the NFA is Σ∗ .
II. There exists a regular language A such
that for all languages B, A ∩ B is regular.

Which one of the following is CORRECT?
a. Only I is true
b. Only II is true
c. Both I and II are true
d. Both I and II are false
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Only II is true

32. In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?
a. aaaa
b. baba
c. abba
d. babaaabab
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).baba

33. Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?
a. L (D) ⊂ L (G)
b. L (D) ⊃ L (G)
c. L (D) = L (G)
d. L (D) is empty
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).L (D) = L (G)

34. Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?
a. (0 + 1) * 11(0 + 1) *
b. 0 * 110 *
c. 0 * 10 * 10 *
d. (0 + 1) * 1(0 + 1) * 1 (0 + 1) *
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).0 * 10 * 10 *

35. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
a. m ≤ 2^n
b. n ≤ m
c. M has one accept state
d. m = 2^n
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).m ≤ 2^n

36. Consider the following languages.

L1 = {a^i b^j c^k | i = j, k ≥ 1}
L1 = {a^i b^j | j = 2i, i ≥ 0}

Which of the following is true?
a. L1 is not a CFL but L2 is
b. L1 ∩ L2 = ∅ and L1 is non-regular
c. L1 ∪ L2 is not a CFL but L2 is
d. There is a 4-state PDA that accepts L1, but there is no DPDA that accepts L2
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L1 ∩ L2 = ∅ and L1 is non-regular

37. Which of the following languages is (are) non-regular?

L1 = {0^m1^n | 0 ≤ m ≤ n ≤ 10000}
L2 = {w | w reads the same forward and backward}
L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}
a. L2 and L3 only
b. L1 and L2 only
c. L3 only
d. L2 only
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).L2 only

38. Which of the following intuitive definition is true about LR(1) Grammar.
a. For a grammar to be LR(1) it is sufficient that a left-to-right shift reduce parser be able to recognize handles of right-sentential form when they appear on the stack
b. For a grammar to be LR(1) it is sufficient that a left-to-right shift reduce parser be able to recognize handles of left-sentential form when they appear on the stack
c. For a grammar to be LR(1) it is sufficient that a left-to-right shift reduce parser be able to recognize handles of left-sentential form or right-sentential form when they appear on the stack
d. All of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).For a grammar to be LR(1) it is sufficient that a left-to-right shift reduce parser be able to recognize handles of right-sentential form when they appear on the stack

39. Consider the Following regular expressions

r1 = 1(0 + 1)*
r2 = 1(1 + 0)+
r3 = 11*0

What is the relation between the languages generated by the regular expressions above ?
a. L (r1) ⊆ L (r2) and L(r1) ⊆ L(r3)
b. L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3)
c. L (r1) ⊇ L (r2) and L(r2) ⊆ L(r3)
d. L (r1) ⊇ L (r3) and L(r2) ⊆ L(r1)
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3)

40. Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are:
a. NFA – 3, DFA – 4
b. NFA – 3, DFA – 3
c. NFA – 3, DFA – 3
d. NFA – 4, DFA – 4
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).NFA – 3, DFA – 4

Page 4 of 14