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
View Answer

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?
The corresponding Language ends in 1 & does not contain substring 00 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

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

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

4. Let the given DFA consist of x states. Find x-y such that y is the number of states on minimization of DFA?
Find x-y such that y is number of states on minimization of DFA for given DFA of x states
a) 3
b) 2
c) 1
d) 4
View Answer

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

Answer: a
Explanation:
Find number of states in DFA to surpass all letters of alphabet excluding vowels

6. For the DFA given below compute the following:
Union of all possible combinations at state 7,8 and 9.
Find the union of all possible combinations at state 7, 8 & 9 for the DFA
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

Answer: d
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

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

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

Answer: b
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

Answer: a
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.
advertisement

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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.