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

View Answer

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}

View Answer

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

View Answer

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.

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

View Answer

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

View Answer

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}

View Answer

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

View Answer

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

View Answer

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

View Answer

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.

**Sanfoundry Global Education & Learning Series – Automata Theory.**

To practice all areas of Automata Theory, __here is complete set of 1000+ Multiple Choice Questions and Answers__.