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. A pushdown automation M = (Q, Σ, Γ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈ Q, a ∈ Σ ∪ {λ} and b ∈ Γ
(s1) δ(q, a, b) contains at most one element
(s2) if δ(q, λ, b) is not empty then δ(q, c, b) must be empty for every c ∈ Σ
a. only s1
b. only s2
c. both s1 and s2
d. neither s1 nor s2
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).both s1 and s2

92. For every context free grammar (G) there exists an algorithm that passes any w ∈ L(G) in number of steps proportional to
a. ln|w|
b. |w|
c. |w|^2
d. |w|^3
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).|w|^3

93. Match the following:

a. Context sensitive language          i. Deterministic finite automation
b. Regular grammar                            ii. Recursive enumerable
c. Context free grammar                     iii. Recursive language
d. Unrestricted grammar                     iv. Pushdown automation

Codes:
      a   b    c   d
a. ii    i    iv   iii
b. iii   iv   i    ii
c. iii   i    iv   ii
d. ii    iv   i   iii
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).iii   i    iv   ii

94. The statements s1 and s2 are given as:

s1: Context sensitive languages are closed under intersection, concatenation, substitution and inverse homomorphism.
s2: Context free languages are closed under complementation, substitution and homomorphism.

Which of the following is correct statement?
a. Both s1 and s2 are correct
b. s1 is correct and s2 is not correct
c. s1 is not correct and s2 is correct
d. Both s1 and s2 are not correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).s1 is correct and s2 is not correct

95. Consider the following statements :

I. Recursive languages are closed under complementation.
II. Recursively enumerable languages are closed under union.
III. Recursively enumerable languages are closed under complementation.

Which of the above statements are true ?
a. I only
b. I and II
c. I and III
d. II and III
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).I and II

96. Given the following statements :

(i) The power of deterministic finite state machine and nondeterministic finite state machine are same.
(ii) The power of deterministic pushdown automaton and nondeterministic pushdown automaton are same.

Which of the above is the correct statement(s) ?
a. Both (i) and (ii)
b. Only (i)
c. Only (ii)
d. Neither (i) nor (ii)
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Only (i)

97. Let Q(x, y) denote “x + y = 0” and let there be two quantifications given as follows, where x & y are real numbers. Then which of the following is valid ?
quantifications
a. (i) is true & (ii) is false
b. (i) is false & (ii) is true
c. (i) is false & (ii) is also false
d. both (i) & (ii) are true
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).(i) is false & (ii) is true

98. Which is not the correct statement(s) ?

(i) Every context sensitive language is recursive.
(ii) There is a recursive language that is not context sensitive.
a. (i) is true, (ii) is false
b. (i) is true and (ii) is true
c. (i) is false, (ii) is false
d. (i) is false and (ii) is true
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).(i) is true and (ii) is true

99. Which one of the following is not a Greibach Normal form grammar?

(i)            S ->a|bA|aA|bB
A->a
B->b
(ii)           S->a|aA|AB
A->a
B->b
(iii)          S->a|A|aA
A->a
a. (i) and (ii)
b. (i) and (iii)
c. (ii) and (iii)
d. (i), (ii) and (iii)
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).(ii) and (iii)

100. The equivalent grammar corresponding to the grammar G:S→aA,A→BB,B→aBb∣εG:S→aA,A→BB,B→aBb∣ε is
a. S→aA,A→BB,B→aBb
b. S→a∣aA,A→BB,B→aBb∣ab
c. S→a∣aA,A→BB∣B,B→aBb
d. S→a∣aA,A→BB∣B,B→aBb∣ab
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).S→a∣aA,A→BB∣B,B→aBb∣ab

Page 10 of 13