Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 15
Q201:
What is the relationship between FA and NFA according to Kleene’s theorem?
A. FA can be converted to TG only
B. NFA can be converted to FA
C. FA and NFA are equivalent
D. NFA is always smaller than FA
Correct Answer:
C
Chapter: 15
Q202:
Which of the following statements about NFAs is true?
A. NFAs cannot have multiple transitions for the same input
B. NFAs are equivalent to TGs
C. NFAs do not accept regular languages
D. NFAs cannot accept any strings
Correct Answer:
B
Chapter: 15
Q203:
Fill in the blank: An NFA can accept a string if _______ path reaches a final state.
A. every
B. at least one
C. no
D. none of the
Correct Answer:
B
Chapter: 15
Q204:
What is the key difference between FA and NFA?
A. FA has multiple initial states
B. NFA allows multiple transitions for the same input
C. FA is nondeterministic
D. NFA cannot accept strings with loops
Correct Answer:
B
Chapter: 15
Q205:
What does an NFA help to eliminate in a FA?
A. Final state
B. Initial state
C. Loop
D. Alphabet
Correct Answer:
C
Chapter: 15
Q206:
What is the result of converting an FA to NFA as per Kleene’s theorem?
A. FA is reduced to a single state
B. FA is converted to a TG
C. FA and NFA become equivalent
D. NFA cannot be converted back to FA
Correct Answer:
C
Chapter: 15
Q207:
What does an NFA do when there is no valid transition for an input?
A. Accepts the input
B. Rejects the input
C. Creates a new state
D. Loops indefinitely
Correct Answer:
B
Chapter: 15
Q208:
Fill in the blank: The NFA corresponding to the FA for (a+b)*b accepts strings ending with _______.
A. a
B. b
C. a or b
D. c
Correct Answer:
B
Chapter: 15
Q209:
In the example of applying an NFA to a maze, what is being solved?
A. A regular expression
B. A finite automaton
C. A maze puzzle
D. A transition table
Correct Answer:
C
Chapter: 15
Q210:
What is the main application of NFA in artificial intelligence?
A. Loop detection
B. Pathfinding
C. Language processing
D. Data encryption
Correct Answer:
B
Chapter: 15
Q211:
Fill in the blank: A NFA may have _______ transitions for a single input.
A. only one
B. no
C. more than one
D. none
Correct Answer:
C
Chapter: 15
Q212:
Which of the following is true for converting FA to NFA?
A. FA loses all its transitions
B. NFA adds additional states
C. FA and NFA become equivalent
D. NFA cannot accept the same language
Correct Answer:
C
Chapter: 15
Q213:
Fill in the blank: An NFA accepts a string if there is _______ path leading to a final state.
A. one
B. two
C. no
D. any
Correct Answer:
A
Chapter: 16
Q214:
What is the shortest string accepted by the NFA applied to a maze?
A. aaa
B. aaaaa
C. aaaaaa
D. aaaaaaaaa
Correct Answer:
C
Chapter: 16
Q215:
What is the regular expression for the NFA accepting infinite strings starting with six 'a's?
A. aaaaa(aa)*
B. aaaaaa(aa)*
C. aaaaaa(bb)*
D. aaaaaaaa
Correct Answer:
B
Chapter: 16
Q216:
What additional feature does an NFA with Null string (NFA∧) have compared to a regular NFA?
A. Infinite states
B. Multiple initial states
C. Null string transitions
D. Multiple final states
Correct Answer:
C
Chapter: 16
Q217:
Fill in the blank: An NFA∧ accepts strings defined over Σ = {a, b} that end in ______.
A. a
B. b
C. ab
D. ∧
Correct Answer:
B
Chapter: 16
Q218:
In method 1 of converting NFA to FA, what is the key step?
A. Eliminating all transitions
B. Converting NFA to a TG
C. Using Kleene’s theorem
D. Removing null transitions
Correct Answer:
C
Chapter: 16
Q219:
Which of the following is NOT true about NFA to FA conversion?
A. There may be more than one transition for a letter
B. An empty state is introduced for letters with no transitions
C. The NFA becomes deterministic
D. An NFA can never be equivalent to an FA
Correct Answer:
D
Chapter: 16
Q220:
What is introduced for a letter that has no transition in NFA during FA conversion?
A. Final state
B. Empty state
C. Null state
D. Infinite loop
Correct Answer:
B