Engineering Questions with Answers - Multiple Choice Questions
MCQs on Equivalence of NFA and DFA
1 - Question
Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
View Answer
Answer: d
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
2 - Question
It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said
View Answer
Answer: a
Explanation: We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.
3 - Question
Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
View Answer
Answer: d
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
4 - Question
John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
a) 9
b) 11
c) 12
d) 15
View Answer
Answer: a
Explanation:
5 - Question
Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
View Answer
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
6 - Question
Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
View Answer
Answer: a
Explanation: Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.
7 - Question
Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
View Answer
Answer: d
Explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.
8 - Question
L1= {w | w does not contain the string tr }
L2 = {w | w does contain the string tr}
Given ∑ = {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
View Answer
Answer: a
Explanation:
9 - Question
Predict the number of transitions required to automate the following language using only 3 states:
L = {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
View Answer
Answer: a
Explanation:
10 - Question
The total number of states to build the given language using DFA:
L = {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
View Answer
Answer: a
Explanation: We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.