11.  Let Nf and Np denote the classes of languages accepted by nondeterministic finite automata and nondeterministic pushdown automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic pushdown 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 nondeterministic 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 nonterminals 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
