Closure-Property
Question 1 |
The set of all recursively enumerable languages is
closed under complementation.
| |
closed under intersection.
| |
a subset of the set of all recursive languages.
| |
an uncountable set.
|
Question 1 Explanation:
Recursive enumerable languages are closed under intersection.
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
Recursive enumerable languages are not closed under Complementation.
Recursive enumerable languages are a countable set, as every recursive enumerable language has a corresponding Turing Machine and set of all Turing Machine is countable.
Recursive languages are subset of recursive enumerable languages.
Question 2 |
Consider the following types of languages: L1: Regular, L2: Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?
I only | |
I and III only | |
I and IV only | |
I, II and III only |
Question 2 Explanation:
I. 
L3 is recursive, so
is also recursive (because recursive language closed under complementation), so is recursive enumerable.
L4 is recursive enumerable.
So is also recursive enumerable (closed under union).
II.
L2 is context free, so L2 is recursive.
Since L2 is recursive. So
is recursive.
L3 is recursive.
So is also recursive (closed under union)
III.
L1 is regular, so L1* is also regular.
L2 is context free.
So, L1*∩L2 is also context free (closed under regular intersection).
IV.
L1 is regular.
L2 is context free, so
may or may not be context free (not closed under complement).
So, may or may not be context free.
Hence, answer is (D).
L3 is recursive, so
is also recursive (because recursive language closed under complementation), so is recursive enumerable. L4 is recursive enumerable.
So
is also recursive enumerable (closed under union). II.
L2 is context free, so L2 is recursive.
Since L2 is recursive. So
is recursive. L3 is recursive.
So
is also recursive (closed under union) III.
L1 is regular, so L1* is also regular.
L2 is context free.
So, L1*∩L2 is also context free (closed under regular intersection).
IV.
L1 is regular.
L2 is context free, so
may or may not be context free (not closed under complement). So,
may or may not be context free. Hence, answer is (D).
There are 2 questions to complete.