Theory of Automata MCQs with Answers
Practice important Theory of Automata MCQs with answers and explanations.
Chapter: 23
Q301:
Fill in the blank: In the Mealy machine, the output is determined using the relation output = __________.
A. (input) OR (old B)
B. (input) NAND (old A AND old B)
C. (input) AND (old A OR old B)
D. old A AND (input)
Correct Answer:
A
Chapter: 23
Q302:
What happens to the state q0 when reading the letter 0?
A. The new state becomes (1,0)
B. The new state remains (0,0)
C. The new state becomes (0,1)
D. The new state becomes (1,1)
Correct Answer:
A
Chapter: 23
Q303:
Fill in the blank: The delay box introduces __________ in the sequential circuit.
A. States
B. Outputs
C. Transitions
D. Inputs
Correct Answer:
A
Chapter: 23
Q304:
When running the string '01101110' on the machine, which state will the machine end up in?
A. q0
B. q1
C. q2
D. q3
Correct Answer:
D
Chapter: 23
Q305:
Fill in the blank: The NAND box provides the __________ of Boolean AND output.
A. Addition
B. Subtraction
C. Complement
D. Multiplication
Correct Answer:
C
Chapter: 24
Q306:
What is a regular language?
A. A language that can be expressed by a regular expression
B. A language that can be expressed by a context-free grammar
C. A language that can be expressed by a Turing machine
D. A language that can be expressed by a finite automaton
Correct Answer:
A
Chapter: 24
Q307:
If L1 and L2 are regular languages, which of the following operations will also produce a regular language?
A. L1 + L2
B. L1L2
C. L1*
D. All of the above
Correct Answer:
D
Chapter: 24
Q308:
Fill in the blank: A TG accepting L1 + L2 can be constructed using _______.
A. L1 and L2 expressed by TG1 and TG2
B. Only L1 expressed by TG1
C. Only L2 expressed by TG2
D. Any two random TGs
Correct Answer:
A
Chapter: 24
Q309:
What is the complement of a language L?
A. The language of all strings over the alphabet not in L
B. The language of all strings in L
C. The union of L and its complement
D. The intersection of L and its complement
Correct Answer:
A
Chapter: 24
Q310:
According to Kleene's theorem, what happens to an FA when final and non-final states are swapped?
A. It will accept the complement of the original language
B. It will accept the union of the original language
C. It will accept the intersection of the original language
D. It will accept the original language
Correct Answer:
A
Chapter: 24
Q311:
Fill in the blank: If L is a language over an alphabet Σ, then (Lc)c = _______.
A. L
B. Σ
C. Lc
D. ∅
Correct Answer:
A
Chapter: 24
Q312:
How is the complement of L1 ∪ L2 related to the complements of L1 and L2?
A. (L1 ∪ L2)c = L1c ∩ L2c
B. (L1 ∪ L2)c = L1c ∪ L2c
C. (L1 ∪ L2)c = L1 ∩ L2
D. (L1 ∪ L2)c = (L1c ∪ L2c)c
Correct Answer:
A
Chapter: 24
Q313:
Fill in the blank: To describe the complement of a language, it is essential to describe the _______.
A. Alphabet of the language
B. States of the FA
C. Transitions of the FA
D. Regular expressions used
Correct Answer:
A
Chapter: 24
Q314:
What does DeMorgan's law for sets state about the intersection of two regular languages?
A. L1 ∩ L2 is regular
B. L1 ∪ L2 is regular
C. L1c ∪ L2c is regular
D. (L1 ∩ L2)c = L1c ∪ L2c
Correct Answer:
A
Chapter: 24
Q315:
In the given example, if L = {aba, abb}, what is the FA accepting L?
A. An FA with final states accepting only 'aba' and 'abb'
B. An FA accepting all strings except 'aba' and 'abb'
C. An FA accepting all possible strings
D. An FA with no accepting states
Correct Answer:
A
Chapter: 24
Q316:
Fill in the blank: The theorem stating that if L1 and L2 are regular languages, then L1 ∩ L2 is also regular is proved using _______.
A. DeMorgan's law for sets
B. Kleene's theorem
C. Pumping lemma
D. Myhill-Nerode theorem
Correct Answer:
A
Chapter: 25
Q317:
What does DeMorgan's law for sets state about the intersection of two regular languages?
A. (L1c ∪ L2c)c = L1 ∩ L2
B. (L1 ∪ L2)c = L1c ∩ L2c
C. (L1 ∪ L2)c = L1 ∩ L2c
D. (L1 ∩ L2)c = L1 ∪ L2c
Correct Answer:
A
Chapter: 25
Q318:
If L1 and L2 are regular languages, which operation results in a regular language?
A. L1 ∩ L2
B. L1 ∪ L2
C. L1c
D. All of the above
Correct Answer:
D
Chapter: 25
Q319:
Fill in the blank: Finding regular expressions defining the language L1 ∩ L2 is _______.
A. Easy
B. Difficult
C. Impossible
D. Always straightforward
Correct Answer:
B
Chapter: 25
Q320:
What is an example of a nonregular language?
A. Language of all palindromes
B. Language of all strings with an even number of a’s
C. Language of all strings over {a, b}
D. Language of all strings with an odd number of b’s
Correct Answer:
A