Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 25
Q321:
Fill in the blank: The language {an bn : n=0,1,2,3,…} is _______.
A. Regular
B. Nonregular
C. Finite
D. Empty
Correct Answer:
B
Chapter: 25
Q322:
How can an FA accepting the intersection of two regular languages be constructed?
A. By combining states of both FAs
B. By creating a new FA with transitions from both FAs
C. By building an FA with final states from both FAs
D. By converting and reducing previous FAs
Correct Answer:
A
Chapter: 25
Q323:
Fill in the blank: The language {an bn} is proven to be nonregular by showing that the FA must have _______.
A. An infinite number of states
B. A looping circuit
C. A finite number of states
D. No loops
Correct Answer:
B
Chapter: 25
Q324:
What is the correct regular expression for the language L1 ∩ L2 in the given example?
A. (b+abbab)a(a+bbaaba)(b+aba)
B. (a+b)aa(a+b)
C. (b+aba)
D. (a+b)a(a+b)
Correct Answer:
A
Chapter: 25
Q325:
Fill in the blank: An FA corresponding to the intersection of two regular languages has an initial state corresponding to the _______.
A. Initial state of both FAs
B. Final state of both FAs
C. Any state of the FAs
D. State with the most transitions
Correct Answer:
A
Chapter: 25
Q326:
What is the result of (L1 ∪ L2)c where L1 and L2 are regular languages?
A. L1c ∩ L2c
B. L1 ∪ L2c
C. L1c ∪ L2
D. L1 ∩ L2
Correct Answer:
A
Chapter: 25
Q327:
Fill in the blank: To prove a language is nonregular, one method is to show that the corresponding FA must have a _______.
A. Looping circuit
B. Finite number of states
C. Regular expression
D. Deterministic transitions
Correct Answer:
A
Chapter: 26
Q328:
What does the Pumping Lemma state about an infinite regular language?
A. There exist three strings x, y, and z such that xynz are words in L
B. There exist two strings x and y such that xy are words in L
C. There is a finite number of states in the FA
D. for every word w, there is a finite number of decompositions
Correct Answer:
A
Chapter: 26
Q329:
What is a nonregular language?
A. A language that can be expressed by a regular expression
B. A language that cannot be expressed by any regular expression
C. A language that is finite
D. A language with a finite number of states
Correct Answer:
B
Chapter: 26
Q330:
Which of the following languages is considered nonregular?
A. {an bn : n=0,1,2,3,…}
B. {a, b, c}
C. {aa, bb}
D. {a, b}
Correct Answer:
A
Chapter: 26
Q331:
If L1 and L2 are regular languages, what can be said about L1 ∩ L2?
A. It is always nonregular
B. It is also regular
C. It is always infinite
D. It is finite
Correct Answer:
B
Chapter: 26
Q332:
According to the example given, why does the FA accept words not in L?
A. Because it has an infinite number of states
B. Because it contains circuits that lead to invalid words
C. Because the language L is regular
D. Because L is finite
Correct Answer:
B
Chapter: 26
Q333:
Which theorem is used to prove that a language is nonregular by showing that it cannot be expressed by any FA?
A. Theorem of Finite Automata
B. Pumping Lemma
C. Kleene's Theorem
D. DeMorgan's Law
Correct Answer:
B
Chapter: 26
Q334:
For the language L = {Λ, ab, aabb, aaabbb, …}, which method is used to show it is nonregular?
A. Building a corresponding FA
B. Using the Pumping Lemma
C. Constructing a regular expression
D. Determining its finite states
Correct Answer:
B
Chapter: 26
Q335:
In the proof of the Pumping Lemma, what does the string y represent?
A. A string that is null
B. An empty string
C. A string that generates a circuit
D. A string that generates the path from the start state to a revisited state
Correct Answer:
C
Chapter: 26
Q336:
What example is used to illustrate the Pumping Lemma with a FA having 5 states?
A. The language {an bn : n=0,1,2,3,…}
B. The language EQUAL
C. The language PALINDROME
D. The language {a, b, c}
Correct Answer:
A
Chapter: 26
Q337:
The language EQUAL consists of strings with what property?
A. Number of a’s equal to number of b’s
B. Number of a’s less than number of b’s
C. Number of a’s greater than number of b’s
D. Any number of a’s and b’s
Correct Answer:
A
Chapter: 26
Q338:
The Pumping Lemma can be applied to which type of language to prove it is regular?
A. Regular languages
B. Nonregular languages
C. Finite languages
D. Infinite languages
Correct Answer:
A
Chapter: 27
Q339:
What does the Pumping Lemma version II state about an infinite language?
A. For all words w in L of length more than N, there are strings x, y, and z with length(x) + length(y) ≤ N such that w = xyz and all xynz are in L
B. For all words w in L, there exist three strings x, y, and z where y can be null
C. string xynz is not necessarily in L
D. All words of length more than N are accepted by an FA
Correct Answer:
B
Chapter: 27
Q340:
In the example given, why does the language PALINDROME not satisfy Pumping Lemma version II?
A. The word w can be decomposed such that xyyz is not in PALINDROME
B. The word w is too short to apply Pumping Lemma
C. version I was incorrectly applied
D. Pumping Lemma version II does not apply to any language
Correct Answer:
A