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 *
NFAs with the regular expressions
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?
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?
regular language
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
Finite State Automaton
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?
regular language
a. A
b. B
c. C
d. D
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).C

76. Consider the following statement:
finite automata
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
DFA
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?
regular language
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?
Regular languages and finite automata
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!
Answer: (b).{w ∈ {a, b}* every a in w is followed by at least two b’}

Page 8 of 14