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.

151. Pumping lemma for regular language is generally used for proving:
a. whether two given regular expressions are equivalent
b. a given grammar is ambiguous
c. a given grammar is regular
d. a given grammar is not regular
View Answer Report Discuss Too Difficult!
Answer: (a).whether two given regular expressions are equivalent

152. Which of the following problems is undecidable?
a. To determine if two finite automata are equivalent
b. Membership problem for context free grammar
c. Finiteness problem for finite automata
d. Ambiguity problem for context free grammar
View Answer Report Discuss Too Difficult!
Answer: (d).Ambiguity problem for context free grammar

153. Finite state machine can recognize language generated by ....................
a. Only context free grammar
b. Only context sensitive grammar
c. Only regular grammar
d. any unambiguous grammar
View Answer Report Discuss Too Difficult!
Answer: (c).Only regular grammar

154. The language L = {a^i b c^i | i ≥ 0} over the alphabet {a, b, c} is:
a. a regular language.
b. not a deterministic context free language but a context free language.
c. recursive and is a deterministic context free language.
d. not recursive.
View Answer Report Discuss Too Difficult!
Answer: (c).recursive and is a deterministic context free language.

155. Which of the following statements is not correct?
a. Every recursive language is recursively enumerable.
b. L = {0^n 1^n 0^n | n=1, 2 , 3, ....} is recursively enumerable.
c. Recursive languages are closed under intersection.
d. Recursive languages are not closed under intersection.
View Answer Report Discuss Too Difficult!
Answer: (d).Recursive languages are not closed under intersection.

156. Context free grammar is not closed under :
a. Concatenation
b. Complementation
c. Kleene Star
d. Union
View Answer Report Discuss Too Difficult!
Answer: (b).Complementation

157. Consider the following languages :

L1 = {a^m b^n | m ≠ n}
L2 = {a^m b^n | m = 2n+1}
L3 = {a^m b^n | m ≠ 2n}

Which one of the following statement is correct?
a. Only L1 and L2 are context free languages
b. Only L1 and L3 are context free languages
c. Only L2 and L3 are context free languages
d. L1, L2 and L3 are context free languages
View Answer Report Discuss Too Difficult!
Answer: (d).L1, L2 and L3 are context free languages

158. Given a Non-deterministic Finite Automation (NFA) with states p and r as initial and final states respectively transition table as given below. The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is
a. 5
b. 4
c. 3
d. 2
View Answer Report Discuss Too Difficult!
Answer: (c).3