Consider Context-Free Languages (CFLs) and , and assume that for some Context-Free Grammar (CFG) and for some CFG . Note that both the CFGs share the same alphabet .

Context-Free Languages are closed under the following operations

## Union

Consider the following grammar

Then , and therefore CFLs are closed under union. In essence, we are adding a new start variable and the new start variable can go to either of or .

## Concatenation

Consider the following grammar

Then , and therefore CFLs are closed under concatenation. In essence, we are adding a new start variable and the new start variable goes to .

## Kleene Star

Consider the following grammar

Then , and therefore CFLs are closed under star. In essence, we are adding a new start variable and the new start variable goes to .

For the following operations, consider a CFL , and assume that for some CFG in *Chomsky Normal Form*.

## Reversal

When , ; and .

For example, let . Then .

A derivation of a string in this grammar can be visualized as a binary parse tree, with the left-right traversal of leaves of the tree generating the string that is derived. A right-left traversal of the leaves of the same tree will generate . Thus a *mirror image* of the parse tree will generate the reverse of a string. So the following grammar will generate all strings in .

Form a CFG where is determined as follows

- is in if and only if it is in .
- For and , is in if and only if it is in .
- For , is in if and only if is in .

Then , so is context-free.

## Prefix

When , ; and .

For example, let . Then .

Suppose that has no useless variables, and form a CFG where and is determined as follows

- is in .
- For and , is in if and only if is in .
- For , is in if and only if it in .

Then , so is context-free.

To explain this, the original variables generate what they did before. The primed variables generate prefixes of what the original variables generated. We need to keep both because if we had , derives , and derives so that derives , there may be strings in that are not in . In fact .

## Subsequence

When , and ; and .

For example, let . Then .

A derivation using this CNF can be visualized as a binary parse tree, with the left-right traversal of leaves of the tree generating the string that is derived. In constructing a subsequence, each may be present or absent. Thus, any number of the terminals in this string can be replaced by to get a subsequence (when the leaves of the parse-tree are traversed left-right) of . In fact, all possible combinations of doing this will be . So the following grammar will generate all strings in .

Form a CFG where is determined as follows

- For , is in if and only is in for some .

Then , so is context-free.