MCQ Computer Science

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

1. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned

Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.

2. In order to reduce the run time of a turing machine:
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned

Answer: One way to reduce the run time can be to increase the number of tapes. Sometimes, using two tapes can be used to avoid back and forth motions altogether.

3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned

Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.

4. Given:
L= {x??= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No

Explanation: It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus, It is not possible to build a DFA for the given Language.

5. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata

Explanation: They are collectively known as Transducers.

6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet

Explanation: A FA can be represented as FA= (Q, ?, d, q0, F) where Q=Finite Set of States, ?=Finite Input Alphabet, d=Transition Function, q0=Initial State, F=Final/Acceptance State).

7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
a) Compiler
b) Interpreter
d) None of the mentioned

Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.

8. The maximum number of transition which can be performed over a state in a DFA?
?= {a, b, c}
a) 1
b) 2
c) 3
d) 4

Explanation: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.
9. Finite automata requires minimum _______ number of stacks.
a) 1
b) 0
c) 2
d) None of the mentioned

Explanation: Finite automata doesn’t require any stack operation .

10. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned

Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
11. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned

Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.

12. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned

Explanation: An epsilon move is a transition from one state to another that doesn’t require any specific condition.

13. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false

Explanation: e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.

14. According to the given language, which among the following expressions does it corresponds to?
Language L={x?{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+e)4

Explanation: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be e. Thus e needs to be included in the given regular expression.

15. Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned