Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
B
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
View Answer
B
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
View Answer
B
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
View Answer
C
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'
View Answer
B
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A
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
View Answer
A