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 contextfree 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 contextfree 
b.  It is necessarily contextfree 
c.  It is necessarily nonregular 
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.  contextfree but not regular 
c.  contextfree but its complement is not contextfree 
d.  not contextfree 
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 contextfree languages. Which of the following statements about L is TRUE? 
a.  L is necessarily a regular language 
b.  L is necessarily a contextfree language, but not necessarily a regular language 
c.  L is necessarily a nonregular language 
d.  None of the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).None of the above

28.  Consider the contextfree 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 contextfree 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}. 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
