Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-26

1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite

2. Complement of a DFA can be obtained by
a) making starting state as final state.
b) no trival method.
c) making final states non-final and non-final to final.
d) make final as a starting state.
3. Which of the following does not represents the given language?
Language: {0,01}
a) 0+01
b) {0} U {01}
c) {0} U {0}{1}
d) {0} ^ {01}
4. P, O, R be regular expression over ?, P is not e, then
R=Q + RP has a unique solution:
a) Q*P
b) QP*
c) Q*P*
d) (P*O*) *
5. If ?= {0,1}, then ?* will result to:
a) e
b) ?
c) ?
d) None of the mentioned
6. Generate a regular expression for the following problem statement:
P(x): String of length 6 or less for å={0,1}*
a) (1+0+e)6
b) (10)6
c) (1+0)(1+0)(1+0)(1+0)(1+0)(1+0)
d) More than one of the mentioned is correct
7. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned
8. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular
9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
?= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language
10. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2
11. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) e-NFA to NFA

12. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?
a) 226
b) 224
c) 225
d) 223

13. State true or false?
Statement: e (Input) does not appears on Input tape.
a) True
b) False
Answer: a

14. Number of states require to simulate a computer with memory capable of storing ‘3’ words each of length ‘8’.
a) 3 * 28
b) 2(3*8)
c) 2(3+8)
d) None of the mentioned
15. Which phase of compiler includes Lexical Analysis?
a) 1
b) 2
c) 3
d) Its primary function, not in any phase