Show Question
Math and science::Theory of Computation

# Context-free languages: closed operations

### Context-free language closure

If $$L$$ and $$M$$ are context-free languages, then the following are also context-free languages:

• $$L \cup M$$
• $$L \circ M$$
• $$L^{\star}$$

In other words, context-free languages are closed under union, concatenation and Kleen star.

There are important operations under which context free languages are not closed. Can you remember them?

Context-free languages are not closed under:

• intersection
• complementation
• set difference

## Context

grammar → context-free grammar → context-free language → context-free language closure → Chomsky normal form → pushdown automaton → deterministic pushdown automaton