Automata Theory Questions and Answers – Union, Intersection & Complement

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Union, intersection and complement of Regular Language & Expression”.

1. Regular sets are closed under union,concatenation and kleene closure.
a) True
b) False
c) Depends on regular set
d) Can’t say
View Answer

Answer:a
Explanation: Regular sets are closed under these three operation.

2. Complement of a DFA can be obtained by
a) making starting state as final state
b) no trival method
c) making final states non-final and non-final to final
d) make final as a starting state
View Answer

Answer:c
Explanation: String accepted in previous DFA will not be accepted and non accepting string will be accepted .

3. Complement of regular sets are _________
a) Regular
b) CFG
c) CSG
d) RE
View Answer

Answer:a
Explanation: Regular sets are closed under complement operation.
advertisement
advertisement

4. If L1 and L2 are regular sets then intersection of these two will be
a) Regular
b) Non Regular
c) Recursive
d) Non Recursive
View Answer

Answer:a
Explanation: Regular expression are also colsed under intersection.

5. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be
a) Empty set
b) CFG
c) Decidable
d) Regular
View Answer

Answer:d
Explanation: Regular is closed under difference.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Reverse of a DFA can be formed by
a) using PDA
b) making final state as non-final
c) making final as starting state and starting state as final state
d) None of the mentioned
View Answer

Answer:c
Explanation: By making final state as starting state string starting from end will be accepted.

7. Reverse of (0+1)* will be
a) Phi
b) Null
c) (0+1)*
d) (0+1)
View Answer

Answer:c
Explanation: There is only one state which is start and final state of DFA so interchanging starting start and final state doesn’t change DFA.
advertisement

8. A ___________ is a substitution such that h(a) contains a string for each a.
a) Closure
b) Interchange
c) Homomorphism
d) Inverse Homomorphism
View Answer

Answer:c
Explanation: This operation replace using a function .

9. Homomorphism of a regular set is _______
a) Universal set
b) Null set
c) Regular set
d) Non regular set
View Answer

Answer:c
Explanation: Regular set are closed under homomorphism.
advertisement

10. (a ^ 5b ^ 5)* is example of ________
a) Type 0 language
b) Type 1 language
c) Type 2 language
d) Type 3 language
View Answer

Answer:d
Explanation: It is a regular expression.

11. Which of the following is type 3 language ?
a) Strings of 0’s whose length is perfect square
b) Palindromes string
c) Strings of 0’s having length prime number
d) String of odd number of 0’s
View Answer

Answer:d
Explanation: Only d is regular language.

12. a ^ nb ^ n where (n+m) is even .
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer

Answer:d
Explanation: It is a regular expression.

13. Complement of a ^ nb ^ m where n >= 4 and m <= 3 is example of
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer

Answer:d
Explanation: It is a regular expression.

14. a ^ nb ^ m where n >= 1, m >= 1, nm >= 3 is example of
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer

Answer:d
Explanation: It is a regular expression.

15. Complement of (a + b)* will be
a) phi
b) null
c) a
d) b
View Answer

Answer:a
Explanation: Given expression accept all string so complement will accept nothing.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.