91.  S > aSabSbab; The language generated by the above grammar over the alphabet {a,b} is the set of 
a.  All palindromes 
b.  All odd length palindromes 
c.  Strings that begin and end with the same symbol 
d.  All even length palindromes 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).All odd length palindromes

92.  Consider the below question: 
a.  Not recursive 
b.  Regular 
c.  Context free but not regular 
d.  Recursively enumerable but not context free 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Context free but not regular

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

94.  Consider the CFG with {S,A,B) as the nonterminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules S > aB S > bA B > b A > a B > bS A > aS B > aBB A > bAA Which of the following strings is generated by the grammar? 
a.  aaaabb 
b.  aabbbb 
c.  aabbab 
d.  abbbba 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).aabbab

95.  Consider the below statement: 
a.  L1 only 
b.  L3 Only 
c.  L1 and L2 
d.  L2 and L3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).L2 and L3

96.  Consider the following statements about the context free grammar G = {S → SS, S → ab, S → ba, S → Ε} I. G is ambiguous II. G produces all strings with equal number of a’s and b’s III. G can be accepted by a deterministic PDA. Which combination below expresses all the true statements about G? 
a.  I only 
b.  I and III only 
c.  II and III only 
d.  I, II and III 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).I and III only

97.  Which one of the following grammars generates the language L = {a^ib^j  i ≠ j} 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).D

98.  Consider the languages: L1 = {a^nb^nc^m  n, m > 0} L2 = {a^nb^mc^m  n, m > 0} Which one of the following statements is FALSE? 
a.  L1 ∩ L2 is a contextfree language 
b.  L1 U L2 is a contextfree language 
c.  L1 and L2 are contextfree language 
d.  L1 ∩ L2 is a context sensitive language 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).L1 ∩ L2 is a contextfree language

99.  Consider the languages: L1 = {ww^R w ∈ {0, 1}*} L2 = {w#w^R  w ∈ {0, 1}*}, where # is a special symbol L3 = {ww  w ∈ (0, 1}*) Which one of the following is TRUE? 
a.  L1 is a deterministic CFL 
b.  L2 is a deterministic CFL 
c.  L3 is a CFL, but not a deterministic CFL 
d.  L3 is a deterministic CFL 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).L2 is a deterministic CFL

100.  Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton? 
a.  10110 
b.  10010 
c.  01010 
d.  01001 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).10010
