Context-Free Language

languages

Definition

Context-Free Language

A formal language is called context-free if it can be generated by a context-free grammar.

Equivalently, it is a language accepted by a pushdown automaton.

Inherent Ambiguity

Definition

Inherently Ambiguous Context-Free Language

A context-free language $L$ is called inherently ambiguous if every context-free grammar that generates $L$ is ambiguous.

Link to original

Closure

Context-free languages are closed under:

• union, concatenation, and star,
• homomorphism
• intersection with regular languages.

They are not closed under:

• intersection in general,
• complement.

Counterexample for intersection

Let

$$L_1=\{a^m{b}^m{c}^n\mid m,n\ge 0\}$$

and

$$L_2=\{a^m{b}^n{c}^n\mid m,n\ge 0\}.$$

Both $L_1$ and $L_2$ are context-free. However,

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

and this language is not context-free.

One stack is not enough for intersection $a^n{b}^n$.

Context-free languages can manage one nested dependency well. That is why they are good at patterns such as

Intersection can force two independent dependencies to hold at the same time. In the standard counterexample, one language requires the $a$-block and $b$-block to match, while the other requires the $b$-block and $c$-block to match.

Their intersection therefore requires all three blocks to match:

$$a^n{b}^n{c}^n$$

This is beyond what one pushdown automaton can handle. A useful memory aid is: intersection would force two stacks, and CFLs only have one.

Examples

Complement need not be infinite

The statement that the complement of every context-free language is always infinite is false.

Let $L={\Sigma }^{\ast }$. This language is context-free.

Its complement with respect to ${\Sigma }^{\ast }$ is

$$\overline{L}=\varnothing$$

which is finite.

Therefore, the complement of a context-free language is not necessarily infinite.

Finite complement

Every language with finite complement is context-free.

Let $L$ be a language such that $\overline{L}$ is finite. Then $\overline{L}$ is regular, because every finite language is regular.

Regular languages are closed under complement. Hence $L$ is regular.

Therefore, $L$ is context-free.