1
$\begingroup$

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

Improve this question
$\endgroup$
2

1 Answer 1

Reset to default
5
$\begingroup$

An example of a class of languages which is closed under union and intersection, but not under complement is the class of finite languages.

Context-free languages are closed under union, but not under intersection or complement. The same holds for linear languages.

Deterministic context-free languages are closed under complement, not under union or intersection.

As you know the regular languages are closed under the three Boolean operations.

This is also true for the context-sensitive languages. The closure of that class under complement has long been an open problem. The context-sensitive languages form a basic class in the Chomsky hierarchy (mainly based on grammar and automata models). But alternatively they also are a basic complexity class: nondeterministic linear space. More general, if the space is at least logarithmic, the nondeterministic space classes are closed under the Boolean operations.

Of course closure under complement is still an open question for time complexity: P=NP (?).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! This makes sense, I got bogged down in trying to make one of the given classes work :) $\endgroup$
    – I have Your Clock
    Commented Aug 16 at 0:27
  • $\begingroup$ @IhaveYourClock I have added some remarks on closure properties for languages classes defined by complexity. $\endgroup$
    – Hendrik Jan
    Commented Aug 16 at 13:19
  • $\begingroup$ @HendrickJan Thank you! This was really interesting $\endgroup$
    – I have Your Clock
    Commented Aug 17 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.