Computer Sciences > Gate 2023 > Regular Language
Which of the following statements is/are CORRECT?
A
The intersection of two recursively enumerable languages is recursively enumerable.
B
The intersection of two recursive languages is recursive.
C
The intersection of two context free languages is context free.
D
The intersection of two regular languages is regular.

Correct : a,c,d

a) is correct

The class of recursively enumerable (RE) languages is closed under intersection.
If L1 and L2 are RE languages, then L1 ∩ L2 is also RE.
This can be done by constructing a Turing machine that runs the machines for both L1 and L2 in parallel and accepts if both accept.
For example:
Let L1 = { w | w contains at least one 'a' } and L2 = { w | w contains at least one 'b' }.
Their intersection is L1 ∩ L2 = { w | w contains both 'a' and 'b' }, which is RE.

b) is incorrect

The class of recursive languages is not always closed under intersection.
If L1 and L2 are recursive, their intersection L1 ∩ L2 might not necessarily be recursive because deciding membership in L1 ∩ L2 could require undecidable steps.
For example:
Let L1 = { w | w halts on input 0 } and L2 = { w | w halts on input 1 }.
Their intersection is L1 ∩ L2 = { w | w halts on both input 0 and input 1 }, which is not recursive because the halting problem is undecidable.

c) is incorrect

The class of context-free languages (CFLs) is not closed under intersection.
There exist CFLs L1 and L2 such that their intersection L1 ∩ L2 is not a CFL.
For example:
Let L1 = { an bn cm | n, m ≥ 0 } and L2 = { am bn cn | n, m ≥ 0 }.
Their intersection is L1 ∩ L2 = { an bn cn | n ≥ 0 }, which is not a CFL.

d) is correct

The class of regular languages is closed under intersection.
If L1 and L2 are regular, then L1 ∩ L2 is also regular.
This can be achieved using the product construction of finite automata.
For example:
Let L1 = { w | w starts with 'a' } and L2 = { w | w ends with 'b' }.
Their intersection is L1 ∩ L2 = { w | w starts with 'a' and ends with 'b' }, which is regular.

So, a, c, d is correct option

Similar Questions

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
#132 MCQ
Let L1 and L2 be any context-free language and R be any regular language. Then, which of the following is correct ? I. L1 ∪ L2 is context-free. II. L1' is cont...
#166 MCQ
For Σ = {a, b}, let us consider the regular language L = {x ∣ x = a2+ 3k or x = b10 + 12k, k ≥ 0} Which one of the following can be a pumping length (the co...
#252 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......