Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 17
Q241:
In constructing an FA using Kleene’s theorem, which method is used to combine multiple FAs?
A. Subtraction
B. Union
C. Division
D. Concatenation
Correct Answer:
B
Chapter: 17
Q242:
What is the primary difference between NFA and FA?
A. FA has more transitions
B. NFA allows multiple transitions for the same letter
C. FA accepts infinite languages
D. NFA has fewer states
Correct Answer:
B
Chapter: 17
Q243:
Which of the following operations does NOT directly help in constructing FAs from NFAs?
A. Closure
B. Concatenation
C. Division
D. Union
Correct Answer:
C
Chapter: 18
Q244:
What method is used to convert NFA to FA when dealing with concatenation of FAs?
A. Introduce new final states
B. Add transitions between final states
C. Remove all transitions
D. Add additional start states
Correct Answer:
B
Chapter: 18
Q245:
Fill in the blank: To convert NFA to FA for concatenation, transitions are introduced connecting each final state of the first FA with the _______ of the second FA.
A. final states
B. initial state
C. middle states
D. end states
Correct Answer:
B
Chapter: 18
Q246:
Which situation is automatically accommodated if the first FA accepts the Null string?
A. The second FA must accept the Null string
B. The resulting FA will not accept any strings
C. The first FA should not accept any strings
D. The second FA must reject the Null string
Correct Answer:
A
Chapter: 18
Q247:
What happens when both FAs in a concatenation example accept the Null string?
A. The resulting NFA will not accept the Null string
B. The resulting NFA will accept the Null string
C. The resulting NFA will only accept strings with more than one character
D. The resulting NFA will reject all strings
Correct Answer:
B
Chapter: 18
Q248:
In constructing an NFA for the union of FAs, which new element is introduced?
A. A new start state
B. Additional transitions
C. More final states
D. A new intermediate state
Correct Answer:
A
Chapter: 18
Q249:
Fill in the blank: The closure of an FA is constructed by introducing an initial state that is also _______.
A. non-final
B. a final state
C. an intermediate state
D. a start state
Correct Answer:
B
Chapter: 18
Q250:
What is the main issue with making the initial state final when constructing an NFA for closure?
A. Acceptance of unwanted strings
B. Acceptance of only Null string
C. Loss of transitions
D. Creation of redundant states
Correct Answer:
A
Chapter: 18
Q251:
Which step is crucial when constructing an NFA for the closure of an FA?
A. Removing all negative signs
B. Adding transitions from the initial state to other states
C. Keeping the initial state non-final
D. Removing all final states
Correct Answer:
B
Chapter: 18
Q252:
In the NFA corresponding to closure of an FA, which state must be introduced?
A. A new non-final state
B. A new final state
C. An additional start state
D. An additional intermediate state
Correct Answer:
B
Chapter: 18
Q253:
What does the concatenation of FAs involve in NFA construction?
A. Creating additional states for each letter
B. Introducing transitions between final states of the first FA and the initial state of the second FA
C. Removing all transitions from final states
D. Creating new start states for each FA
Correct Answer:
B
Chapter: 18
Q254:
Fill in the blank: If the second FA in a concatenation example accepts the Null string, then the resulting FA must accept strings from _______.
A. the second FA only
B. the first FA only
C. both FAs
D. neither FAs
Correct Answer:
C
Chapter: 19
Q255:
In an FA corresponding to FA*, what does the FA accept?
A. Only the Null string
B. Every string
C. No strings
D. Strings ending in 'a'
Correct Answer:
B
Chapter: 19
Q256:
Fill in the blank: The memory required to recognize a language is a restriction that requires a single pass from _______ for any string.
A. left to right
B. right to left
C. top to bottom
D. bottom to top
Correct Answer:
A
Chapter: 19
Q257:
For the language L = {w ∈ {a,b}*: w neither ends in ab nor in ba}, how many states are required to recognize it according to the example?
A. Seven states
B. Five states
C. Ten states
D. Two states
Correct Answer:
A
Chapter: 19
Q258:
How many states are required to recognize the language L3 of strings where the third letter from the right is 'a'?
A. 15 states
B. 20 states
C. 10 states
D. 25 states
Correct Answer:
A
Chapter: 19
Q259:
Fill in the blank: To recognize strings where the 20th letter from the right is '1', the FA requires _______ states.
A. 2097151
B. 15
C. 100
D. 50
Correct Answer:
A
Chapter: 19
Q260:
If two strings x and y are distinguishable with respect to a language L, what must exist?
A. A string z such that xz ∈ L and yz ∉ L or xz ∉ L and yz ∈ L
B. Both xz and yz must belong to L
C. Both xz and yz must not belong to L
D. xz must always belong to L
Correct Answer:
A