Quiz on Automata Theory

Why do we need Automata Theory?

• To understand how machines compute functions and solve problems

• To create physical robots

• To design microprocessors

• To study quantum mechanics

What is the key difference between a DFA and an NFA?

• A DFA allows multiple transitions for the same input, while an NFA does not

• An NFA allows multiple transitions for the same input, while a DFA does not

• An NFA does not have a start state

• A DFA can recognize more languages than an NFA

Which of the following statements is true regarding the equivalence of NFA and DFA?

• Every DFA has an equivalent NFA

• Every NFA has an equivalent DFA

• NFAs and DFAs recognize the same class of languages

• All of the above

What is an epsilon (ε) transition in NFA?

• A transition that requires input to change states

• A transition that does not consume any input

• A transition that moves back to the start state

• A transition that loops infinitely

What happens when we minimize a DFA?

• The number of states increases

• The number of states decreases or remains the same

• The language recognized by the DFA changes

• The DFA stops being deterministic

Which of the following is NOT a valid regular expression operation?

• Concatenation

• Union

• Complementation

• Kleene Star

Which of the following is true about regular languages?

• Every finite language is regular

• Every infinite language is regular

• Every regular language is infinite

• Regular languages cannot be represented using DFAs

The Pumping Lemma is used to prove that:

• A language is regular

• A language is not regular

• A finite automaton is deterministic

• A regular language can be converted to a DFA

Which of the following languages can be proved to be non-regular using the Pumping Lemma?

• L = {aⁿbⁿ | n ≥ 0}

• L = {w | w contains an even number of a's}

• L = {w | w starts with 'a' and ends with 'b'}

• L = {a, ab, abb, abbb, ...}

How many types of grammars are defined in Chomsky's hierarchy?

• 2

• 3

• 4

• 5