Closure properties of CFLs

Why it exists

Closure properties are the quickest way to answer "is this language context-free?" for combined languages, and they are a favourite GATE topic because the answers differ from the regular case: context-free languages are not closed under intersection or complement. The answer table must be known by heart, and so must the counterexamples.

Prerequisites

You need the grammar and PDA descriptions of context-free languages and their equivalence (PDA and CFG).

Precise definitions

A class of languages is closed under an operation if applying the operation to members always gives a member. For the class of context-free languages (CFLs):

Also closed (quoted): substitution of context-free languages for the symbols, quotient by a regular language, prefix closure. Not closed: infinite unions and arbitrary subsets (as for regular languages).

How it works

The grammar constructions

For $G_1$: $S \to aSb \mid \varepsilon$ (the language $a^n b^n$) and $G_2$: $S \to cS \mid c$ (the language $c^+$) the constructions give (renaming the variables to $S_1, S_2$ and adding a new start symbol $S$):

Each result was checked against the set definition of the operation on all strings up to length $8$ (and on $150$ random pairs of grammars).

Why the constructions work. Union: any derivation starts with $S \to S_1$ or $S \to S_2$ and then continues inside one grammar; concatenation: a string of $L_1 L_2$ is a string of $L_1$ followed by one of $L_2$; star: $S \Rightarrow S_1 S \Rightarrow S_1 S_1 S \Rightarrow \cdots \Rightarrow S_1 \cdots S_1$; reversal: a parse tree turned over is a parse tree of the reversed grammar; homomorphism: replacing a leaf $a$ by the string $h(a)$.

Intersection with a regular language

Run a PDA $P$ for $L$ and a DFA $D$ for $R$ side by side: the states are pairs, the stack is $P$'s stack, the DFA component changes only when an input symbol is read, and the pair accepts when both components accept. The row at the end of the table above: a PDA for $a^n b^n$ (4 states) and a DFA for "length divisible by $4$" (4 states) give a product with $16$ states (13 reachable) that accepts $a^{2k} b^{2k}$. This is the only kind of intersection that is safe: with a second context-free language there are two stacks.

Intersection and complement fail

$L_1 = \{a^i b^i c^k : i, k \ge 0\}$ is context-free (grammar $S \to XC$, $X \to aXb \mid \varepsilon$, $C \to cC \mid \varepsilon$), and so is $L_2 = \{a^i b^j c^j\}$ (grammar $S \to AY$, $A \to aA \mid \varepsilon$, $Y \to bYc \mid \varepsilon$). Their intersection is

$L_1 \cap L_2 = \{a^n b^n c^n : n \ge 0\},$

which is not context-free (pumping lemma on the next page). Hence CFLs are not closed under intersection (checked: both languages equal their grammars on all strings up to length $12$ and the intersection is $a^n b^n c^n$). If CFLs were closed under complement, then $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$ would be context-free (closed under union): a contradiction. So they are not closed under complement either, and not under difference (take $\Sigma^* \setminus L$).

The complement of a non-CFL can be a CFL

The language $\{a^n b^n c^n\}$ is not context-free but its complement is. A string is outside the language if (1) it is not of the form $a^* b^* c^*$ (it contains $ba$, $ca$ or $cb$): a regular condition; or (2) it is $a^i b^j c^k$ with $i \ne j$; or (3) with $j \ne k$. Each of the three is context-free:

$S \to R \mid P \mid Q, \quad R \to X\,ba\,X \mid X\,ca\,X \mid X\,cb\,X, \quad X \to aX \mid bX \mid cX \mid \varepsilon,$ $P \to T\,C, \quad T \to aTb \mid A \mid B, \quad A \to aA \mid a, \quad B \to bB \mid b, \quad C \to cC \mid \varepsilon,$ $Q \to D\,U, \quad D \to aD \mid \varepsilon, \quad U \to bUc \mid E \mid F, \quad E \to bE \mid b, \quad F \to cF \mid c.$

The union is the complement of $\{a^n b^n c^n\}$ (compared with the definition on all strings up to length $9$). So "the complement of a CFL need not be a CFL" and "the complement of a non-CFL may be a CFL" are both true statements.

Using closure to show a language is not context-free

If $L$ is context-free then so is $L \cap R$ for every regular $R$. To show that $L$ is not context-free find a regular $R$ so that $L \cap R$ is known not to be.

• $L = \{w \in \{a, b, c\}^* : \#a = \#b = \#c\}$. Then $L \cap a^* b^* c^* = \{a^n b^n c^n\}$ is not context-free, so $L$ is not.
• $L = \{ww : w \in \{a, b\}^*\}$: intersect with $a^* b^* a^* b^*$; the result is $\{a^i b^j a^i b^j\}$, which the pumping lemma excludes.
• Use a homomorphism to erase symbols or rename them and reach a known language.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The corresponding table for regular languages is on closure properties of regular languages; the determinism question is on DPDA versus NPDA (DCFLs are closed under complement but not union); the non-context-freeness of $a^n b^n c^n$ is proved with the pumping lemma for CFLs.

PYQs

Which of the following statements is/are CORRECT?

Let L1, L2 be any two context-free languages and R be
any regular language.
Then which of the following is/are CORRECT?
I. L1 U L2is context free.
II. L̅1 is context-free
III. L1 – R is context – free.
IV. L1 ∩ L2 is context – free

Consider the following languages over the alphabet Σ =
{a, b, c}. Let L1 = {anbncm | m, n > 0} and L2 =
{ambncn | m, n > 0}.
Which of the following are context-free languages?
I. (L1 ∪ L2)
II. (L1 ∩ L2)

Consider the following languages.
L1={ai b j ck | i =j, k>=1}
L2={ai b j | j=2i , i >=0}
Which of the following is true?

Let L be a context-free language and M a regular
language. Then the language  L ∩ M is

Consider the languages:
L1 = {anbncm | n, m > 0} and L2 = {anbmcm | n, m > 0},
Which one of the following statements is FALSE?

Let L be a regular language and M be a context-free
language, both over the alphabet Σ . Let Lc and
Mc denote the complements of L and M respectively.
Which of the following statements about the language
Lc U Mc is TRUE?

Consider the following types of languages:
L1: Regular
L2: Context-free
L3: Recursive
L4: Recursively enumerable.
Which of the following is/are TRUE?
I. L3' ∪ L4 is recursively enumerable .
II. L2' ∪ L3 is recursive .
III. L1* ∪ L2 is context-free .
IV. L1 ∪ L2' is context-free.

Self-check

Revision card

References