Automata Theory Questions and Answers – The Language of DFA

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Language of DFA”

1. How many languages are over the alphabet R?
a) countably infinite
b) countably finite
c) uncountable finite
d) uncountable infinite
View Answer

Answer: d
Explanation: A language over an alphabet R is a set of strings over A which is uncountable and infinite.
advertisement

2. According to the 5-tuple representation i.e. FA= {Q, ∑, δ, q, F}
Statement 1: q ϵ Q’; Statement 2: FϵQ
a) Statement 1 is true, Statement 2 is false
b) Statement 1 is false, Statement 2 is true
c) Statement 1 is false, Statement 2 may be true
d) Statement 1 may be true, Statement 2 is false
View Answer

Answer: b
Explanation: Q is the Finite set of states, whose elements i.e. the states constitute the finite automata.

3. δˆ tells us the best:
a) how the DFA S behaves on a word u
b) the state is the dumping state
c) the final state has been reached
d) Kleene operation is performed on the set
View Answer

Answer: a
Explanation: δ or the Transition function describes the best, how a DFA behaves on a string where to transit next, which direction to take.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. Which of the following option is correct?
A = {{abc, aaba}. {ε, a, bb}}
a) abcbb ₵ A
b) ε₵A
c) ε may not belong to A
d) abca ₵ A
View Answer

Answer: b
Explanation: As the question has dot operation, ε will not be a part of the concatenated set. Had it been a union operation, ε would be a part of the operated set.

5. For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?
a) 0
b) 0,2
c) 0,2,4
d) 0,1,2,3
View Answer

Answer: d
Explanation: All the decimal numbers on division would lead to only 4 remainders i.e. 0,1,2,3 (Property of Decimal division).
advertisement

6. Which of the following x is accepted by the given DFA (x is a binary string ∑= {0,1})?
The given DFA accepts all binary strings that they are divisible by 3 & 2
a) divisible by 3
b) divisible by 2
c) divisible by 2 and 3
d) divisible by 3 and 2
View Answer

Answer: d
Explanation: The given DFA accepts all the binary strings such that they are divisible by 3 and 2.Thus, it can be said that it also accepts all the strings which is divisible by 6.

7. Given:
L1= {xϵ ∑*|x contains even no’s of 0’s}
L2= {xϵ ∑*|x contains odd no’s of 1’s}
No of final states in Language L1 U L2?
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation:
The number of final states in Language L1 U L2 is 3
advertisement

8. The maximum number of transition which can be performed over a state in a DFA?
∑= {a, b, c}
a) 1
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.

9. The maximum sum of in degree and out degree over a state in a DFA can be determined as:
∑= {a, b, c, d}
a) 4+4
b) 4+16
c) 4+0
d) depends on the Language
View Answer

Answer: d
Explanation: The out degree for a DFA I fixed while the in degree depends on the number of states in the DFA and that cannot be determined without the dependence over the Language.
advertisement

10. The sum of minimum and maximum number of final states for a DFA n states is equal to:
a) n+1
b) n
c) n-1
d) n+2
View Answer

Answer: a
Explanation: The maximum number of final states for a DFA can be total number of states itself and minimum would always be 1, as no DFA exits without a final state. Therefore, the solution is n+1.

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.