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. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________
a. 2
b. 3
c. 4
d. 5
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).3

22. Let T be the language represented by the regular expression Σ∗0011Σ∗ where Σ = {0, 1}. What is the minimum number of states in a DFA that recognizes L' (complement of L)?
a. 4
b. 5
c. 6
d. 8
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).5

23. Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?
a. (a* + b* + c*)*
b. (a*b*c*)*
c. ((ab)* + c*)*
d. (a*b* + c*)*
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).((ab)* + c*)*

24. Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language Lc∪ Mc is TRUE?
a. It is necessarily regular but not necessarily context-free
b. It is necessarily context-free
c. It is necessarily non-regular
d. None of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).None of the above

25. Which of the following statements is TRUE about the regular expression 01*0?
a. It represents a finite set of finite strings
b. It represents an infinite set of finite strings
c. It represents a finite set of infinite strings
d. It represents an infinite set of infinite strings
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).It represents an infinite set of finite strings

26. The language {0^n 1^n 2^n | 1 ≤ n ≤ 10^6} is
a. regular
b. context-free but not regular
c. context-free but its complement is not context-free
d. not context-free
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).regular

27. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?
a. L is necessarily a regular language
b. L is necessarily a context-free language, but not necessarily a regular language
c. L is necessarily a non-regular language
d. None of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).None of the above

28. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
a. id + id + id + id
b. id + (id* (id * id))
c. (id* (id * id)) + id
d. ((id * id + id) * id)
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).id + id + id + id

29. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?
a. 5
b. 4
c. 3
d. 2
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).5

30. The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ .
a. 2
b. 3
c. 4
d. 5
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).2

Page 3 of 14