131.  Consider the language L1,L2,L3 as given below. L1={0^p1^q  p,q ∈ N} L2={0^p1^q p,q ∈ N and p=q} L3={0^p1^q0^r  p,q,r ∈N and p=q=r} Which of the following statements is NOT TRUE? 
a.  Push Down Automata (PDA) can be used to recognize L1 and L2 
b.  L1 is a regular language 
c.  All the three languages are context free 
d.  Turing machine can be used to recognize all the three languages 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).All the three languages are context free

132.  Definition of a language L with alphabet {a} is given as following. L= { a^(nk)  k > 0, and n is a positive integer constant}. What is the minimum number of states needed in a DFA to recognize L? 
a.  k+1 
b.  n+1 
c.  2^(n+1) 
d.  2^(k+1) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).n+1

133.  Which of the following pairs have DIFFERENT expressive power? 
a.  Deterministic finite automata (DFA) and NonDeterministic finite automata(NFA) 
b.  Deterministic push down automata (DPDA) and Nondeterministic pushdown automata 
c.  Deterministic singletape Turing machine and Nondeterministic singletape Turing Machine 
d.  Singletape Turing machine and multitape Turing machine 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Deterministic push down automata (DPDA) and Nondeterministic pushdown automata

134.  Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a contextfree language, then is L’ (complement of L) also contextfree? 3) If L is a regular language, then is L’ also regular? 4) If L is a recursive language, then, is L’ also recursive? 
a.  1, 2, 3, 4 
b.  1, 2 
c.  2, 3, 4 
d.  3, 4 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).3, 4

135.  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.  ScT (S is a subset of T) 
b.  TcS (T is a subset of S) 
c.  S=T 
d.  SnT=Ø 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).S=T

136.  Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true ? 
a.  L = O 
b.  L is regular but not O 
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 O

137.  Consider the following two statements: S1: { 0^2n n >= l} is a regular language S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language Which of the following statements is correct? 
a.  Only S1 is correct 
b.  Only S2 is correct 
c.  Both S1 and S2 are correct 
d.  None of S1 and S2 is correct 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Both S1 and S2 are correct

138.  Given an arbitrary 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
