41.  Consider the grammar G. E > TE’ E’ > +TE’  ԑ T’ > FT’ T’ > *FT’  ԑ F > (E)  id If LL(1) parsing table is constructed using the grammar G, then how many entries are present in the row that represents E’ nonterminal ? (consider the entries which are not error/not blank entries) 
a.  1 
b.  2 
c.  3 
d.  4 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).3

42.  Let, init (L) = {set of all prefixes of L}, Let L = {w  w has equal number of 0’s and 1’s} init (L) will contain: 
a.  all binary strings with unequal number of 0’s and 1’s 
b.  all binary strings with ԑstring 
c.  all binary strings with exactly one more 0's than number of 1's 
d.  None of above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).all binary strings with ԑstring

43.  Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then 
a.  On every input on which M1 doesn’t halt, M2 doesn’t halt too 
b.  On every i/p on which M1 halts, M2 halts too 
c.  On every i/p which M1 accepts, M2 halts 
d.  None of above 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).On every i/p which M1 accepts, M2 halts

44.  Consider the following decision problems: (P1) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true? 
a.  Both (P1) and (P2) are decidable 
b.  Neither (P1) nor (P2) are decidable 
c.  Only (P1) is decidable 
d.  Only (P2) is decidable 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Both (P1) and (P2) are decidable

45.  Consider the following two statements: 
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: (a).Only S1 is correct

46.  Which of the following statements is true ? 
a.  If a language is context free it can always be accepted by a deterministic pushdown automaton 
b.  The union of two context free languages is context free 
c.  The intersection of two context free languages is context free 
d.  The complement of a context free language is context free 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).The union of two context free languages is context free

47.  Consider the following languages. Which of the languages are regular? 
a.  Only L1 and L2 
b.  Only L2, L3 and L4 
c.  Only L3 and L4 
d.  Only L3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Only L3

48.  Consider the following problem X. Given a Turing machine M over the input alphabet Σ, any state q of M And a word w∈Σ*, does the computation of M on w visit the state q? Which of the following statements about X is correct? 
a.  X is decidable 
b.  X is undecidable but partially decidable 
c.  X is undecidable and not even partially decidable 
d.  X is not a decision problem 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).X is undecidable but partially decidable

49.  The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as 
a.  Context Free 
b.  Regular 
c.  Deterministic Context Free 
d.  Recursive 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).Regular

50.  The Finite state machine described by the following state diagram with A as starting state, where an arc label is x / y and x stands for 1bit input and y stands for 2 bit output 
a.  Outputs the sum of the present and the previous bits of the input. 
b.  Outputs 01 whenever the input sequence contains 11. 
c.  Outputs 00 whenever the input sequence contains 10. 
d.  None of these 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).Outputs the sum of the present and the previous bits of the input.
