Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Multiple Choice Questions
Q341: Which language is used in the example to demonstrate Pumping Lemma version II's failure?
- A: PALINDROME
- B: PRIME
- C: BOOLEAN
- D: UNION
View Answer
B
Q342: What is the main idea of the Myhill-Nerode theorem?
- A: It partitions ∑* into distinct classes
- B: It shows all languages are regular
- C: It determines the number of states in a finite automaton
- D: It counts the number of strings in L
View Answer
A
Q343: For a regular language L, how many distinct classes does L generate according to the Myhill-Nerode theorem?
- A: Infinite number of classes
- B: Finite number of classes
- C: One class
- D: None
View Answer
A
Q344: If a language L is regular, what can be said about the number of classes it generates?
- A: It generates a finite number of classes
- B: It generates an infinite number of classes
- C: It generates one class
- D: None of the above
View Answer
A
Q345: Which of the following is an example of a language that partitions ∑* into distinct classes and is regular?
- A: The language of strings ending in 'a'
- B: The language of all strings over {a, b}
- C: The language of all strings of length 4
- D: The language of strings with no 'a'
View Answer
A
Q346: What does it mean for two strings x and y to belong to the same class in the context of a regular language?
- A: They end in the same state in an FA
- B: They have the same length
- C: They are identical in every character
- D: They are not distinguishable by any FA
View Answer
A
Q347: Which language is described as containing all strings with double 'a' and is regular according to the examples provided?
- A: The language of strings with no 'a'
- B: The language of strings without 'aa' but ending in 'a'
- C: The language of strings containing at least two 'a's
- D: The language of strings with at least one 'b'
View Answer
C
Q348: Which language is used in the example to demonstrate partitioning Σ* into four classes (C1, C2, C3, C4)?
- A: L = EVENEVEN
- B: L = PRIME
- C: L = PALINDROME
- D: L = {w ∈ {a,b}*: length(w) ≥ 2, w ends in ab or ba}
View Answer
A
Q349: How many classes does the language L = {w ∈ {a,b}*: length(w) ≥ 2, w ends in either ab or ba} partition Σ* into?
- A: Four
- B: Seven
- C: Two
- D: Five
View Answer
B
Q350: Which class in the language L = {w ∈ {a,b}*: length(w) ≥ 2, w ends in either ab or ba} contains only the null string?
- A: C1
- B: C2
- C: C3
- D: C4
View Answer
A