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.

 11. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE? a. Df ⊂ Nf and Dp ⊂ Np b. Df ⊂ Nf and Dp = Np c. Df = Nf and Dp = Np d. Df = Nf and Dp ⊂ Np

 12. The regular expression 0*(10*)* denotes the same set as a. (1*0)*1* b. 0 + (0 + 10)* c. (0 + 1)* 10(0 + 1)* d. none of these

 13. The smallest finite automation which accepts the language {x | length of x is divisible by 3} has : a. 2 states b. 3 states c. 4 states d. 5 states

 14. Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least a. N^2 b. 2^N c. 2N d. N!

 15. Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have? a. 8 b. 14 c. 15 d. 48

 16. Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? a. S ⊂ T b. T ⊂ S c. S = T d. S ∩ T = φ

 17. Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true? a. L = 0+ b. L is regular but not 0+ c. L is context free but not regular d. L is not context free