WorksheetsTAFL Unit 1 Quiz: Finite Automata
Total questions: 20
Worksheet time: 10mins
What is the output of a finite automaton?
Grammar
Automaton
Language
Transition
Which of the following is not a part of a DFA?
Finite set of states
Alphabet
Stack
Transition function
A DFA can have...
Multiple initial states
Multiple accepting states
Infinite states
ε-transitions
In a DFA, from every state, for every input symbol, there is...
No transition
At most one transition
At least one transition
Exactly one transition
Which one is more powerful?
DFA
NFA
Both are equally powerful
PDA
What does an NFA use that a DFA does not?
Stack
Multiple transitions for same input
Tape
None of these
The transition function of a DFA is:
δ: Q × Σ → Q
δ: Q × Σ → P(Q)
δ: Q × Σ → Q × Σ
δ: Q × Σ → Q × Γ × {L, R}
The extended transition function is used for:
States only
Single symbol input
Input strings
Final state only
A dead state in a DFA is one from which:
No transition is possible
No accepting state is reachable
Loop is not allowed
Input is invalid
What is ε-closure of a state in an NFA?
Set of all states reachable from it using 1 input
Set of accepting states
Set of states reachable using ε-transitions
Final state set
The minimal number of states in a DFA accepting only the empty string is:
0
1
2
Depends on the string
DFA is used to recognize:
Context-Free Languages
Regular Languages
Non-Regular Languages
Type-1 Languages
In which automaton do we not allow ε-transitions?
ε-NFA
NFA
DFA
PDA
Which component is not part of a finite automaton?
States
Stack
Transition function
Alphabet
Which of the following can be converted into a DFA?
Regular Expression
Context-Free Grammar
Turing Machine
Stack Automata
In DFA minimization, which states are removed?
Final states
Dead states
Unreachable states
Initial state
Which automaton uses a finite memory?
DFA
PDA
Turing Machine
LBA
A DFA accepts an infinite language if:
It has a dead state
It has more than one final state
It contains a cycle
It is non-deterministic
Which state is always present in a DFA?
Final state
Start state
Trap state
Intermediate state
The language {w | w has an even number of 0s} is:
Not regular
Regular
Context-Free
Recursive
