Automata Theory online test on “Closure Properties under Boolean Operations”.
1. If L1, L2 are regular and op(L1, L2) is also regular, then L1 and L2 are said to be ____________ under an operation op.
a) open
b) closed
c) decidable
d) none of the mentioned
Answer: b
Clarification: If two regular languages are closed under an operation op, then the resultant of the languages over an operation op will also be regular.
2. Suppose a regular language L is closed under the operation halving, then the result would be:
a) 1/4 L will be regular
b) 1/2 L will be regular
c) 1/8 L will be regular
d) Al of the mentioned
Answer: d
Clarification: At first stage 1/2 L will be regular and subsequently, all the options will be regular.
3. If L1′ and L2′ are regular languages, then L1.L2 will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Answer: a
Clarification: Regular language is closed under complement operation. Thus, if L1′ and L2′ are regular so are L1 and L2. And if L1 and L2 are regular so is L1.L2.
4. If L1 and L2′ are regular languages, L1 ∩ (L2′ U L1′)’ will be
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Answer: a
Clarification: If L1 is regular, so is L1′ and if L1′ and L2′ are regular so is L1′ U L2′. Further, regular languages are also closed under intersection operation.
5. If A and B are regular languages, !(A’ U B’) is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Answer: a
Clarification: If A and B are regular languages, then A Ç B is a regular language and A ∩ B is equivalent to !(A’ U B’).
6. Which among the following are the boolean operations that under which regular languages are closed?
a) Union
b) Intersection
c) Complement
d) All of the mentioned
Answer: d
Clarification: Regular languages are closed under the following operations:
a) Regular expression operations
b) Boolean operations
c) Homomorphism
d) Inverse Homomorphism
7. Suppose a language L1 has 2 states and L2 has 2 states. After using the cross product construction method, we have a machine M that accepts L1 ∩ L2. The total number of states in M:
a) 6
b) 4
c) 2
d) 8
Answer: 4
Clarification: M is defined as: (Q, S, d, q0, F)
where Q=Q1*Q2 and F=F1*F2
8. If L is a regular language, then (L’)’ U L will be :
a) L
b) L’
c) f
d) none of the mentioned
Answer: a
Clarification: (L’)’ is equivalent to L and L U L is subsequently equivalent to L.
9. If L is a regular language, then (((L’)r)’)* is:
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Answer: a
Clarification: If L is regular so is its complement, if L’ is regular so is its reverse, if (L’)r is regular so is its Kleene.
10. Which among the following is the closure property of a regular language?
a) Emptiness
b) Universality
c) Membership
d) None of the mentioned
Answer: d
Clarification: All the following mentioned are decidability properties of a regular language. The closure properties of a regular language include union, concatenation, intersection, Kleene, complement , reverse and many more operations.