in Theory of Computation edited by
5,855 views
17 votes
17 votes

Context-free languages are closed under:

  1. Union, intersection

  2. Union, Kleene closure

  3. Intersection, complement

  4. Complement, Kleene closure

in Theory of Computation edited by
by
2261 2454 2576
5.9k views

Subscribe to GO Classes for GATE CSE 2022

3 Answers

18 votes
18 votes
 
Best answer

Context free languages are not closed under intersection and complement. Correct option is (B) Union and Kleene closure.

edited by
by
49 96 161

5 Comments

The link doesn't say anything about kleen star.
0
0
Arjun sir, please tell is it the case that DCFL* is CSL always?
0
0
No. Consider $L_1 = \{a^nb^n\}  \cup \{ca^nb^{2n}\}$. Let $L = \{c\} \cup L_1$. L is DCFL. But L* is CFL
1
1
This came in TIFR
0
0
1 vote
1 vote

The context-free languages are closed under union, concatenation and Kleene closure.

so option B

by
5 11
1 vote
1 vote
CFLs are not closed under intersection, complement and set difference. Hence, the correct option is (B).
by
2

2 Comments

ankit, is DCFL* is CSL?
0
0
edited by
DCFL are not closed under Kleene closure, which means it may or may not be DCFL. So, we can't really comment about whether it would bs CSL or not. Hence, not a CSL. Please correct me if I'm wrong.
1
1
Answer:

Related questions