Finite Automata Quiz

Which of the following is true for a finite automaton?

• It has an infinite number of states

• It has a finite number of states

• It cannot recognize any language

• It does not have an initial state

A finite automaton is said to be deterministic if:

• It has multiple transitions for a single input from a state

• It has at most one transition for a single input from a state

• It accepts all types of languages

• It has an infinite number of states

In a finite automaton, the transition function maps:

• A state to a set of states

• A state and input symbol to a unique state

• A state to another state without input

• An input symbol to a state

Which of the following is NOT a property of a Deterministic Finite Automaton (DFA)?

• Every state has exactly one transition for each input symbol

• It can recognize regular languages

• It may have epsilon (ε) transitions

• It has a finite number of states

The set of all strings over {a, b} that contain 'aa' as a substring can be recognized by:

• A finite automaton

• A pushdown automaton

• A Turing machine

• None of the above

The power of a Nondeterministic Finite Automaton (NFA) compared to a Deterministic Finite Automaton (DFA) is:

• More powerful

• Less powerful

• Equally powerful

• Cannot be determined

What is the minimum number of states required to recognize an empty language using a DFA?

• 0

• 1

• 2

• Cannot be determined

Which of the following statements is true for every DFA?

• It must have at least one accepting state

• It must have exactly one initial state

• It must have at least one transition for each symbol

• It must have more states than an equivalent NFA

If an NFA has n states, the equivalent DFA may have at most:

• n+1 states

• 2^n states

• n^2 states

• n! states

Which of the following problems can be solved using a finite automaton?

• Checking if a string is a palindrome

• Checking if a string contains an equal number of a's and b's

• Checking if a string has balanced parentheses

• Checking if a string ends with '101'