# 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

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

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

Explanation: Regular sets are closed under complement operation.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

Explanation: Regular is closed under difference.

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

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)

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.

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

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

Explanation: Regular set are closed under homomorphism.

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

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

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

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

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

Explanation: It is a regular expression.

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

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. 