Automata Theory Quiz
Test your knowledge of automata theory concepts and applications.
Full Name
*
First Name
Last Name
Email Address
*
example@example.com
Which of the following is a property of deterministic finite automata (DFA)?
*
Each state has exactly one transition for each symbol in the alphabet.
A state may have multiple transitions for the same symbol.
There can be epsilon (ε) transitions.
The automaton can have infinitely many states.
Which of the following languages is NOT regular?
*
The set of all strings over {a, b} with an even number of a's.
The set of all palindromes over {a, b}.
The set of all strings over {a, b} that do not contain substring 'ab'.
The set of all strings over {a, b} where every b is immediately followed by an a.
Select all machines that can recognize context-free languages.
*
Pushdown Automaton (PDA)
Deterministic Finite Automaton (DFA)
Turing Machine
Linear Bounded Automaton
Other
Match the automaton to the language class it recognizes.
*
Rows
Regular Languages
Context-Free Languages
Context-Sensitive Languages
Recursively Enumerable Languages
Deterministic Finite Automaton (DFA)
1
2
3
4
Pushdown Automaton (PDA)
5
6
7
8
Linear Bounded Automaton (LBA)
9
10
11
12
Turing Machine
13
14
15
16
Which of the following statements about nondeterministic finite automata (NFA) is TRUE?
*
Every NFA can be converted to an equivalent DFA.
NFAs cannot accept regular languages.
NFAs are more powerful than DFAs.
NFAs must have exactly one initial state.
Give a regular expression that generates all strings over {0,1} containing at least one '1'.
*
A Turing machine halts on every input. What class of languages does it recognize?
*
Recursive Languages
Context-Free Languages
Regular Languages
Recursively Enumerable Languages
Which statements are TRUE about regular languages? (Select all that apply)
*
They are closed under union.
They are closed under intersection.
They are closed under complement.
They are closed under reversal.
Other
Short Answer: Briefly explain the difference between a DFA and an NFA.
*
True or False: Every context-free language can be recognized by a deterministic pushdown automaton (DPDA).
*
True
False
Submit Quiz
Should be Empty: