Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q361: What is a decision procedure?
- A: A solution with multiple steps
- B: An undecidable problem
- C: A yes/no solution to a problem
- D: A non-decidable process
View Answer
C
Q362: Which method is used to determine if two FAs accept equivalent languages?
- A: Theorem of Automata
- B: Method 1
- C: Regular Expression Equivalence
- D: Boolean Algebra Method
View Answer
B
Q363: If L1 and L2 are regular languages, what can be said about L1 ∩ L2?
- A: It's not regular
- B: It's always regular
- C: It depends on the alphabet
- D: It's undecidable
View Answer
B
Q364: How can you determine if a regular expression defines any word using Method 1?
- A: Remove the '+' symbol
- B: Separate the left side of the '+'
- C: Remove all '*' from the expression
- D: Find the minimal FA
View Answer
C
Q365: What regular expression is used in Method 1 to check language non-emptiness?
- A: (a+b)*
- B: (a+∧)(ab+ba)(a+∧)
- C: ab*(ba)*
- D: ∧(a+b)*
View Answer
B
Q366: In the proof of Pref(Q in R), what is required to be marked in the finite automaton (FA)?
- A: All initial states
- B: All final states
- C: At least one state
- D: All accepting states
View Answer
C
Q367: What happens if no state in the FA is marked according to Method 2?
- A: The FA accepts some words
- B: The FA is regular
- C: The FA accepts no words
- D: The FA accepts all possible words
View Answer
C
Q368: What is the problem in determining whether a state of FA should be marked when Q is infinite?
- A: It's impossible to mark any state
- B: The process is non-constructive
- C: FA becomes non-deterministic
- D: FA becomes undecidable
View Answer
B
Q369: Which method involves marking states and tracing paths from initial to final states?
- A: Method 1
- B: Regularization process
- C: Method 2
- D: FA construction
View Answer
C
Q370: What does it mean when an FA accepts no string after applying Method 2?
- A: The FA is deterministic
- B: The FA is empty
- C: The FA is ambiguous
- D: The FA is infinite
View Answer
B