Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 27
Q341:
Which language is used in the example to demonstrate Pumping Lemma version II's failure?
A. PALINDROME
B. PRIME
C. BOOLEAN
D. UNION
Correct Answer:
B
Chapter: 27
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
Correct Answer:
A
Chapter: 27
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
Correct Answer:
A
Chapter: 27
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
Correct Answer:
A
Chapter: 27
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'
Correct Answer:
A
Chapter: 27
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
Correct Answer:
A
Chapter: 27
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'
Correct Answer:
C
Chapter: 28
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}
Correct Answer:
A
Chapter: 28
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
Correct Answer:
B
Chapter: 28
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
Correct Answer:
A
Chapter: 28
Q351:
In the example provided, what is the result of the quotient of two regular languages according to the theorem?
A. The quotient is always regular
B. The quotient is not regular
C. The theorem is not applicable
D. The result is indeterminate
Correct Answer:
B
Chapter: 28
Q352:
According to the pseudo theorem, what is required for a language Q to be regular if PQ=R and P and R are regular?
A. Q must be regular
B. P must be regular
C. R must be regular
D. P and R must be regular
Correct Answer:
C
Chapter: 28
Q353:
What is the main point of disproof for the pseudo theorem?
A. Q is regular but not accepted by any FA
B. Q is not regular and thus disproves the theorem
C. Q is regular but does not satisfy PQ=R
D. Q is regular and hence the theorem is proved
Correct Answer:
B
Chapter: 28
Q354:
If two languages R and Q are given, what does the language Pref(Q in R) represent?
A. The set of strings that, when concatenated to the front of some word in Q, produce a word in R
B. The set of all words in R
C. The set of all words in Q
D. The set of prefixes of words in R
Correct Answer:
D
Chapter: 28
Q355:
In the language L = EVENEVEN, what is the class containing all strings with even number of a’s and even number of b’s?
A. C1
B. C2
C. C3
D. C4
Correct Answer:
D
Chapter: 28
Q356:
Which language’s prefixes are defined by the example Q = {aa, abaaabb, bbaaaaa, bbbbbbbbbb} and R = {b, bbbb, bbbaaa, bbbaaaaa}?
A. Pref(Q in R)
B. Pref(R in Q)
C. Q in R
D. R in Q
Correct Answer:
A
Chapter: 28
Q357:
What is the result of taking the quotient of the language a* with a language that includes {anbn: n=0,1,2,…} and b*?
A. a*b*
B. b*
C. a* {anbn}
D. a* {anbn} b*
Correct Answer:
A
Chapter: 29
Q358:
What does the language Pref(Q in R) represent?
A. A regular language
B. A non-regular language
C. A context-free language
D. A Turing machine language
Correct Answer:
A
Chapter: 29
Q359:
If R is regular and Q is any language, what can be said about Pref(Q in R)?
A. Always non-regular
B. Always regular
C. Regular if R is regular
D. Non-regular if Q is infinite
Correct Answer:
B
Chapter: 29
Q360:
What type of problem is one that can be solved in a finite number of steps?
A. Undecidable
B. Decidable
C. Effectively solvable
D. Non-effectively solvable
Correct Answer:
C