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.

61. Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has ................ equivalence classes.
a. 2
b. 4
c. 5
d. 6
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).6

62. Let L = {0^n1^n | n≥0} be a context free language.
Which of the following is correct?
a. L’ is context free and L^k is not context free for any k≥1
b. L’ is not context free and L^k is context free for any k≥1
c. Both L’ and L^k is for any k≥1 are context free
d. Both L’ and L^k is for any k≥1 are not context free
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both L’ and L^k is for any k≥1 are context free

63. Given a Turing Machine

M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3})

Where δ is a transition function defined as

δ(q0,a) = (q1,a,R)
δ(q1,b) = (q2,b,R)
δ(q2,a) = (q2,a,R)
δ(q2,b) = (q3,b,R)

The language L(M) accepted by the Turing Machine is given as:
a. aa*b
b. abab
c. aba*b
d. aba*
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).aba*b

64. Match the following :

List - I                                                             List - II
(a) {a^n b^n|n > 0} is a deterministic                  (i) but not recursive language
context free language        
(b) The complement of {a^n b^n a^n|n > 0}         (ii) but not context free language
is a context free language
(c) {a^n b^n a^n} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation
(d) L is a recursive language                         (iv) but not regular

Codes :
     (a)   (b)   (c)   (d)
a. (i)   (ii)   (iii)   (iv)
b. (i)   (ii)   (iv)   (iii)
c. (iv) (iii)  (ii)    (i)
d. None of the above is correct match
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).None of the above is correct match

65. The language of all non-null strings of a’s can be defined by a context free grammar as
follow :

S→a S|S a| a

The word a^3 can be generated by ................ different trees.
a. Two
b. Three
c. Four
d. Five
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Four

66. The context free grammar given by

S→XYX
X→aX|bX|λ
Y→bbb

generates the language which is defined by regular expression:
a. (a+b)*bbb
b. abbb(a+b)*
c. (a+b)*(bbb)(a+b)*
d. (a+b)(bbb)(a+b)*
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).(a+b)*(bbb)(a+b)*

67. There are exactly ................ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
a. 64
b. 256
c. 1024
d. 5832
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).5832

68. Given the following two languages :

L1={a^n b a^n|n>0}
L2={a^n b a^n b^n+1|n>0}

Which of the following is correct?
a. L1 is context free language and L2 is not context free language
b. L1 is not context free language and L2 is context free language
c. Both L1 and L2 are context free languages
d. Both L1 and L2 are not context free languages
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L1 is context free language and L2 is not context free language

69. Consider a language A defined over the alphabet ∑={0, 1} as A = {0^[n/2] 1^n: n >= 0} .
The expression [n/2] means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.

Which of the following is not an example of a string in A ?
a. 011
b. 0111
c. 0011
d. 001111
View Answer Report Discuss Too Difficult!
Answer: (c).0011

70. A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β

I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)
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: (d).I, II and III

Page 7 of 13