Automata Theory Multiple Choice Questions on “The Language of DFA”
1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite
Answer: d
Clarification: A language over an alphabet R is a set of strings over A which is uncountable and infinite.
2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false
Answer: b
Clarification: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.
3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set
Answer: a
Clarification: δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.
4. Which of the following option is correct?
A= {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A
Answer: b
Clarification: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.
5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3
Answer: d
Clarification: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).
6. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2
Answer: a
Clarification: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.
7. Given:
L1= {xϵ ∑*|x contains even no’s of 0’s}
L2= {xϵ ∑*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
Answer: c
8. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a) 1
b) 2
c) 3
d) 4
Answer: c
Clarification: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.
9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language
Answer: d
Clarification: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.