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.

101. Which of the following languages are context-free?

L1 = {a^m b^n a^n b^m ⎪ m, n ≥ 1}
L2 = {a^m b^n a^m b^n ⎪ m, n ≥ 1}
L3 = {a^m b^n ⎪ m = 2n + 1}
a. L1 and L2 only
b. L1 and L3 only
c. L2 and L3 only
d. L3 only
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L1 and L3 only

102. Which one of the following statements is FALSE ?
a. There exist context-free languages such that all the context-free grammars generating them are ambiguous
b. An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it
c. Both deterministic and non-deterministic pushdown automata always accept the same set of languages
d. A finite set of string from one alphabet is always a regular language
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both deterministic and non-deterministic pushdown automata always accept the same set of languages

103. If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations.
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult!
Answer: (d).D

104. Consider the following context-free grammars. Which one of the following pairs of languages is generated by G1 and G2, respectively.
context-free grammars
context-free grammars
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).D

105. Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)
(s, ϵ, Z0) → (f, ϵ)
(s, a, X) → (s, XXX)
(s, b, X) → (t, ϵ)
(t, b, X) → (t,.ϵ)
(t, c, X) → (u, ϵ)
(u, c, X) → (u, ϵ)
(u, ϵ, Z0) → (f, ϵ)

The language accepted by the PDA is
a. {a^lb^mc^n | l = m = n}
b. {a^lb^mc^n | l = m}
c. {a^lb^mc^n | 2l = m+n}
d. {a^lb^mc^n | m=n}
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).{a^lb^mc^n | 2l = m+n}

106. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S→aS∣A
A→aAb∣bAa∣ϵ

Which of the following strings is generated by the grammar above?
a. aabbaba
b. aabaaba
c. abababb
d. aabbaab
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).aabbaab

107. Consider 2 scenarios:

C1: For DFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

C2: For NFA (ϕ, Ʃ, δ, qo, F),
if F = ϕ, then L = Ʃ*

Where F = Final states set
ϕ = Total states set

Choose the correct option ?
a. Both are true
b. Both are False
c. C1 is true, C2 is false
d. C1 is false, C2 is true
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C1 is true, C2 is false

108. Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG ‘G’ and given string ‘w’, what is the relation between l , P , r ?
a. l ≤ P ≥ r
b. l = P = r
c. l ≥ P ≤ r
d. none of these
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).l = P = r

109. Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine,
there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union
and complementation.
3. Turing decidable languages are closed under intersection
and complementation.
4. Turing recognizable languages are closed under union
and intersection.
a. 1 and 4 only
b. 1 and 3 only
c. 2 only
d. 3 only
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).2 only

110. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

(A) L2 – L1 is recursively enumerable.
(B) L1 – L3 is recursively enumerable
(C) L2 ∩ L1 is recursively enumerable
(D) L2 ∪ L1 is recursively enumerable.
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).B