 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

 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

 103. If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M is a memory reference), then the sequence of operations. a. A b. B c. C d. D

 104. Consider the following context-free grammars. Which one of the following pairs of languages is generated by G1 and G2, respectively.  a. A b. B c. C 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}

 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

 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