1. 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
Explanation: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).
2. Which of the following x is accepted by the given DFA (x is a binary string ∑= {0,1})?
a) divisible by 3
b) divisible by 2
c) divisible by 2 and 3
d) divisible by 3 and 2
Explanation: The given DFA accepts all the binary strings such that they are divisible by 3 and 2.Thus, it can be said that it also accepts all the strings which is divisible by 6.
3. 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
Explanation:
4. 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
Explanation: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.
5. 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
Explanation: 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.
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
Explanation: 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. There are ________ tuples in finite state machine.
a) 4
b) 5
c) 6
d) unlimited
Explanation: States, input symbols, initial state, accepting state and transition function.
8. Transition function maps.
a) Σ * Q -> Σ
b) Q * Q -> Σ
c) Σ * Σ -> Q
d) Q * Σ -> Q
Explanation: Inputs are state and input string output is states.
9. Number of states require to accept string ends with 10.
a) 3
b) 2
c) 1
d) can’t be represented.
Explanation: This is minimal finite automata.
10. Extended transition function is .
a) Q * Σ* -> Q
b) Q * Σ -> Q
c) Q* * Σ* -> Σ
d) Q * Σ -> Σ
Explanation: This takes single state and string of input to produce a state.