Skip to main content
edited tags
Link
D.W.
  • 165.6k
  • 21
  • 230
  • 490
Source Link

Give a class of languages which is closed under intersection and union, but not under complement

I am pondering this question, it is posed early on in a course on Formal languages and Automata, but before much progress has been made on closure of Regular and Context Free languages under operations. It has been proven in lecture that Regular, Context Free, and context sensitive languages are closed under intersection, and that Context Free and Context Sensitive languages are closer under concatenation.

We have not yet done anything about intersection, (closed under intersection would imply closed under complement by De Morgan's I think, or closed under union but not intersection would imply not closed under complement). I think the answer is probably Context Free, but I cannot find a way to show this - we have not done the Context Free pumping lemma yet so there is no real way (that I know of) for me to do a counter-example and show that the intersection of two particular CF languages is not CF

Thanks for any answers