A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

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:
regulr and non regular launguage
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 push-down 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?
regular languages
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 1-bit 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!
Answer: (a).Outputs the sum of the present and the previous bits of the input.

Page 5 of 14