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.

71. Match the following NFAs with the regular expressions they correspond to

1. ϵ + 0(01*1 + 00) * 01*
2. ϵ + 0(10 *1 + 00) * 0
3. ϵ + 0(10 *1 + 10) *1
4. ϵ + 0(10 *1 + 10) *10 *
a. P - 2, Q - 1, R - 3, S - 4
b. P - 1, Q - 3, R - 2, S - 4
c. P - 1, Q - 2, R - 3, S - 4
d. P - 3, Q - 2, R - 1, S - 4
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).P - 1, Q - 2, R - 3, S - 4

72. Which of the following are regular sets?
a. I and IV only
b. I and III only
c. I only
d. IV only
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).I and IV only

73. Which of the following languages is regular?
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C

74. Consider the following Finite State Automaton. The language accepted by this automaton is given by the regular expression
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C

75. Which one of the following is TRUE?
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C

76. Consider the following statement:
a. {q0, q1, q2}
b. {q0, q1}
c. {q0, q1, q2, q3}
d. {q3}
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).{q0, q1, q2}

77. Which of the regular expressions given below represent the following DFA?
I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
a. I and II 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

78. Which one of the following is CORRECT?
a. Only (I)
b. Only (II)
c. Both (I) and (II)
d. Neither (I) nor (II)
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).Only (I)

79. If s is a string over (0 + 1)* then let n0(s) denote the number of 0’s in s and n1(s) the number of 1’s in s. Which one of the following languages is not regular?
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).D

80. Consider the machine M given below. The language recognized by M is :
a. {w ∈ {a, b}* / every a in w is followed by ex­actly two b's}
b. {w ∈ {a, b}* every a in w is followed by at least two b’}
c. {w ∈ {a, b}* w contains the substring 'abb'}
d. {w ∈ {a, b}* w does not contain 'aa' as a substring}
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).{w ∈ {a, b}* every a in w is followed by at least two b’}