Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 16
Q221:
In the conversion of NFA to FA, what is done when a letter has more than one transition?
A. A state representing all transitions is created
B. The letter is removed from the alphabet
C. A new state is added
D. The NFA is discarded
Correct Answer:
A
Chapter: 16
Q222:
Fill in the blank: Method 2 of converting NFA to FA creates ______ for each letter with no transition.
A. a new state
B. an empty state
C. a combination of states
D. a final state
Correct Answer:
B
Chapter: 16
Q223:
What type of strings are accepted by the NFA∧ in the example given?
A. Strings ending in ∧
B. Strings starting with a
C. Strings ending with b
D. Strings containing a loop
Correct Answer:
C
Chapter: 16
Q224:
Which of the following languages is accepted by an NFA with Σ = {a, b} and ending with a?
A. bb
B. aa
C. bba
D. ba
Correct Answer:
D
Chapter: 16
Q225:
In converting an NFA to FA using Method 3, what is used to create the transition table for the FA?
A. Empty states
B. Null transitions
C. Combination of states
D. Final states
Correct Answer:
C
Chapter: 16
Q226:
Fill in the blank: NFA to FA conversion involves introducing ______ states for certain letters.
A. combination
B. final
C. empty
D. starting
Correct Answer:
C
Chapter: 16
Q227:
What is the key concept demonstrated by applying an NFA to a maze problem?
A. Pathfinding
B. Loop detection
C. String matching
D. Regular expression generation
Correct Answer:
A
Chapter: 16
Q228:
What is the first step in converting an NFA to FA using Method 2?
A. Eliminating all transitions
B. Starting from the initial state
C. Adding null transitions
D. Removing loops
Correct Answer:
B
Chapter: 17
Q229:
What is Method 3 of converting NFA to FA primarily concerned with?
A. Introducing new transitions
B. Using a single state for multiple transitions
C. Introducing empty states
D. Deleting unnecessary states
Correct Answer:
C
Chapter: 17
Q230:
Fill in the blank: The NFA in Method 3 accepts strings containing ______.
A. aa
B. bb
C. ba
D. ab
Correct Answer:
B
Chapter: 17
Q231:
What is the purpose of Kleene’s Theorem in NFA and FA conversion?
A. To create random transitions
B. To prove every FA has a corresponding RE
C. To generate more states in the FA
D. To eliminate null transitions
Correct Answer:
B
Chapter: 17
Q232:
In Kleene’s theorem, how can a complicated RE be simplified to construct an FA?
A. By removing transitions
B. By decomposing into simple REs
C. By adding null transitions
D. By converting FA to NFA
Correct Answer:
B
Chapter: 17
Q233:
Fill in the blank: The RE r = aa+bbb represents an FA accepting _______.
A. Strings of 'a's and 'b's
B. Strings ending in 'b'
C. Strings starting with 'b'
D. Strings of length 1
Correct Answer:
A
Chapter: 17
Q234:
Which of the following is NOT a part of Kleene’s theorem?
A. Union of FAs
B. Concatenation of FAs
C. Closure of FAs
D. Subtraction of FAs
Correct Answer:
D
Chapter: 17
Q235:
What is the first step to construct an FA for L1 = {a} according to Kleene’s theorem?
A. Build an NFA for L1
B. Add null transitions
C. Remove unnecessary states
D. Use a regular expression
Correct Answer:
A
Chapter: 17
Q236:
What must be introduced to an NFA to create nondeterminism in the union of two FAs?
A. A new final state
B. A new start state
C. More transitions
D. A null state
Correct Answer:
B
Chapter: 17
Q237:
In constructing the NFA equivalent to the union of FAs, what must be done to the old start state?
A. Add transitions to it
B. Remove it
C. Eliminate its negative sign
D. Make it a final state
Correct Answer:
C
Chapter: 17
Q238:
Fill in the blank: Kleene's theorem helps construct FAs for regular expressions through ______.
A. Decomposition
B. Iteration
C. Subtraction
D. Elimination
Correct Answer:
A
Chapter: 17
Q239:
What is a key component in Method 2 of constructing FAs from NFAs?
A. Adding more states
B. Concatenation of FAs
C. Elimination of final states
D. Null transition handling
Correct Answer:
B
Chapter: 17
Q240:
Which of the following represents the closure operation in constructing NFAs?
A. Adding new states
B. Union of two FAs
C. Looping transitions
D. Removing empty transitions
Correct Answer:
C