This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Finite Automata”.
1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
View Answer
Explanation: A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. Moore Machine is an application of:
a) Finite automata without input
b) Finite automata with output
c) Non- Finite automata with output
d) None of the mentioned
View Answer
Explanation: Finite automaton with an output is categorize din two parts: Moore M/C and Mealy M/C.
3. In mealy machine, the O/P depends upon?
a) State
b) Previous State
c) State and Input
d) Only Input
View Answer
Explanation: Definition of Mealy Machine.
4. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned
View Answer
Explanation: The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.
5. Which of the following not an example Bounded Information?
a) fan switch outputs {on, off}
b) electricity meter reading
c) colour of the traffic light at the moment
d) none of the mentioned
View Answer
Explanation: Bounded information refers to one whose output is limited and it cannot be said what were the recorded outputs previously until memorized.
6. The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA
View Answer
Explanation: For a string of n characters with no repetitive substrings, the number of states required to pass the string is n+1.
7. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite
View Answer
Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.
8. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
View Answer
Explanation: States, input symbols,initial state,accepting state and transition function.
9. Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false
View Answer
Explanation: Statement 1 and 2 always true for a given Language.
10. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
View Answer
Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
11.ubset Construction method refers to:
a) Conversion of NFA to DFA
b) DFA minimization
c) Eliminating Null references
d) e-NFA to NFA
View Answer
Explanation: The conversion of a non-deterministic automata into a deterministic one is a process we call subset construction or power set construction.
12.Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
View Answer
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
13.Given Language: {x | it is divisible by 3}
The total number of final states to be assumed in order to pass the number constituting {0, 1} is
a) 0
b) 1
c) 2
d) 3
View Answer
Explanation: The DFA for the given language can be constructed.
14. According to the given transitions, which among the following are the epsilon closures of q1 for the given NFA?
? (q1, e) = {q2, q3, q4}
? (q4, 1) =q1
? (q1, e) =q1
a) q4
b) q2
c) q1
d) q1, q2, q3, q4
View Answer
Explanation: The set of states which can be reached from q using e-transitions, is called the e-closure over state q.
15. The automaton which allows transformation to a new state without consuming any input symbols:
a) NFA
b) DFA
c) NFA-l
d) All of the mentioned
View Answer
Explanation: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.
