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

computer science gate 2023 recursive enumerable languages recursive languages context free languages regular languages language intersection GATE computer sciences 2023 logical gates questions

Unique Visitor Count

Total Unique Visitors

Loading......