Q.1 Which of the following is true about a deterministic finite automaton (DFA)?
It can have multiple transitions for the same symbol from a state
It can have ε-transitions
It has exactly one transition for each symbol in the alphabet from each state
It cannot have a start state
Explanation - In a DFA, for every state and input symbol, there is exactly one defined transition.
Correct answer is: It has exactly one transition for each symbol in the alphabet from each state
Q.2 Which type of automaton uses ε (epsilon) transitions?
DFA
NFA
Turing Machine
Pushdown Automaton
Explanation - Nondeterministic Finite Automata (NFA) can have ε-transitions, allowing moves without consuming input symbols.
Correct answer is: NFA
Q.3 Which of the following languages can be recognized by a finite automaton?
Regular languages
Context-free languages
Context-sensitive languages
Recursively enumerable languages
Explanation - Finite automata recognize exactly the set of regular languages.
Correct answer is: Regular languages
Q.4 What is the minimum number of states required in a DFA to accept the language of all strings over {0,1} ending with '01'?
2
3
4
5
Explanation - A DFA needs 3 states to track the sequence of last two symbols to recognize strings ending in '01'.
Correct answer is: 3
Q.5 Which statement is true for an NFA?
An NFA always has more states than its equivalent DFA
An NFA may have multiple transitions for the same input from a state
An NFA cannot accept regular languages
An NFA does not have accepting states
Explanation - NFA allows multiple possible transitions for the same input from a state, unlike DFA.
Correct answer is: An NFA may have multiple transitions for the same input from a state
Q.6 What does the transition function δ in a DFA do?
It maps a state to a set of accepting states
It maps a pair of state and input symbol to a next state
It defines the start state
It defines the alphabet
Explanation - The DFA transition function δ: Q × Σ → Q maps current state and input symbol to a unique next state.
Correct answer is: It maps a pair of state and input symbol to a next state
Q.7 Which of the following is a correct definition of a regular expression?
It generates context-free languages
It is equivalent in power to finite automata
It requires a stack to recognize languages
It can recognize recursively enumerable languages
Explanation - Regular expressions and finite automata are equivalent in terms of the class of languages they define: regular languages.
Correct answer is: It is equivalent in power to finite automata
Q.8 Which of the following is NOT a property of regular languages?
Closure under union
Closure under intersection
Closure under complementation
Closure under context-sensitive substitution
Explanation - Regular languages are not closed under context-sensitive substitution; this operation can produce non-regular languages.
Correct answer is: Closure under context-sensitive substitution
Q.9 In a DFA, if a state has no outgoing transitions for some symbol, what is implied?
The DFA is invalid
It leads to a dead state or trap state
The language is not regular
The automaton is nondeterministic
Explanation - DFA completeness requires all transitions; missing transitions are considered as going to an implicit trap state.
Correct answer is: It leads to a dead state or trap state
Q.10 Which of the following can be converted to a DFA without changing the language recognized?
NFA with ε-transitions
Context-free grammar
Turing machine
Pushdown automaton
Explanation - An NFA (even with ε-transitions) can always be converted to an equivalent DFA that recognizes the same language.
Correct answer is: NFA with ε-transitions
Q.11 Which technique is used to minimize the number of states in a DFA?
Subset construction
State equivalence partitioning
Pushdown conversion
Grammar simplification
Explanation - State minimization is performed by grouping equivalent states and merging them to reduce DFA size.
Correct answer is: State equivalence partitioning
Q.12 Which of these automata can recognize some non-regular languages?
DFA
NFA
Pushdown Automaton
Finite State Machine
Explanation - Pushdown automata, which use a stack, can recognize context-free languages, which include some non-regular languages.
Correct answer is: Pushdown Automaton
Q.13 What is the primary difference between DFA and NFA?
DFA can have ε-transitions, NFA cannot
NFA can have multiple transitions for same input, DFA cannot
DFA uses stack memory, NFA does not
NFA can recognize context-free languages
Explanation - DFA has exactly one transition per symbol from each state, whereas NFA may have multiple.
Correct answer is: NFA can have multiple transitions for same input, DFA cannot
Q.14 Which of the following is true about the equivalence of DFA and NFA?
Every DFA can be converted to an equivalent NFA
Every NFA can be converted to an equivalent DFA
Both statements are true
Neither statement is true
Explanation - DFAs and NFAs recognize the same class of regular languages; conversions between them are always possible.
Correct answer is: Both statements are true
Q.15 The language L = {0^n1^n | n ≥ 0} is:
Regular
Context-free but not regular
Context-sensitive
Recursively enumerable but not context-sensitive
Explanation - The language requires counting and cannot be recognized by a finite automaton, but is context-free.
Correct answer is: Context-free but not regular
Q.16 Which of the following operations preserves regularity?
Intersection with another regular language
Complementation
Union with another regular language
All of the above
Explanation - Regular languages are closed under union, intersection, and complementation.
Correct answer is: All of the above
Q.17 What is a trap state in a DFA?
A state with multiple outgoing transitions
A state that is both start and accepting
A non-accepting state from which no accepting state is reachable
A state with ε-transitions
Explanation - Trap states are dead-end states that cannot lead to acceptance of a string.
Correct answer is: A non-accepting state from which no accepting state is reachable
Q.18 Which of the following statements is FALSE?
Every regular language can be expressed as a DFA
Every regular language can be expressed as a regular expression
Every DFA can be converted to an equivalent NFA
Every context-free language can be expressed as a DFA
Explanation - DFAs cannot recognize all context-free languages; some require memory like a stack.
Correct answer is: Every context-free language can be expressed as a DFA
Q.19 Which of the following is used to represent transitions in an automaton?
Transition table or state diagram
Parse tree
Derivation tree
Syntax tree
Explanation - Automaton transitions are typically represented as tables or diagrams showing movement between states.
Correct answer is: Transition table or state diagram
Q.20 In an NFA, a string is accepted if:
All computation paths end in an accepting state
At least one computation path ends in an accepting state
No computation path ends in an accepting state
Only the longest path ends in an accepting state
Explanation - NFA accepts a string if any possible path leads to an accepting state.
Correct answer is: At least one computation path ends in an accepting state
Q.21 Which algorithm is commonly used to convert an NFA to a DFA?
Pumping lemma
Subset construction
Kleene’s algorithm
State elimination
Explanation - Subset construction systematically creates DFA states corresponding to sets of NFA states.
Correct answer is: Subset construction
Q.22 The language of all strings over {a,b} containing an even number of a's can be recognized by a DFA with how many states?
1
2
3
4
Explanation - Two states suffice: one for even number of a's, one for odd number of a's.
Correct answer is: 2
Q.23 Which of the following is NOT true for finite automata?
They have finite states
They can recognize infinite languages
They can use unlimited memory
They can be deterministic or nondeterministic
Explanation - Finite automata have no external memory and cannot use unlimited memory.
Correct answer is: They can use unlimited memory
Q.24 Which of the following languages can a DFA recognize?
Strings with equal number of a's and b's
Strings ending with '101'
Palindrome strings over {0,1}
The language {0^n1^n | n ≥ 0}
Explanation - DFA can recognize patterns like strings ending with a specific sequence, but not languages requiring counting or palindromes.
Correct answer is: Strings ending with '101'