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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).3 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!
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).2^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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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 = φ
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L is regular but not 0+

18. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?
a. L must be {a^n| n is odd}
b. L must be {a^n| n is even}
c. L must be {a^n| ³ O}
d. Either L must be {a^n | n is odd}, or L must be {a^n | n is even}
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).Either L must be {a^n | n is odd}, or L must be {a^n | n is even}

19. How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's.
a. 1
b. 2
c. 3
d. 4
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).2

20. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}

Which one of the following choices precisely represents the strings in X0?
a. 10 (0* + (10)*)1
b. 10 (0* + (10)*)*1
c. 1(0* + 10)*1
d. 10 (0 + 10)*1 + 110 (0 + 10)*1
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).1(0* + 10)*1

Page 2 of 14