151.  Pumping lemma for regular language is generally used for proving: 
a.  whether two given regular expressions are equivalent 
b.  a given grammar is ambiguous 
c.  a given grammar is regular 
d.  a given grammar is not regular 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).whether two given regular expressions are equivalent

152.  Which of the following problems is undecidable? 
a.  To determine if two finite automata are equivalent 
b.  Membership problem for context free grammar 
c.  Finiteness problem for finite automata 
d.  Ambiguity problem for context free grammar 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Ambiguity problem for context free grammar

153.  Finite state machine can recognize language generated by .................... 
a.  Only context free grammar 
b.  Only context sensitive grammar 
c.  Only regular grammar 
d.  any unambiguous grammar 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Only regular grammar

154.  The language L = {a^i b c^i  i ≥ 0} over the alphabet {a, b, c} is: 
a.  a regular language. 
b.  not a deterministic context free language but a context free language. 
c.  recursive and is a deterministic context free language. 
d.  not recursive. 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).recursive and is a deterministic context free language.

155.  Which of the following statements is not correct? 
a.  Every recursive language is recursively enumerable. 
b.  L = {0^n 1^n 0^n  n=1, 2 , 3, ....} is recursively enumerable. 
c.  Recursive languages are closed under intersection. 
d.  Recursive languages are not closed under intersection. 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Recursive languages are not closed under intersection.

156.  Context free grammar is not closed under : 
a.  Concatenation 
b.  Complementation 
c.  Kleene Star 
d.  Union 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Complementation

157.  Consider the following languages : L1 = {a^m b^n  m ≠ n} L2 = {a^m b^n  m = 2n+1} L3 = {a^m b^n  m ≠ 2n} Which one of the following statement is correct? 
a.  Only L1 and L2 are context free languages 
b.  Only L1 and L3 are context free languages 
c.  Only L2 and L3 are context free languages 
d.  L1, L2 and L3 are context free languages 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).L1, L2 and L3 are context free languages

158.  Given a Nondeterministic Finite Automation (NFA) with states p and r as initial and final states respectively transition table as given below. The minimum number of states required in Deterministic Finite Automation (DFA) equivalent to NFA is 
a.  5 
b.  4 
c.  3 
d.  2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).3
