31.  Consider the following two statements:
I. If all states of an NFA are accepting states then the language accepted by the NFA is Σ∗ . II. There exists a regular language A such that for all languages B, A ∩ B is regular. Which one of the following is CORRECT? 
a.  Only I is true 
b.  Only II is true 
c.  Both I and II are true 
d.  Both I and II are false 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Only II is true

32.  In the contextfree grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa  bSb  a  b  ϵ Which of the following strings is NOT generated by the grammar? 
a.  aaaa 
b.  baba 
c.  abba 
d.  babaaabab 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).baba

33.  Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ? 
a.  L (D) ⊂ L (G) 
b.  L (D) ⊃ L (G) 
c.  L (D) = L (G) 
d.  L (D) is empty 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).L (D) = L (G)

34.  Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's? 
a.  (0 + 1) * 11(0 + 1) * 
b.  0 * 110 * 
c.  0 * 10 * 10 * 
d.  (0 + 1) * 1(0 + 1) * 1 (0 + 1) * 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).0 * 10 * 10 *

35.  Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true? 
a.  m ≤ 2^n 
b.  n ≤ m 
c.  M has one accept state 
d.  m = 2^n 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).m ≤ 2^n

36.  Consider the following languages.
L1 = {a^i b^j c^k  i = j, k ≥ 1} L1 = {a^i b^j  j = 2i, i ≥ 0} Which of the following is true? 
a.  L1 is not a CFL but L2 is 
b.  L1 ∩ L2 = ∅ and L1 is nonregular 
c.  L1 ∪ L2 is not a CFL but L2 is 
d.  There is a 4state PDA that accepts L1, but there is no DPDA that accepts L2 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).L1 ∩ L2 = ∅ and L1 is nonregular

37.  Which of the following languages is (are) nonregular?
L1 = {0^m1^n  0 ≤ m ≤ n ≤ 10000} L2 = {w  w reads the same forward and backward} L3 = {w ∊ {0, 1} *  w contains an even number of 0's and an even number of 1's} 
a.  L2 and L3 only 
b.  L1 and L2 only 
c.  L3 only 
d.  L2 only 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).L2 only

38.  Which of the following intuitive definition is true about LR(1) Grammar. 
a.  For a grammar to be LR(1) it is sufficient that a lefttoright shift reduce parser be able to recognize handles of rightsentential form when they appear on the stack 
b.  For a grammar to be LR(1) it is sufficient that a lefttoright shift reduce parser be able to recognize handles of leftsentential form when they appear on the stack 
c.  For a grammar to be LR(1) it is sufficient that a lefttoright shift reduce parser be able to recognize handles of leftsentential form or rightsentential form when they appear on the stack 
d.  All of the above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).For a grammar to be LR(1) it is sufficient that a lefttoright shift reduce parser be able to recognize handles of rightsentential form when they appear on the stack

39.  Consider the Following regular expressions
r1 = 1(0 + 1)* r2 = 1(1 + 0)+ r3 = 11*0 What is the relation between the languages generated by the regular expressions above ? 
a.  L (r1) ⊆ L (r2) and L(r1) ⊆ L(r3) 
b.  L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3) 
c.  L (r1) ⊇ L (r2) and L(r2) ⊆ L(r3) 
d.  L (r1) ⊇ L (r3) and L(r2) ⊆ L(r1) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3)

40.  Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are: 
a.  NFA – 3, DFA – 4 
b.  NFA – 3, DFA – 3 
c.  NFA – 3, DFA – 3 
d.  NFA – 4, DFA – 4 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).NFA – 3, DFA – 4
