Automata Theory Multiple Choice Questions on “DFA Processing Strings”.
1. The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________
a) 14 states
b) 13 states
c) 12 states
d) A password pass system cannot be created using DFA
Answer: a
Clarification: For a string of n characters with no repetitive substrings, the number of states required to pass the string is n+1.
3. Let ∑= {a, b, …. z} and A = {Hello, World}, B= {Input, Output}, then (A*∩B) U (B*∩A) can be represented as:
a) {Hello, World, Input, Output, ε}
b) {Hello, World, ε}
c) {Input, Output, ε}
d) {}
Answer: d
Clarification: Union operation creates the universal set by combining all the elements of first and second set while intersection operation creates a set of common elements of the first and the second state.
4. For a machine to surpass all the letters of alphabet excluding vowels, how many number of states in DFA would be required?
a) 3
b) 2
c) 22
d) 27
Answer: a
5. Given L= {Xϵ∑*= {a, b} |x has equal number of a, s and b’s}.
Which of the following property satisfy the regularity of the given language?
a) Regularity is dependent upon the length of the string
b) Regularity is not dependent upon the length of the string
c) Can’t be said for a particular string of a language
d) It may depend on the length of the string
Answer: b
Clarification: DFA can be made for infinite language with an infinite length. Thus, dependency over length is unfruitful.
6. Given:
L= {xϵ∑= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No
Answer: b
Clarification: It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus, It is not possible to build a DFA for the given Language.
7. δ(A,1) = B, δ(A,0) =A
Δ (B, (0,1)) =C
δ(C,0) = A (Initial state =A)
String=”011001” is transit at which of the states?
a) A
b) C
c) B
d) Invalid String
Answer: a
Clarification: It is east and simple to create the table and then the corresponding transition graph in order to get the result, at which state the given string would be accepted.