# Automata Theory Questions and Answers – DFA Processing Strings

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses 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

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}

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) {}

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 first and the second state.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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
c) 22
d) 27

6. For the DFA given below compute the following:
Union of all possible combinations at state 7,8 and 9. a) {aba, ac, cc, ca, cb, bc, bab, ca}
b) {bab, bc, ac, aba, ca, aac, ccb}
c) {cc, ca, cb, aba, bab, ac}
d) {aba, ac, cc, ca, cb, bc, bab, caa}

Explanation: The string a state receives is the combination of all input alphabets which lie across the path covered.

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

Explanation: DFA can be made for infinite language with an infinite length. Thus, dependency over length is unfruitful.

8. Given:
L= {xϵ∑= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No

Explanation: 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.

9. δ(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

Explanation: 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. 