Deterministic Finite Automata (DFA) MCQ

By: Prof. Dr. Fazal Rehman Shamil | Last updated: September 23, 2024

Which of the following statements is true for a DFA?

A) It has multiple start states.
B) It has multiple accept states.
C) It can have epsilon transitions.
D) It has a unique next state for each input symbol.
Answer: D

A DFA is called deterministic because:

A) It has a fixed number of states.
B) It can deterministically decide whether to accept or reject a string.
C) It does not accept epsilon transitions.
D) It has multiple transitions for a single input symbol.
Answer: B

Which of the following is not a part of the 5-tuple representation of a DFA?

A) A finite set of states.
B) A finite set of input symbols.
C) A finite set of output symbols.
D) A transition function.
Answer: C

In a DFA, the transition function:

A) Maps a state and an input symbol to multiple states.
B) Maps a state and an input symbol to a single state.
C) Maps a state and an input symbol to an output symbol.
D) Maps a state and an output symbol to an input symbol.
Answer: B

The language accepted by a DFA is:

A) Context-free.
B) Context-sensitive.
C) Regular.
D) Recursively enumerable.
Answer: C

Which of the following is true about the states of a DFA?

A) Every state must be an accept state.
B) Every state must be a start state.
C) There can be exactly one start state.
D) There can be multiple start states.
Answer: C

In a DFA, what happens if there is no valid transition for a given input symbol from a particular state?

A) The DFA moves to a random state.
B) The DFA halts and rejects the input.
C) The DFA accepts the input.
D) The DFA returns to the start state.
Answer: B

Which of the following is not true for a DFA?

A) It can recognize regular languages.
B) It can have epsilon transitions.
C) It has a single start state.
D) It has a set of final states.
Answer: B

A DFA can be used to determine if a string:

A) Is in a context-free language.
B) Is in a regular language.
C) Is in a context-sensitive language.
D) Is in a recursively enumerable language.
Answer: B

Which of the following operations can be performed on regular languages recognized by DFAs?

A) Union
B) Intersection
C) Complement
D) All of the above
Answer: D

The set of all strings over the alphabet {0, 1} that contain an even number of 1s can be recognized by:

A) A DFA
B) A PDA
C) A Turing machine
D) None of the above
Answer: A

The DFA for the language {w | w contains at least one ‘a’} over the alphabet {a, b} will have:

A) 2 states
B) 3 states
C) 1 state
D) 4 states
Answer: A

For a DFA, which of the following statements is false?

A) It has a finite number of states.
B) It can be represented using a transition table.
C) It can accept all types of languages.
D) It has a unique transition for each symbol from a state.
Answer: C

The complement of a language recognized by a DFA can be obtained by:

A) Reversing the transitions
B) Making the start state an accept state
C) Swapping the accept and non-accept states
D) Removing the start state
Answer: C

Which of the following is necessary for a language to be recognized by a DFA?

A) The language must be infinite.
B) The language must be context-free.
C) The language must be regular.
D) The language must be context-sensitive.
Answer: C

Which one of the following cannot be recognized by any DFA?

A) Strings with an even number of 0s
B) Palindromes
C) Strings containing ‘101’ as a substring
D) Strings ending with ‘0’
Answer: B

A DFA can be minimized by:

A) Combining equivalent states
B) Adding more states
C) Adding more transitions
D) Removing all final states
Answer: A

In a minimized DFA, each state represents:

A) A single string
B) A set of strings
C) A single input symbol
D) An epsilon transition
Answer: B

The product of two DFAs recognizing languages L1 and L2 will recognize:

A) L1 ∪ L2
B) L1 ∩ L2
C) L1 – L2
D) L1 concatenated with L2
Answer: B

A DFA can be converted to:

A) A PDA
B) An NFA
C) A Turing machine
D) None of the above
Answer: B

Which of the following is true about the start state of a DFA?

A) It can be any state.
B) It is the state from which the machine starts processing the input.
C) It is always an accept state.
D) It must have at least one incoming transition.
Answer: B

A language L is recognized by a DFA if and only if:

A) L is context-free.
B) L is context-sensitive.
C) L is regular.
D) L is recursively enumerable.
Answer: C

The transition function of a DFA takes as input:

A) A state and an input symbol
B) A state and an output symbol
C) Two states
D) Two input symbols
Answer: A

Which of the following statements is false for a DFA?

A) A DFA has a finite number of states.
B) A DFA can have more than one accept state.
C) A DFA can have more than one start state.
D) A DFA has a unique transition for each input symbol from a given state.
Answer: C

The pumping lemma for regular languages can be used to:

A) Prove that a language is regular
B) Prove that a language is not regular
C) Prove that a language is context-free
D) Prove that a language is context-sensitive
Answer: B

The DFA for recognizing the language {w | w ends with ’01’} over the alphabet {0, 1} requires at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C

A DFA and an NFA are equivalent in the sense that:

A) Both recognize the same set of languages.
B) Both have the same number of states.
C) Both can have epsilon transitions.
D) Both require the same amount of memory.
Answer: A

A DFA for the language {w | w has an even number of 0s and an odd number of 1s} will have at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C

Which of the following is true about the final states of a DFA?

A) There must be exactly one final state.
B) There must be at least one final state.
C) There can be zero or more final states.
D) There can be exactly two final states.
Answer: C

A DFA for the language {w | w contains at most two ‘1’s} over the alphabet {0, 1} requires at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C

The language {w | w contains the substring ’00’} over the alphabet {0, 1} can be recognized by a DFA with at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B

For a DFA, if there are ‘n’ states and ‘m’ input symbols, the maximum number of transitions is:

A) n
B) m
C) n*m
D) n+m
Answer: C

A DFA is minimized when:

A) All states are reachable.
B) All transitions are utilized.
C) It has the minimum number of states possible.
D) It has no epsilon transitions.
Answer: C

Which of the following operations can convert an NFA to a DFA?

A) Subset construction
B) State elimination
C) Transition addition
D) Epsilon removal
Answer: A

*The language recognized by the DFA given by the regular expression (0|1)01 is:

A) All strings containing ’01’
B) All strings ending with ’01’
C) All strings starting with ’01’
D) All strings with at least one ’01’
Answer: B

In a DFA, if a state has multiple outgoing transitions for the same input symbol, it is:

A) Invalid
B) Valid
C) Called a nondeterministic state
D) Called a conflicting state
Answer: A

A DFA recognizing the language {w | w does not contain ’00’} over the alphabet {0, 1} will have at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B

Which of the following is not true about DFAs and NFAs?

A) Every DFA is also an NFA.
B) Every NFA can be converted to an equivalent DFA.
C) DFAs and NFAs recognize the same class of languages.
D) DFAs can have epsilon transitions.
Answer: D

A DFA for the language {w | w contains an odd number of ‘1’s} over the alphabet {0, 1} will have:

A) 1 state
B) 2 states
C) 3 states
D) 4 states
Answer: B

Which of the following is true about a DFA’s transition function?

A) It maps a state to a set of states.
B) It maps a state to an input symbol.
C) It maps a state and an input symbol to a state.
D) It maps an input symbol to a state.
Answer: C

A DFA for the language {w | w starts with ‘0’ and ends with ‘1’} over the alphabet {0, 1} requires at least:

A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C

 

Related Posts: