Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
B
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
View Answer
B
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
View Answer
A
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
View Answer
D
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
View Answer
A
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
View Answer
B
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
View Answer
C
Q238: Fill in the blank: Kleene's theorem helps construct FAs for regular expressions through ______.
- A: Decomposition
- B: Iteration
- C: Subtraction
- D: Elimination
View Answer
A
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
View Answer
B
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
View Answer
C