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.

91. S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of
a. All palindromes
b. All odd length palindromes
c. Strings that begin and end with the same symbol
d. All even length palindromes
View Answer Report Discuss Too Difficult!
Answer: (b).All odd length palindromes

92. Consider the below question:
recursive language
a. Not recursive
b. Regular
c. Context free but not regular
d. Recursively enumerable but not context free
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Context free but not regular

93. The language L= {0^i21^i | i≥0 } over the alphabet {0,1, 2} is:
a. not recursive
b. is recursive and is a deterministic CFL
c. is a regular language
d. is not a deterministic CFL but a CFL
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).is recursive and is a deterministic CFL

94. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA

Which of the following strings is generated by the grammar?
a. aaaabb
b. aabbbb
c. aabbab
d. abbbba
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).aabbab

95. Consider the below statement:
a. L1 only
b. L3 Only
c. L1 and L2
d. L2 and L3
View Answer Report Discuss Too Difficult!
Answer: (d).L2 and L3

96. Consider the following statements about the context free grammar

G = {S → SS, S → ab, S → ba, S → Ε}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?
a. I only
b. I and III only
c. II and III only
d. I, II and III
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).I and III only

97. Which one of the following grammars generates the language L = {a^ib^j | i ≠ j}
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult!
Answer: (d).D

98. Consider the languages:

L1 = {a^nb^nc^m | n, m > 0}
L2 = {a^nb^mc^m | n, m > 0}

Which one of the following statements is FALSE?
a. L1 ∩ L2 is a context-free language
b. L1 U L2 is a context-free language
c. L1 and L2 are context-free language
d. L1 ∩ L2 is a context sensitive language
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L1 ∩ L2 is a context-free language

99. Consider the languages:

L1 = {ww^R |w ∈ {0, 1}*}
L2 = {w#w^R | w ∈ {0, 1}*}, where # is a special symbol
L3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?
a. L1 is a deterministic CFL
b. L2 is a deterministic CFL
c. L3 is a CFL, but not a deterministic CFL
d. L3 is a deterministic CFL
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L2 is a deterministic CFL

100. Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
recursive language
a. 10110
b. 10010
c. 01010
d. 01001
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).10010

Page 10 of 14