Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q141: Which of the following does Kleene’s Theorem prove?
- A: An FA is more powerful than a TG
- B: All languages can be expressed by an RE
- C: A TG, FA, and RE can express the same language
- D: Only regular languages are accepted by FAs
View Answer
C
Q142: What is the main goal of Kleene's Theorem Part II?
- A: Prove TGs are non-deterministic
- B: Prove REs correspond to TGs
- C: Convert TGs to DFAs
- D: Show the minimal states in FAs
View Answer
B
Q143: Which step involves introducing a new start state when a TG has more than one start state?
- A: Step 1
- B: Step 2
- C: Step 3
- D: Step 4
View Answer
A
Q144: If a TG has more than one final state, what is introduced to connect the old final states?
- A: A new final state
- B: A new transition
- C: A new initial state
- D: A new loop
View Answer
A
Q145: In Kleene's theorem, which step eliminates the middle state when three states are connected?
- A: Step 4
- B: Step 3
- C: Step 2
- D: Step 1
View Answer
A
Q146: What is the purpose of replacing multiple incoming transition edges with a single one?
- A: Simplify the TG
- B: Minimize states
- C: Eliminate loops
- D: Create DFA-like behavior
View Answer
A
Q147: What is the final result after eliminating states 2 and 3 in the example provided?
- A: (aa+bb)(a+b)*
- B: (ab+ba)(aa+b)*(aaa+bba)
- C: (a+b)(aa+bb)
- D: (a+b)aabb
View Answer
B
Q148: Which algorithm step involves changing the notion of TG to GTG?
- A: Step 1
- B: Step 2
- C: Step 3
- D: Step 4
View Answer
A
Q149: In the example of state elimination, what is the result of eliminating state 4?
- A: A simplified RE
- B: A more complex TG
- C: A single transition
- D: A loop with final state
View Answer
C
Q150: How many steps are discussed in converting a TG to a GTG for determining RE?
- A: Two
- B: Three
- C: Four
- D: Five
View Answer
C