MCQ Computer Science

# 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

Explanation: A language over an alphabet R is a set of strings over A which is uncountable and 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.

Explanation: String accepted in previous DFA will not be accepted and non accepting string will be accepted .

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}

Explanation: The given option represents {0, 01} in different forms using set operations and Regular Expressions. The operator like ^, v, etc. are logical operation and they form invalid regular expressions when used.

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*) *

Explanation: The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.
Let P and Q be regular expressions,
R=Q+RP
R=Q+(Q+RP) P
R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,
If we do this recursively, we get:
R= QP*

5. If ?= {0,1}, then ?* will result to:
a) e
b) ?
c) ?
d) None of the mentioned

Explanation: The star operation brings together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, resulting only the empty string.

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

Explanation: As the input variables are under Kleene Operation, we need to include e,thus option c is not correct,thereby option (a) is the right answer.

7. (a+b)* is equivalent to
a) b*a*
b) (a*b*)*
c) a*b*
d) none of the mentioned

Explanation : None.

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

Explanation : None.

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

Explanation: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over 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

Explanation: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

11. Subset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) e-NFA to NFA

Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.

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

Explanation: The maximum number of states an equivalent DFA can comprise for its respective NFA with k states will be 2k.

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

Explanation: e does not appears on Input tape, e transition means a transition without scanning a symbol i.e. without moving the read head.

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