Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 10
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
Correct Answer:
C
Chapter: 11
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
Correct Answer:
B
Chapter: 11
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
Correct Answer:
A
Chapter: 11
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
Correct Answer:
A
Chapter: 11
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
Correct Answer:
A
Chapter: 11
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
Correct Answer:
A
Chapter: 11
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
Correct Answer:
B
Chapter: 11
Q148:
Which algorithm step involves changing the notion of TG to GTG?
A. Step 1
B. Step 2
C. Step 3
D. Step 4
Correct Answer:
A
Chapter: 11
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
Correct Answer:
C
Chapter: 11
Q150:
How many steps are discussed in converting a TG to a GTG for determining RE?
A. Two
B. Three
C. Four
D. Five
Correct Answer:
C
Chapter: 11
Q151:
What is the role of a transition labeled by Λ in TGs?
A. Represents a regular language
B. Eliminates nondeterminism
C. Connects old and new states
D. Acts as a final state
Correct Answer:
C
Chapter: 11
Q152:
Fill in the blank: Kleene's Theorem Part II explains how a ___________ can be obtained corresponding to a TG.
A. FA
B. RE
C. GTG
D. DFA
Correct Answer:
B
Chapter: 11
Q153:
What happens when a state in a TG has multiple incoming transitions with corresponding REs?
A. It is eliminated
B. A single transition is introduced
C. The TG is converted to a DFA
D. The transitions are merged
Correct Answer:
D
Chapter: 11
Q154:
Fill in the blank: Kleene's Theorem Part I proves that if a language can be accepted by an FA, it can be accepted by a ___________.
A. TG
B. RE
C. GTG
D. NFA
Correct Answer:
A
Chapter: 12
Q155:
What does Kleene’s Theorem Part III state?
A. Any language can be expressed by an FA
B. If a language can be expressed by a RE, then there exists an FA accepting it
C. FA cannot accept a regular language
D. FA and RE are unrelated
Correct Answer:
B
Chapter: 12
Q156:
What is the purpose of the transition labeled by Λ in TGs?
A. To represent concatenation
B. To represent a union
C. To represent an empty transition
D. To represent a closure
Correct Answer:
C
Chapter: 12
Q157:
When reducing a TG to have a single initial and single final state, what is the main step?
A. Remove all loops
B. Eliminate all intermediate states
C. Introduce an additional initial and final state
D. Merge all transitions into one
Correct Answer:
C
Chapter: 12
Q158:
The language over Σ = {a, b} consisting of only b can be accepted by what type of automaton?
A. TG
B. GTG
C. FA
D. NFA
Correct Answer:
C
Chapter: 12
Q159:
In Method 1 (Union of two FAs), the union of two FAs corresponds to which operation on regular expressions?
A. Concatenation
B. Addition
C. Closure
D. Subtraction
Correct Answer:
B
Chapter: 12
Q160:
Which of the following regular expressions corresponds to a language accepted by an FA with a single transition edge?
A. (a+b)*b
B. (a+b)*(a+b)
C. b*+(a+bb)a*
D. ab
Correct Answer:
C