Theory of Computation

“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

Explanation: For a string of n characters with no repetitive substrings, the number of
states required to pass the string is n+1.


2. Which of the following is the corresponding Language to the given DFA?




a) L = {x ϵ {0, 1} * | x ends in 1 and does not contain substring 01}
b) L = {x ϵ {0,1} * |x ends in 1 and does not contain substring 00}
c) L = {x ϵ {0,1} |x ends in 1 and does not contain substring 00}
d) L = {x ϵ {0,1} * |x ends in 1 and does not contain substring 11}
Answer: b

Explanation: The Language can be anonymously checked and thus the answer can be
predicted. The language needs to be accepted by the automata (acceptance state) in
order to prove its regularity.

, 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

Explanation: 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
4. Let the given DFA consist of x states. Find x-y such that y is the number of states on
minimization of DFA?




a) 3
b) 2
c) 1
d) 4
Answer: b


Explanation: Use the equivalence theorem or Myphill Nerode theorem to minimize the
DFA.


5. 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